Weak-commitment Search for Solving Constraint Satisfaction Problems
12th National Conference on Artificial Intelligence (AAAI-94), pp. 313--318,1994.
The min-conflict heuristic has been
introduced into backtracking algorithms
and iterative improvement algorithms
as a powerful heuristic for
solving constraint satisfaction problems.
Backtracking algorithms become inefficient
when a bad partial solution
is constructed, since an exhaustive search is
required for revising the bad decision.
On the other hand, iterative improvement algorithms
do not construct a consistent partial
solution and can revise a bad decision without exhaustive search.
However,
most of the powerful heuristics obtained through the long history of
constraint satisfaction studies (e.g., forward checking) presuppose the existence of a consistent partial
solution.
Therefore, these heuristics can not be applied to iterative improvement
algorithms.
Furthermore, these algorithms are not theoretically complete.
In this paper, a new algorithm called weak-commitment search which
utilizes the min-conflict heuristic is developed.
This algorithm removes the drawbacks of backtracking algorithms and iterative
improvement algorithms,
i.e., the algorithm can revise bad decisions without exhaustive
search, the completeness of the algorithm is guaranteed, and various heuristics can be
introduced since a consistent partial solution is constructed.
The experimental results on various example problems
show that this algorithm is 3 to 10 times more efficient than
other algorithms.