Dynamic Backtracking

JAIR 1993 pp. 25-46

doi:10.1613/JAIR.1 /jair/1993/ginsberg1993jair-dynamic/

Abstract

Because of their occasional need to return to shallow points in a search tree, existing backtracking methods can sometimes erase meaningful progress toward solving a search problem. In this paper, we present a method by which backtrack points can be moved deeper in the search space, thereby avoiding this difficulty. The technique developed is a variant of dependency-directed backtracking that uses only polynomial space while still providing useful control information and retaining the completeness guarantees provided by earlier approaches.

PDF JAIR Semantic Scholar

Cite

Text

Ginsberg. "Dynamic Backtracking." Journal of Artificial Intelligence Research, 1993. doi:10.1613/JAIR.1

Markdown

[Ginsberg. "Dynamic Backtracking." Journal of Artificial Intelligence Research, 1993.](https://mlanthology.org/jair/1993/ginsberg1993jair-dynamic/) doi:10.1613/JAIR.1

BibTeX

@article{ginsberg1993jair-dynamic,
  title     = {{Dynamic Backtracking}},
  author    = {Ginsberg, Matthew L.},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {1993},
  pages     = {25-46},
  doi       = {10.1613/JAIR.1},
  volume    = {1},
  url       = {https://mlanthology.org/jair/1993/ginsberg1993jair-dynamic/}
}