This paper explores generalized best-first search strategies and the optimality of A*. It shows that several properties of A* retain their form when using scoring functions that depend on all available information, not just current cost and estimated completion cost. It establishes general tests for admissibility and node expansion for these strategies. The computational optimality of A* is examined, and a hierarchy of four optimality types is defined. 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, the strongest type of optimality and the algorithm achieving it are identified. The main results relate to algorithms that return optimal solutions when all cost estimates are optimistic. A* is shown to be not optimal in this class, but if performance tests confirm cases where estimates are consistent, A* is indeed optimal. Additionally, A* is optimal over a subset of this class containing all best-first algorithms guided by path-dependent evaluation functions. The paper discusses the algorithm BF*, a specialization of generalized best-first search, and its properties. It examines the termination and completeness of BF* on infinite graphs, the quality of the solution found, and the admissibility of BF*. It also presents conditions for node expansion and analyzes the performance of A* under additive cost measures. The paper concludes that A* is optimal under certain conditions, but not universally. It also discusses the importance of M in guaranteeing the termination of BF* on infinite graphs and in identifying the solution path found. The paper also examines the admissibility of BF* and provides conditions for node expansion. It concludes that A* is optimal under certain conditions, but not universally.This paper explores generalized best-first search strategies and the optimality of A*. It shows that several properties of A* retain their form when using scoring functions that depend on all available information, not just current cost and estimated completion cost. It establishes general tests for admissibility and node expansion for these strategies. The computational optimality of A* is examined, and a hierarchy of four optimality types is defined. 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, the strongest type of optimality and the algorithm achieving it are identified. The main results relate to algorithms that return optimal solutions when all cost estimates are optimistic. A* is shown to be not optimal in this class, but if performance tests confirm cases where estimates are consistent, A* is indeed optimal. Additionally, A* is optimal over a subset of this class containing all best-first algorithms guided by path-dependent evaluation functions. The paper discusses the algorithm BF*, a specialization of generalized best-first search, and its properties. It examines the termination and completeness of BF* on infinite graphs, the quality of the solution found, and the admissibility of BF*. It also presents conditions for node expansion and analyzes the performance of A* under additive cost measures. The paper concludes that A* is optimal under certain conditions, but not universally. It also discusses the importance of M in guaranteeing the termination of BF* on infinite graphs and in identifying the solution path found. The paper also examines the admissibility of BF* and provides conditions for node expansion. It concludes that A* is optimal under certain conditions, but not universally.