Linear-Space est-First Search: Summary of
Richard E. Korf · 1992
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