A - algorithm — heuristic, admissibility, consistency — important for GNC: Visual walkthrough

What this page proves, in one breath: we will build — from nothing — the single most important fact about A*: if your guess never overpromises, the first goal A* pulls out of its queue is guaranteed to be the shortest possible. We prove it in pictures, one idea per figure, then show exactly where it breaks when the guess lies.

Everything here rests on the parent note's three functions. We restate them once, in plain words, before we use a single symbol.

The three quantities (nothing assumed). Picture a road network of nodes (places, drawn as dots) joined by edges (roads, drawn as lines). Each edge has a cost — how expensive it is to travel it (distance, time, fuel). We require every edge cost to be $\geq 0$ (no road pays you to walk it); this is the standard setting and it is what makes the estimates below sensible.

$g (n)$ = the real cost of the cheapest road we have actually found from the start to the node $n$ . It is money already spent.
$h (n)$ = a guess of the remaining cost from $n$ onward to the goal. It is a peek, not a fact.
$f (n) = g (n) + h (n)$ = ==guessed total cost of a whole trip that passes through $n$ ==. Spent + still-owed.

A* always pulls out (we say "pops") the frontier node with the smallest $f$ . The frontier — the "open list" — is the ring of dots we have reached but not yet expanded.

We also need one word: $h^{*} (n)$ = the true cheapest remaining cost from $n$ to the goal. We never know it while running (that is why we need a guess $h$ ), but it exists, and our whole proof compares $h$ against it. Because every edge cost is $\geq 0$ , this true remaining cost is itself never negative: $h^{*} (n) \geq 0$ .

This walkthrough needs only admissibility ( $0 \leq h \leq h^{*}$ ). It does not need the triangle inequality, Bellman's principle, or the stronger property called consistency — those decide a different question (whether A* ever has to re-expand a closed node), covered in the parent note, not the optimality proof here.

Step 1 — Set the stage: start, goal, and the frontier

WHAT. We draw a start node $S$ , a goal node $G$ , and colour the frontier — the dots we have reached but not yet fully explored — in amber. Everything behind the frontier is "closed" (done); everything ahead is unexplored.

WHY. Every proof about A* is really a proof about the moment before a bad thing could happen. To reason about that moment we must first see the picture of the search in progress: a wavefront of amber frontier nodes sweeping from $S$ toward $G$ .

PICTURE. Look at the amber ring in the figure. Anything not yet reached lies beyond it, so any path from $S$ to $G$ that is not yet finished must cross that ring at some dot. Hold that thought — it becomes Step 3.

Step 2 — Define the enemy: a suboptimal goal $G_{2}$

WHAT. Suppose, for contradiction, that A* is about to pop a goal node we call $G_{2}$ whose found cost is worse than optimal. Write the true best total cost as $C^{*}$ . So $g (G_{2}) > C^{*}$ .

WHY this move. We use proof by contradiction: assume the disaster (popping a bad goal first) and show it forces an impossibility. If a bad goal can never be popped first, then the first goal popped is optimal — which is exactly what we want.

$cost we found to reach G_{2} g (G_{2}) > true best possible total C^{*}$

$g (G_{2})$ — the real cost of the path A* has for this goal.
$C^{*}$ — the length of the genuinely shortest $S \to G$ route.
The strict $>$ is the assumption "this goal is worse than optimal."

PICTURE. The figure shows two goal-coloured dots: the true optimal goal at cost $C^{*}$ (cyan) and the impostor $G_{2}$ at a bigger cost (amber). We will prove A* can't reach for the amber one first.

Step 3 — There is always a good node $n$ waiting on the frontier

