Hybrids of Search and Inference: Time-Space Trade-Offs
The more constraints one imposes the more one frees oneself.
Throughout this book 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 divided into subproblems, conditioned on the instantiation of a subset of variables, each of which ...