ML Anthology

Sparse-Memory Graph Search

Rong Zhou, Eric A. Hansen
IJCAI 2003 pp. 1259-1268
/ijcai/2003/zhou2003ijcai-sparse/

Abstract

We describe a framework for reducing the space complexity of graph search algorithms such as A* that use Open and Closed lists to keep track of the frontier and interior nodes of the search space. We propose a sparse representation of the Closed list in which only a fraction of already expanded nodes need to be stored to perform the two functions of the Closed List – preventing duplicate search effort and allowing solution extraction. Our proposal is related to earlier work on search algorithms that do not use a Closed list at all [Korf and Zhang, 2000]. However, the approach we describe has several advantages that make it effective for a wider variety of problems. 1

PDF Semantic Scholar

Cite

Text

Zhou and Hansen. "Sparse-Memory Graph Search." International Joint Conference on Artificial Intelligence, 2003.

Markdown

[Zhou and Hansen. "Sparse-Memory Graph Search." International Joint Conference on Artificial Intelligence, 2003.](https://mlanthology.org/ijcai/2003/zhou2003ijcai-sparse/)

BibTeX

@inproceedings{zhou2003ijcai-sparse,
  title     = {{Sparse-Memory Graph Search}},
  author    = {Zhou, Rong and Hansen, Eric A.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2003},
  pages     = {1259-1268},
  url       = {https://mlanthology.org/ijcai/2003/zhou2003ijcai-sparse/}
}