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.