Linear-Space Best-First Search: Summary of Results

Best-first search is a general search algorithm that, always expands next a frontier node of lowest cost. Its applicability, however, is limited by its exponential memory requirement. Iterative deepening, a previous approach to this problem, does not expand nodes in best-first, order if t’ he cost, function can decrease along a path. We present a linear-space best-first search algorithm (RBFS) that always explores new nodes in best-first order, regardless of the cost function, and expands fewer nodes than iterative deepening with a. nondecreasing cost function. On the sliding-tile puzzles, RBFS with a weighted evaluation function dramatically reduces computation time with only a small penalty in solution cost. In general, RBFS reduces the space complexity of best-first search from exponential to linear, a. t the cost of only a constant factor in time complexity in our expcriments.

Authors

• Richard E. Korf

Keywords

No keywords are indexed for this paper.