Introduction
Constraint-Satisfaction Problems (CSPs), such as map coloring, circuit analysis, or scheduling, are fundamental to AI but often computationally intractable (NP-complete). As problem size increases, standard backtracking search times grow exponentially. Dechter and Pearl (1985) propose a novel framework to mitigate this by leveraging "easy" problem versions to guide the search for difficult ones.
Directional Consistency
A central contribution of the paper is the concept of directional consistency. While traditional methods like arc consistency ensure global compatibility, the authors argue that full consistency is often unnecessary. Instead, they propose Directional Arc-Consistency (DAC) and Directional Path-Consistency (DPC). These methods enforce consistency only in the order variables are instantiated during search, significantly reducing preprocessing costs while guaranteeing backtrack-free solutions for specific graph structures.
The Relaxation and Advice Scheme
To tackle a hard CSP, the authors suggest a "relaxation" strategy that simplifies the problem's underlying constraint graph into a tree (Width-1) or a simple structure (Width-2). Once relaxed, the system doesn't just find one solution; it uses a recursive algorithm to count the number of consistent solutions available for each possible value assignment. These counts serve as a "figure of merit," advising the search algorithm to prioritize values that lead to the highest number of solutions in the simplified model.
Key Insights
- Trees as the Gold Standard: CSPs with tree-structured constraint graphs can be solved in linear time ($O(nk^2)$) once directional arc-consistency is established.
- The Power of Counting: Simply knowing if a value is "possible" in a relaxed model isn't enough. By counting how many solutions a value permits, the algorithm gains a probabilistic sense of which path is most likely to succeed in the original, harder problem.
- Cycle-Cutsets: Complex graphs can be converted into trees by "fixing" a small set of variables (the cycle-cutset). Once those are assigned, the remaining problem is a tree and can be solved instantly.
Experimental Results
The authors evaluated their Advised Backtrack (ABT) algorithm against standard backtracking (RBT) using randomly generated CSPs. ABT dramatically reduced the average number of backtracks from 50 down to 0–3. However, they noted a critical trade-off: generating "perfect" advice can sometimes be more computationally expensive than the original search. The optimal balance is found using "weak advice"—spanning only a portion of the variables—to provide enough guidance to skip most backtracks without heavy overhead.
Conclusion
By formalizing what makes a problem "easy" and extracting quantitative advice from simplified models, Dechter and Pearl provide a powerful meta-heuristic for CSPs. This approach mirrors human problem-solving strategies and offers a path toward more autonomous and efficient AI search techniques.
Summary updated