This paper explores the properties of heuristic best-first search strategies where the scoring function \( f \) depends on all available information from each candidate path, not just the current cost \( g \) and the estimated completion cost \( h \). It demonstrates that several known properties of A* remain valid, such as admissibility and conditions for node expansion, under these more general conditions. The paper examines the computational optimality of A*, defined as never expanding a node that can be skipped by another algorithm with access to the same heuristic information. A hierarchy of four optimality types is defined, and three classes of algorithms and four domains of problem instances are considered. The main results show that A* is not optimal when all cost estimates are optimistic (i.e., \( h \leq h^* \)), but it is optimal over a subset of algorithms that use path-dependent evaluation functions. The paper also provides conditions for node expansion and analyzes the performance of A* under additive cost measures, showing that it is computationally optimal under certain conditions.This paper explores the properties of heuristic best-first search strategies where the scoring function \( f \) depends on all available information from each candidate path, not just the current cost \( g \) and the estimated completion cost \( h \). It demonstrates that several known properties of A* remain valid, such as admissibility and conditions for node expansion, under these more general conditions. The paper examines the computational optimality of A*, defined as never expanding a node that can be skipped by another algorithm with access to the same heuristic information. A hierarchy of four optimality types is defined, and three classes of algorithms and four domains of problem instances are considered. The main results show that A* is not optimal when all cost estimates are optimistic (i.e., \( h \leq h^* \)), but it is optimal over a subset of algorithms that use path-dependent evaluation functions. The paper also provides conditions for node expansion and analyzes the performance of A* under additive cost measures, showing that it is computationally optimal under certain conditions.