Generalized best-first search strategies and the optimality of A*

TLDR

The paper develops a framework to analyze the optimality of heuristic best‑first search strategies, focusing on A* and related algorithms, and seeks to classify the strongest optimality guarantees achievable for each algorithm–domain pair. Using a scoring function that incorporates all path information, the authors define a hierarchy of four optimality types, evaluate three algorithm classes across four problem domains, and determine the optimality level and corresponding algorithm for each class‑domain combination. The study finds that A* is not optimal for all admissible heuristics, but it becomes optimal when heuristics are consistent or when restricted to best‑first algorithms guided by path‑dependent evaluation functions, and no superior optimal algorithm exists in the general case.

Abstract

This paper reports several properties of heuristic best-first search strategies whose scoring functions ƒ depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h . It is shown that several known properties of A* retain their form (with the minmax of f playing the role of the optimal cost), which helps establish general tests of admissibility and general conditions for node expansion for these strategies. On the basis of this framework the computational optimality of A*, in the sense of never expanding a node that can be skipped by some other algorithm having access to the same heuristic information that A* uses, is examined. A hierarchy of four optimality types is defined and three classes of algorithms and four domains of problem instances are considered. Computational performances relative to these algorithms and domains are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm for achieving it. The main results of this paper relate to the class of algorithms that, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., h ≤ h *). On this class, A* is shown to be not optimal and it is also shown that no optimal algorithm exists, but if the performance tests are confirmed to cases in which the estimates are also consistent, then A* is indeed optimal. Additionally, A* is also shown to be optimal over a subset of the latter class containing all best-first algorithms that are guided by path-dependent evaluation functions.