Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1089023.1089024 | J. ACM |
Keywords | DocType | Volume |
heuristic search,4-peg Towers,a&ast,towers of hanoi,frontier search,best-first search,breadth-first search,best-first search algorithm,algorithm,Hanoi problem,dijkstra's algorithm,Fifteen Puzzle,Closed list,four-peg Towers,bidirectional search,sequence alignment,unidirectional search,sliding-tile puzzles,Open list | Journal | 52 |
Issue | Citations | PageRank |
5 | 42 | 2.32 |
References | Authors | |
30 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard E. Korf | 1 | 3568 | 729.78 |
| Weixiong Zhang | 2 | 1458 | 119.03 |
| Ignacio Thayer | 3 | 49 | 3.12 |
| Heath Hohwald | 4 | 115 | 6.75 |