chapter 6

General Search Strategies: Look-Back

Yet knowing how way leads on to way, I doubted if I should ever come back.

Robert Frost, “The Road Not Taken”

We have now looked at the basic backtracking algorithm as it applies to CSPs, and at some schemes developed to foresee and avoid some future traps during the algorithm’s forward phase ( Chapter 5). This chapter introduces another class of improvement schemes that attempt to counteract backtracking’s propensity for thrashing, or repeatedly rediscovering the same inconsistencies and partial successes during search. These schemes are invoked when the algorithm gets stuck in a dead-end and prepares to backtrack. Collectively, these are called look-back schemes, and they can be divided into ...

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.