Algorithms for constraint satisfaction
Javier Larrosa, Pedro Meseguer · INTELIGENCIA ARTIFICIAL · 2003
This paper describes the main algorithms for solving constraint satisfaction problems, and includes the corresponding encodings (the main different with respect [3] is that, in their paper, they provide a more informal description of the algorithms). We consider three main algorithmic approaches: search, inference and hybrid methods. Search methods can be divided into systematic and non-systematic. We present backtracking as an example of systematic search, and local search as an example of non-systematic search. Inference methods can be divided into complete and incomplete. We describe adaptive consistency as an example of complete inference, and several local consistency algorithms as incomplete inference. We also present some examples of hybrid methods which combine search and inference.