Abstract
A* is widely recognized as the optimal search algorithm for shortest-path problems. While its optimality extends to generalized "cost algebras," its efficiency—the guarantee of expanding the minimum number of nodes—is less certain in these settings. This paper re-evaluates the classic efficiency results established by Dechter and Pearl (1985), identifying a significant error in the original additive setting and exploring how these guarantees translate to non-additive cost structures.
Introduction
The A algorithm has long been the benchmark for finding optimal paths in graphs. In their seminal 1985 work, Dechter and Pearl identified five conditions (Results R1 through R5) under which A is "0-optimal," meaning no other algorithm in its class can find an optimal solution while expanding fewer nodes. However, modern applications often require "cost algebras" where path costs are not simply summed. For instance, in the widest path problem, the cost is the minimum capacity along the route. This paper investigates whether A* maintains its efficiency edge in these generalized mathematical structures.
Methods: Cost Algebras and DXBB Algorithms
The researchers define a cost algebra as a monoid with a total ordering and an "isotonic" operator. Isotonicity ensures that if path A is cheaper than path B, adding the same segment to both preserves their relative order. To evaluate A, the authors compare it against the class of DXBB algorithms* (Deterministic, Expansion-based, Black Box). These algorithms interact with the graph solely through node expansion, lacking any global "peek" at the structure.
The Fall of Result R3
One of the most striking findings is the discovery of a 34-year-old error. Result R3, which claimed A's optimal efficiency among algorithms using consistent heuristics, is shown to be false even in traditional additive settings. The authors introduce the GC1 algorithm as a counterexample. Unlike A, GC1 can "learn" and update heuristic values during the search process, allowing it to skip nodes that A* would be forced to expand.
Generalizing Efficiency to Cost Algebras
The paper systematically tests R1-R5 in the context of cost algebras:
- R1, R2, and R5 remain valid; A* is still optimally efficient under these conditions.
- R4 fails in cost algebras. Unlike the continuous nature of real numbers, cost algebras can have "gaps" (discrete cost sets). These gaps allow competing algorithms to find shortcuts that A* misses due to its assumption of a more fluid cost landscape.
- Strict Isotonicity: The authors show that Nilsson’s Result 6 (stronger heuristics lead to fewer expansions) only holds in cost algebras if isotonicity is strict—meaning adding a cost must strictly increase the total cost.
New Theoretical Foundations
To provide a more robust framework, the authors propose Theorem 8. This theorem defines the set of nodes that any DXBB algorithm "cost-dominating" A* must expand. It centers on the concept of "surely expanded" nodes—those whose estimated cost is strictly less than the optimal cost $C^*$.
Conclusion
This research refines our understanding of heuristic search. By correcting a long-standing error in the shortest-path literature and mapping the boundaries of efficiency in cost algebras, the authors pave the way for more advanced search algorithms. The success of heuristic-updating algorithms like GC1 suggests that the next generation of search techniques may move beyond the static heuristic approach of traditional A*.
Summary updated