A Breadth-First Approach to Memory-Efficient Graph Search
Abstract
Recent work shows that the memory requirements of A * and related graph-search algorithms can be reduced substantially by only storing nodes that are on or near the search frontier, using special techniques to prevent node regeneration, and recovering the solution path by a divide-and-conquer technique. When this approach is used to solve graph-search problems with unit edge costs, we have shown that a breadth-first search strat-egy can be more memory-efficient than a best-first strat-egy. We provide an overview of our work using this approach, which we call breadth-first heuristic search.
Cite
Text
Zhou and Hansen. "A Breadth-First Approach to Memory-Efficient Graph Search." AAAI Conference on Artificial Intelligence, 2006.Markdown
[Zhou and Hansen. "A Breadth-First Approach to Memory-Efficient Graph Search." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/zhou2006aaai-breadth/)BibTeX
@inproceedings{zhou2006aaai-breadth,
title = {{A Breadth-First Approach to Memory-Efficient Graph Search}},
author = {Zhou, Rong and Hansen, Eric A.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2006},
pages = {1695-1699},
url = {https://mlanthology.org/aaai/2006/zhou2006aaai-breadth/}
}