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 the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.