随机约束满足问题的回溯算法分析

提出一种新的随机CSP(constraint sa tisfaction problem)模型,并且通过研究搜索树的平均节点数,分析了回溯算法求解该模型 的平均复杂性.结果表明,这种模型能够生成难解的CSP实例,找到所有的解或证明无解所需的 平均节点数即随变量数的增加而指数增长.因此,该模型可以用来研究难解实例的性质和CSP 算法的性能等问题,从而有助于设计出更为高效的算法.

An Average Time Analysis of Backtracking on Random Constraint Satisfa ction Problems

A new random CSP (constraint satisfaction pro blem) model is proposed in this paper. By analyzing the expected number of nodes in a search tree, the average running time used by the backtracking algorithm o n random constraint satisfaction problems is studied. The results show that the model can generate hard CSP instances, and the expected number of nodes required for finding all solutions or proving that no solution exists becomes exponentia lly large as the number of variables grows. Therefore, the model can be used to analyze the nature of hard instances and evaluate the performance of CSP algorit hms, and hence it helps the researchers to design more efficient algorithms.