Backjump-based backtracking for constraint satisfaction problems

✍ Scribed by Rina Dechter; Daniel Frost

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 385 KB
• Volume: 136
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/s0004-3702(02)00120-0

✦ Synopsis

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.