论文部分内容阅读
提出一种新的随机ＣＳＰ（ｃｏｎｓｔｒａｉｎｔ ｓａｔｉｓｆａｃｔｉｏｎ ｐｒｏｂｌｅｍ）模型，并且通过研究搜索树的平均节点数，分析了回溯算法求解该模型的平均复杂性。结果表明，这种模型能够生成难解的ＣＳＰ实例，找到所有的解或证明无解所需的平均节点数即随变量数的增加而指数增长。因此，该模型可以用来研究难解实例的性质和ＣＳＰ算法的性能问题，从而有助于设计出更为高效的算法。