WHAT. Take the true optimal path from $S$ to $G$ . It has not been fully explored yet (we haven't popped a goal). By Step 1's picture, it must cross the amber frontier at some node — call it $n$ . This $n$ sits on an optimal path and is on the open list.

WHY. We need a concrete node whose $f$ -value we can bound. The optimal path is the perfect place to find one, because along an optimal path the numbers behave beautifully (Step 4).

PICTURE. Follow the cyan optimal path in the figure; where it pierces the amber ring, that dot is $n$ . It is the "champion" waiting in the queue.

Step 4 — The champion's $f$ can never exceed $C^{*}$

WHAT. We compute $f (n)$ and squeeze it below $C^{*}$ .

$f (n) = true cost S \to n g (n) + guess n \to G h (n) \leq g (n) + true cost n \to G h^{*} (n) = C^{*} .$

Term by term:

$g (n)$ — because $n$ lies on the optimal path, this is the optimal cost of getting to $n$ .
$h (n) \leq h^{*} (n)$ — this is admissibility: the guess never overpromises. This inequality is the entire engine of the proof.
$g (n) + h^{*} (n) = C^{*}$ — spent-to- $n$ plus true-remaining-from- $n$ , along the optimal path, is exactly the optimal total.

WHY the tool "admissibility" and not something else? We needed to turn a guess $h (n)$ into a fact we can compare with $C^{*}$ . The only bridge from guess to truth is the promise " $h$ never exceeds $h^{*}$ ." That single inequality is precisely what lets us replace $h (n)$ by $h^{*} (n)$ and collapse to $C^{*}$ .

PICTURE. The bar chart stacks $g (n)$ (cyan) and $h (n)$ (amber); a dashed line marks $C^{*}$ . The amber part is capped at $h^{*} (n)$ — it can only sit below the true remaining cost, so the whole bar stays at or under $C^{*}$ .

Step 5 — The impostor's $f$ is strictly larger

WHAT. For any goal node, the remaining trip is zero, so $h (G_{2}) = 0$ . Therefore

$f (G_{2}) = g (G_{2}) + = 0 h (G_{2}) = g (G_{2}) > C^{*} .$

$h (G_{2}) = 0$ — you are already at the goal; nothing remains to estimate.
$g (G_{2}) > C^{*}$ — this is our Step 2 assumption.

Chaining Step 4 and Step 5:

$f (n) \leq C^{*} < f (G_{2}) .$

WHY. Now both key nodes are expressed as pure $f$ -values on the same scale. A* only ever cares about $f$ , so we have set up a direct comparison.

PICTURE. Two stacked bars side by side: the champion $n$ (short, $\leq C^{*}$ ) and the impostor $G_{2}$ (tall, $> C^{*}$ ). The dashed $C^{*}$ line sits cleanly between them.

Step 6 — The contradiction: A* pops the smaller $f$ first

WHAT. A* is defined to pop the smallest $f$ on the frontier. Since $f (n) < f (G_{2})$ and both are on the open list, A* must pop $n$ before it ever reaches $G_{2}$ . So A* cannot pop the suboptimal $G_{2}$ first. Contradiction with Step 2. ∎

WHY it matters. The disaster was impossible. Therefore the first goal A* removes from the queue is optimal. Admissibility is not a nice-to-have — it is exactly the hinge that makes this contradiction fire.

PICTURE. A min-heap (see Priority Queue / Min-Heap) with $n$ at the top (smallest $f$ ) and $G_{2}$ buried below. The pop-arrow grabs $n$ first.

Step 7 — Degenerate case: what if $h = 0$ everywhere?

WHAT. Set the guess to zero for every node. Then $f (n) = g (n) + 0 = g (n)$ .

WHY show it. A reader must never meet a case we skipped. Because $h^{*} (n) \geq 0$ (Step 0's non-negative-cost assumption), the choice $h = 0$ satisfies $0 \leq 0 \leq h^{*} (n)$ , so it is admissible — the whole proof above still holds. A* is still optimal; it has simply lost its sense of direction and expands outward evenly. That is precisely Dijkstra's Algorithm. (Note how the non-negativity of $h^{*}$ is exactly what makes $0 \leq h^{*}$ true here — without it, this case would not go through.)

PICTURE. Two frontiers overlaid: a fat circular ripple ( $h = 0$ , Dijkstra) versus a narrow cone ( $h =$ good guess) both reaching $G$ . Same shortest answer, wildly different amount of exploration.

Step 8 — Degenerate case: what if $h$ lies (inadmissible)?

WHAT. Now let $h$ overpromise: $h (A) > h^{*} (A)$ for some node. Take the parent's Example 2. Path $S \to A \to G$ costs $1 + 1 = 2$ (the true optimum). A direct edge $S \to G$ costs $2.5$ . Set the bad guess $h (A) = 5$ while the truth is $h^{*} (A) = 1$ .

$f (A) = g (A) + h (A) = 1 + 5 = 6, f (G_{direct}) = 2.5 + 0 = 2.5.$

Because $6 > 2.5$ , A* pops the direct goal first and returns 2.5 — missing the true optimum 2.

WHY. This shows where Step 4 fails: the line " $h (n) \leq h^{*} (n)$ " is gone, so we can no longer squeeze $f (n)$ below $C^{*}$ . The champion $A$ now looks expensive and gets buried. Overestimation is not a small sin — it silently breaks optimality. (If you want speed and can tolerate a bounded error, that is the deliberate trade of Weighted A* and Bounded Suboptimality.)

PICTURE. The bad- $h$ bar for $A$ towers over the $C^{*}$ line — its amber ( $h = 5$ ) has smashed through the cap $h^{*} = 1$ . Beside it, the cheaper-looking direct goal wins the pop.

The one-picture summary

WHAT. One figure compresses the entire argument: the amber frontier, the cyan optimal path piercing it at champion $n$ , the two stacked-bar $f$ -values with the $C^{*}$ dashed line separating $n$ (safe) from $G_{2}$ (too tall), and the min-heap popping $n$ first. Admissibility is the single arrow labelled " $h \leq h^{*}$ " that keeps the champion's bar under the line.

Recall Feynman retelling of the whole walkthrough

You're in a maze, walking from $S$ to the exit $G$ . At every step you look at the ring of places you've reached but not yet explored — that's the amber frontier — and you always go poke at the place whose guessed total trip (steps already walked plus peek-to-exit) is smallest.

Now here's the trick. The real shortest path out of the maze must cross that amber ring somewhere — call that spot $n$ . Since your peek at $n$ never overpromises, your guessed total there is never more than the real shortest length $C^{*}$ . Meanwhile any bad exit you might stumble on early costs more than $C^{*}$ , and once you're standing on an exit your peek is zero, so its total is just its (too-big) walked cost. So the good spot $n$ always has a smaller number than the bad exit — and since you always grab the smallest number first, you can never grab a bad exit before walking through $n$ toward the real one.

That's the whole magic: as long as your peek never overpromises (and never claims less than zero), the first exit you reach is the shortest one. Peek zero everywhere → you're Dijkstra, still correct, just slow. Peek that lies too rosy → the guarantee shatters and you can walk out a longer way without noticing.

Prerequisite threads actually used here: Heuristic Functions (what $h$ is), Priority Queue / Min-Heap (how "pop the smallest $f$ " is implemented), Dijkstra's Algorithm (the $h = 0$ special case), and Greedy Best-First Search (the $g$ -ignored contrast). The stronger consistency property, and its link to the Triangle Inequality and Bellman Optimality, is not needed for this optimality proof — it governs the separate "no re-expansion" guarantee handled in the parent note and in GNC Path Planning.