Sparse-Memory Graph Search

Zhou, Rong; Hansen, Eric A.

Sparse-Memory Graph Search

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1259-1267.

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.

Rong Zhou, and Eric A. Hansen. 2003. Sparse-Memory Graph Search. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 1259–1267. https://ijcai.org/proceedings/2003/179

@inproceedings{ijcai2003p179,
  title     = {Sparse-Memory Graph Search},
  author    = {Zhou, Rong and Hansen, Eric A.},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {1259--1267},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/179},
}

TY  - CPAPER
TI  - Sparse-Memory Graph Search
AU  - Zhou, Rong
AU  - Hansen, Eric A.
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 1259
EP  - 1267
UR  - https://ijcai.org/proceedings/2003/179
ER  -