Linear-Space Best-First Search: Summary of Results

Richard E. Korf

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 the 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, at the cost of only constant factor in time complexity in our experiments.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.