Foundations of Artificial Intelligence, Vol. 2, Suppl. (C), 2006
Chapter 7 Tractable Structures for Constraint Satisfaction Problems
Throughout the past few decades two primary constraint processing schemes emerge— those based on conditioning or search, and those based on inference or derivation. Search in constraint satisfaction takes the form of depth-first backtracking, while inference is performed by variable-elimination and tree-clustering algorithms, or by bounded local consistency enforcing. Compared to human problem solving techniques, conditioning is analogous to guessing (a value of a variable), or reasoning by assumption. The problem is then divided into subproblems, ...