CSP Solving Algorithms
Khaled Ghédira, Bernard Dubuisson · 2013
Various techniques for solving constraint satisfaction problems (CSP) have been developed and classified into two categories: complete resolution methods and incomplete methods. This chapter discusses the complete resolution methods that guarantee completeness (quality) at the expense of efficiency (temporal complexity). The algorithms, including the backtracking algorithm, look-back algorithms, and look-ahead algorithms discussed in this chapter are all based on tree search. CSPs are combinatorial problems known for being NP hard. Since they are all exponential in the worst case, several comparison criteria have been proposed, mainly to estimate the search cost, which is often made on the basis of randomly generated problems. The chapter presents random generation of problems and phase transition as phenomena that were observed in a lot of NP-hard problems.