The optimality of A* revisited
Rina Dechter, Judea Pearl · National Conference on Artificial Intelligence · 1983
This paper examines the optimality of A*, in the sense of expanding the least number of distinct nodes, over three classes of algorithms which return solutions of comparable costs to that found by A*. We first show that A* is optimal over those algorithms guaranteed to find a solution at least as good as A*'s for every heuristic assignment h. Second, we consider a wider class of algorithms which, like A*, are guaranteed to find an optimal solution. (i.e., admissible) if all cost estimates are optimistic (i.e., h≤h*). On this class we show that A* is not optimal and that no optimal algorithm exists unless h is also consistent, in which case A* is optimal. Finally we show that A* is optimal over the subclass of best-first algorithms which are admissible whenever h≤h*.