backjumping
Sign in to saveIn constraint programming and SAT solving, backjumping (also known as non-chronological backtracking or intelligent backtracking) is an enhancement for backtracking algorithms which reduces the search space. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables x_1,\ldots,x_n is used, but the same considerations apply to a dynamic order of evaluation.
~14 min read
Article
9 sectionsContents
- Definition
- Backjumping at leaf nodes
- Backjumping at internal nodes
- Simplifications
- Graph-based backjumping
- Conflict-based backjumping
- See also
- Notes and references
- Bibliography
In constraint programming and SAT solving, backjumping (also known as non-chronological backtracking or intelligent backtracking) is an enhancement for backtracking algorithms which reduces the search space. While backtracking always goes up one level in the search tree when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables x_1,\ldots,x_n is used, but the same considerations apply to a dynamic order of evaluation.
Image:Backtracking-no-backjumping.svg|A search tree visited by regular backtracking Image:Backtracking-with-backjumping.svg|A backjump: the grey node is not visited