chapter 10

Hybrids of Search and Inference: Time-Space Trade-Offs

The more constraints one imposes the more one frees oneself.

Igor Stravinski

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 ...

Get Constraint Processing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.