Best-First Search with Maximum Edge Cost Functions.
P. Alex Dow, Richard E. Korf · ISAIM · 2008
Best-first search is a general search technique that uses an evaluation function to determine what nodes to expand. A* is a well-known best-first search algorithm for finding least cost solution paths on search problems where the cost of a solution path is the sum of the edge costs. In this paper, we focus on search problems where the cost of a solution path is the maximum edge cost. We present an algorithm, MaxBF, that is analogous to A* but meant to solve these maximum edge cost problems. We show that the evaluation function used by MaxBF does not meet a condition for the admissibility of best-first sear ch algorithms given by Dechter & Pearl (1985). Additionally, we show that that condition can be loosened to include the MaxBF evaluation function without sacrificing admissibili ty. Another result shows that, while many choices of heuristic function may require A* to reopen closed nodes, a heuristic need only be optimistic to guarantee that it is never benefici al for MaxBF to reopen closed nodes. Finally, we show that, although MaxBF never needs to reopen closed nodes, it may find an alternate path to a closed node that appears better than the original path. This implie s that a naive version of MaxBF could unnecessarily reopen closed nodes. We give a specification for MaxBF that carefully avoids this inefficiency.