ML Anthology

Memory-Bounded Bidirectional Search

Hermann Kaindl, Aliasghar Khorsand
AAAI 1994 pp. 1359-1364
/aaai/1994/kaindl1994aaai-memory/

Abstract

Previous approaches to bidirectional search require exponential space, and they are either less efficient than unidirectional search for finding optimal solutions, or they cannot even find such solutions for difficult problems. Based on a memory-bounded unidirectional algorithm for trees (SMA*), we developed a graph search extension, and we used it to construct a very efficient memory-bounded bidirectional algorithm. This bidirectional algorithm can be run for difficult problems with bounded memory. In addition, it is much more efficient than the corresponding unidirectional search algorithm also for finding optimal solutions to difficult problems. In summary, bidirectional search appears to be the best approach to solving difficult problems, and this indicates the extreme usefulness of a paradigm that was neglected for long. Notation s, t l-1 (4 ra (4 d d’ d(n) hf (4 il$f F$) c*

PDF AAAI Semantic Scholar

Cite

Text

Kaindl and Khorsand. "Memory-Bounded Bidirectional Search." AAAI Conference on Artificial Intelligence, 1994.

Markdown

[Kaindl and Khorsand. "Memory-Bounded Bidirectional Search." AAAI Conference on Artificial Intelligence, 1994.](https://mlanthology.org/aaai/1994/kaindl1994aaai-memory/)

BibTeX

@inproceedings{kaindl1994aaai-memory,
  title     = {{Memory-Bounded Bidirectional Search}},
  author    = {Kaindl, Hermann and Khorsand, Aliasghar},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1994},
  pages     = {1359-1364},
  url       = {https://mlanthology.org/aaai/1994/kaindl1994aaai-memory/}
}