Thumbnail
Access Restriction
Subscribed

Author Korf, Richard E. ♦ Zhang, Weixiong ♦ Thayer, Ignacio ♦ Hohwald, Heath
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword A* algorithm ♦ Dijkstra's algorithm ♦ Towers of Hanoi ♦ Best-first search ♦ Bidirectional search ♦ Breadth-first search ♦ Heuristic search ♦ Sequence alignment ♦ Sliding-tile puzzles
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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 52
Issue Number 5
Page Count 34
Starting Page 715
Ending Page 748


Open content in new tab

   Open content in new tab
Source: ACM Digital Library