The Optimality of A + Revisited

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 3

Search

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 And 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*).