@article{Korf199341,
    Abstract = {Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, Dijkstra's single-source shortest-path algorithm, and the A∗ algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do 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 nonmonotonic 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 a constant factor in time complexity in our experiments.},
    Author = {Korf, Richard E.},
    File = {Linear-space best-first search - Korf (0) (0) - a - a - v.pdf},
    ISSN = {0004-3702},
    Journal = {Artificial Intelligence},
    Number = {1},
    Pages = {41 - 78},
    Title = {Linear-space best-first search},
    URL = {http://www.sciencedirect.com/science/article/pii/000437029390045D},
    Volume = {62},
    Year = {1993},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/000437029390045D},
    bdsk-url-2 = {http://dx.doi.org/10.1016/0004-3702(93)90045-D},
    date-added = {2017-01-17 18:22:42 +0000},
    date-modified = {2017-01-17 18:22:42 +0000},
    doi = {10.1016/0004-3702(93)90045-D}
}

@article{Korf199341, Abstract = {Best-first search is a general heuristic search algorithm that always expands next a frontier node of lowest cost. It includes as special cases breadth-first search, Dijkstra's single-source shortest-path algorithm, and the A∗ algorithm. Its applicability, however, is limited by its exponential memory requirement. Previous approaches to this problem, such as iterative deepening, do 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 nonmonotonic 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 a constant factor in time complexity in our experiments.}, Author = {Korf, Richard E.}, File = {Linear-space best-first search - Korf (0) (0) - a - a - v.pdf}, ISSN = {0004-3702}, Journal = {Artificial Intelligence}, Number = {1}, Pages = {41 - 78}, Title = {Linear-space best-first search}, URL = {http://www.sciencedirect.com/science/article/pii/000437029390045D}, Volume = {62}, Year = {1993}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/000437029390045D}, bdsk-url-2 = {http://dx.doi.org/10.1016/0004-3702(93)90045-D}, date-added = {2017-01-17 18:22:42 +0000}, date-modified = {2017-01-17 18:22:42 +0000}, doi = {10.1016/0004-3702(93)90045-D} }