O'Reilly logo

Constraint Processing by Rina Dechter

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required