homeresources & publications › a breadth-first approach to memory-efficient graph search

TECHNICAL PUBLICATIONS:

A breadth-first approach to memory-efficient graph search

 

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, a breadth-first search strategy can be more memory-efficient than a best-first strategy. We provide an overview of our work using this approach, which we call breadth-first heuristic search.

 
citation

Zhou, R. ; Hansen, E. A. A breadth-first approach to memory-efficient graph search. Twenty-First National Conference on Artificial Intelligence (AAAI-06); 2006 July 16-20; Boston; MA.