- 213 views
- 185 downloads
A Theoretical Evaluation of Selected Backtracking Algorithms
-
- Author(s) / Creator(s)
-
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
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International