95 Scopus citations

Abstract

The critical resource that limits the application of best-first search is memory. We present a new class of best-first search algorithms that reduce the space complexity. The key idea is to store only the Open list of generated nodes, but not the Closed list of expanded nodes. The solution path can be recovered by a divide-and-conquer technique, either as a bidirectional or unidirectional search. For many problems, frontier search dramatically reduces the memory required by best-first search. We apply frontier search to breadth-first search of sliding-tile puzzles and the 4-peg Towers of Hanoi problem, Dijkstra's algorithm on a grid with random edge costs, and the A* algorithm on the Fifteen Puzzle, the four-peg Towers of Hanoi Problem, and optimal sequence alignment in computational biology.

Original languageEnglish
Pages (from-to)715-748
Number of pages34
JournalJournal of the ACM
Volume52
Issue number5
DOIs
StatePublished - Sep 2005

Keywords

  • A* algorithm
  • Best-first search
  • Bidirectional search
  • Breadth-first search
  • Dijkstra's algorithm
  • Heuristic search
  • Sequence alignment
  • Sliding-tile puzzles
  • Towers of Hanoi

Fingerprint

Dive into the research topics of 'Frontier search'. Together they form a unique fingerprint.

Cite this