A* with an Admissible Heuristic Returns an Optimal Solution
Claim
Let \(G = (V, E)\) be a graph with non-negative edge costs and goal set \(\mathcal{G} \subseteq V\). Let \(h : V \to \mathbb{R}_{\ge 0}\) be an admissible heuristic: \(h(n) \le h^*(n)\) for every \(n\), where \(h^*(n)\) is the cost of a cheapest path from \(n\) to \(\mathcal{G}\) (with \(h^*(n) = \infty\) if \(n\) cannot reach \(\mathcal{G}\)). Assume \(h(g) = 0\) for every \(g \in \mathcal{G}\).
Then A* search — selecting the open-list node of minimum \(f(n) = g(n) + h(n)\), testing the goal at pop time — returns a solution whose cost equals \(C^* := \min_{g \in \mathcal{G}} h^*(s)\), the cost of an optimal path from the start \(s\) to a goal (Hart et al. 1968).
We prove the result for tree search (no closed list). The graph-search version follows by adding the standard closed-list-reopen step described in the A* article, or by strengthening the hypothesis to consistency, after which no reopens occur.
Setup
Throughout, let \(C^*\) be the optimal solution cost and fix any optimal path \(\pi^* = (s = n_0, n_1, \ldots, n_k = g^*)\) with \(g^* \in \mathcal{G}\) and total cost \(C^*\). For any node \(n\) that A* has reached, \(g(n)\) denotes the cost of the path A* used to reach \(n\) — so \(g(n)\) is an upper bound on the true shortest-path cost from \(s\) to \(n\), with equality on \(\pi^*\).
Lemma 1: Some Node of \(\pi^*\) Is Always on the Open List Until \(g^*\) Is Popped
At any point during the algorithm before \(g^*\) is popped, at least one node of the optimal path \(\pi^*\) is on the open list.
Proof. By induction on pops. Initially the open list contains \(s = n_0\), which is on \(\pi^*\). Suppose immediately before some pop the claim holds, and let \(n_i\) be a node of \(\pi^*\) on the open list. If \(n_i\) is not popped, the claim still holds afterward. If \(n_i\) is popped:
- If \(n_i = g^*\), the algorithm halts; the claim’s window (“until \(g^*\) is popped”) has ended.
- Otherwise \(i < k\), and the expansion of \(n_i\) generates its successor on \(\pi^*\), namely \(n_{i+1}\), and adds it to the open list. (In tree search, every successor is added; in graph search with a closed list, \(n_{i+1}\) is added as long as it has not been closed with a cheaper \(g\), which it has not, since the path \(\pi^*\) provides the cheapest possible \(g(n_{i+1})\).) So \(n_{i+1} \in \pi^*\) is on the open list afterward. \(\square\)
Lemma 2: Every Node of \(\pi^*\) Has \(f \le C^*\)
For every \(n_i\) on the optimal path,
\[ f(n_i) = g(n_i) + h(n_i) \le g^*(n_i) + h^*(n_i) = C^*, \]
where \(g^*(n_i)\) is the cost of the prefix \(n_0 \to \cdots \to n_i\) of \(\pi^*\).
Proof. The path A* used to reach \(n_i\) has cost \(g(n_i) \le g^*(n_i)\) (since \(g^*(n_i)\) is the cost of one such path, namely the optimal-path prefix). Admissibility gives \(h(n_i) \le h^*(n_i)\). The two bounds along the optimal path sum to \(g^*(n_i) + h^*(n_i) = C^*\). \(\square\)
Main Argument
Suppose for contradiction that A* terminates by popping a goal \(g'\) with \(g(g') > C^*\). Consider the moment just before \(g'\) is popped. By Lemma 1, some node \(n_i\) of \(\pi^*\) is on the open list. By Lemma 2,
\[ f(n_i) \le C^* < g(g') = g(g') + h(g') = f(g'), \]
using \(h(g') = 0\) at the goal. Then \(n_i\) has strictly smaller \(f\)-value than \(g'\) on the open list, so A* would pop \(n_i\) before \(g'\) — contradicting the choice of \(g'\) as the popped node.
Hence \(g(g') \le C^*\). But \(g(g')\) is the cost of an actual path from \(s\) to a goal, so \(g(g') \ge C^*\). Therefore \(g(g') = C^*\), and the path A* returns is optimal. \(\blacksquare\)
Why the Goal Test Must Happen at Pop Time
The argument relies critically on testing the goal when popped, not when generated. If the goal test fires on generation, A* may return the first goal it encounters, whose path may be suboptimal: the optimal path through some other branch of the open list may not yet have been explored. The pop-time test guarantees that when a goal is selected, no open-list node — including ancestors of cheaper goal paths — has smaller \(f\), which is exactly the condition needed by Lemmas 1–2.
Strengthening to Consistency
If \(h\) is consistent (\(h(n) \le c(n, n') + h(n')\) for every edge), the result strengthens: \(f\) is non-decreasing along any path A* expands, so the first time A* pops any node \(n\), the value \(g(n)\) already equals the optimal \(g^*(n)\). As a consequence, in graph search no node is ever re-opened, and each node is expanded at most once. (proof)