A Theoretical Evaluation of Selected Backtracking Algorithms

• Author(s) / Creator(s)

  • Kondrak, Grzegorz

• Technical report TR94-10. In recent years, numerous new backtracking algorithms have been proposed. The algorithms are usually evaluated by empirical testing. This method, however, has its limitations. Our thesis adopts a different, purely theoretical approach, which is based on characterizations of the sets of search tree nodes visited by the backtracking algorithms. A new notion of inconsistency between instantiations and variables is introduced, a useful tool for describing such well-known concepts as backtrack, backjump, and domain annihilation. The characterizations enable us to: prove the correctness of the algorithms, and partially order the algorithms according to two standard performance measures: the number of visited nodes, and the number of performed consistency checks. Among other results, we prove, for the first time, the correctness of Backjumping and Conflict-Directed Backjumping, and show that Forward Checking never visits more nodes than Backjumping. Our approach leads us also to propose a modification to two hybrid backtracking algorithms, Backmarking with Backjumping (BMJ) and Backmarking with Conflict-Directed Backjumping (BM-CBJ), so that they always perform less consistency checks than the original algorithms. | TRID-ID TR94-10

• Date created

  1994

• Subjects / Keywords

  • Backtracking
  • Constraint satisfaction

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3CC0TT17

• License

  Attribution 3.0 International