Constraint Satisfaction Problems: Algorithms And Complexity

Many classes of problems in database retrieval, VLSI design, computer vision, theorem proving, robot planning, machine learning, and other areas of AI are known to be constraint satisfaction problems(CSPs) in their most general forms. Considering the far and wide applications in so many fields as well as the surprising developments on the theory of computational complexity in recent years, we decide to study CSPs for the algorithms and complexities.The main work of this dissertation is on those CSPs which belong to NP-Complete problems, such as Satisfiability(SAT), K-Coloring and Hamilton Circle problems. Not only have we proposed a series of efficient algorithms for this kind of problems, we have also discussed the hard&easy distributions and the phase transitions of CSPs.The best known algorithms for CSPs are based on local search and backtracking. Combing the idiosyncrasy of each constraint satisfaction problem with the strategy of "seperate and conquer", the dissertation proposes a kind of hybrid problem solving algorithm—Multiple-stage Search Rearrangement Algorithm(MSRA), which can quickly and completely solve various CSPs. The experimental results demonstrate the favorable performance of MSRA. Besides, we have given a new empirical solution of N-Queens problems and described its peculiarity.Furthermore, the average time complexity of MSRA algorithm is analyzed. With the experimental results, we have proved the correctness of the above analysis.Note that NP-Complete theory is only concerned about the worst-case complexity and is nearly impossible to be applied in practical problem solving algorithms, this dissertation discusses the intractabilities of CSPs using experimental methods. Since every algorithm must face with many specific problem instances, the more important thing is the "Hardness" of each problem instance and its distribution. It has been found that phase transition widely exists in CSPs. In this dissertation, we have not only confirmed the existence of phase transition, but also found its many more interesting features. At last, we provide a simple analysis method for explaining the phenomena occuring in the above experiments.After many careful experimental analyses and comparations, we have found:· It is more reasonable for us to find a solution(an assignment of all variables) than to prove the satisfiability of a CSP problem instance.· If the characteristics of a CSP problem have been fully understood, the strategy of "seperate and conquer" is usually very efficient.