Abstract
This paper provides a rigorous mathematical treatment of the optimality of the A search algorithm. While A is widely recognized as a standard for heuristic search, its absolute supremacy depends heavily on the properties of the heuristic function used. We examine the conditions under which A* is optimally efficient among various classes of algorithms, specifically focusing on the roles of admissibility and consistency.
Introduction
In the early 1980s, A was already established as the standard for finding shortest paths in graphs using heuristics. It was known to be "admissible"—guaranteed to find an optimal solution if the heuristic $h(n)$ never overestimates the actual cost to the goal ($h \le h^*$). However, its optimality—whether it expands the minimum number of nodes possible—remained a subject of debate. Dechter and Pearl (1983) set out to formally define optimality and determine the conditions under which A achieves it.
Problem Formulation and Methodology
The authors compare A* against three increasingly broad classes of algorithms:
- Class $A_g$: Algorithms that return solutions at least as good as A* for any heuristic assignment.
- Class $A_c$ (Compatible): Algorithms guaranteed to find the optimal solution (admissible) whenever the heuristic is optimistic ($h \le h^*$).
- Class GBF (Generalized Best-First): A subclass of algorithms that select nodes for expansion based on a merit function $f$, similar to A*.
The metric for optimality is the number of distinct nodes expanded. An algorithm is optimal over a class if, for every problem instance, it expands no more nodes than any other algorithm in that class.
Key Insights: Consistency and the Node Tradeoff
A central finding of the paper is the distinction between admissible and consistent heuristics. A heuristic is consistent (or monotonic) if it satisfies the triangle inequality: $h(n) \le c(n, n') + h(n')$.
The Node Tradeoff
If a heuristic is admissible but inconsistent, it is possible to design an algorithm that skips a node A would expand. However, the authors prove a "tradeoff" rule: any such algorithm must expand at least one other node that A would have skipped to remain admissible. This "weak optimality" suggests that while A* can be "beaten" on specific nodes, it cannot be outperformed globally without a cost elsewhere.
Consistency as the Requirement for Absolute Optimality
The most significant takeaway is that A's absolute optimality is tied to consistency. If the heuristic $h$ is consistent, no algorithm using the same information can ever expand fewer nodes than A.
Key Results
The paper establishes several landmark theorems:
- Theorem 1: A is optimal over all algorithms that are "at least as good as A" across all possible heuristic assignments.
- Theorem 2: A* is not strictly optimal over the class of all admissible algorithms if the heuristic is inconsistent, but it remains "weakly optimal."
- Theorem 3: If the heuristic is consistent, A* is truly optimal over all admissible algorithms.
- Theorem 4: A* is the most efficient algorithm within the entire family of Generalized Best-First search strategies.
Discussion and Limitations
The study focuses strictly on the number of nodes expanded. It does not account for computational overhead (managing Open/Closed lists) or memory constraints, which are significant in practice. Furthermore, the proofs assume additive path costs. Despite these limitations, this work effectively "closed the book" on the theoretical debate regarding A*'s efficiency, shifting the field's focus toward developing better heuristics and managing memory during search.
Summary updated