**Abstract**

This paper reports several properties of heuristic best-first search strategies whose scoring
functionsfdepend 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 offplaying 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 casesin 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.