A* Search

1The algorithm

A* keeps a frontier ordered by f(n) = g(n) + h(n): g is the cheapest cost found so far from the start to n, h is the heuristic's estimate of what remains, so f is an optimistic forecast of the best total cost of any solution passing through n. The loop is short — pop the smallest f, stop if it is a goal, otherwise expand it: compute each successor's g, and insert or update it on the frontier.

The forecast is what buys focus. A node reached cheaply but pointing away from the goal carries a small g and a large h, and its f sinks it down the queue: in the animation, the decoy D is generated at f = 2 + 12 = 14 and simply never expanded while the real contenders open at 11. Strip h away and that focus vanishes — with h = 0 everywhere, A* is uniform-cost search.

An implementation is a binary heap keyed by f, a table of the best g known per node, and parent pointers to rebuild the path at the end. Time is dominated by heap operations, but the binding constraint in practice is memory: the frontier of a hard instance can approach the size of the reachable graph, which is why memory-bounded variants such as IDA* exist.

Coding lab. Implement A* on the lesson graph runs in the app, with checks on your output.

2Goal-test on pop, not on generation

There are two moments an implementation can ask whether a node is the goal: when it is first generated as a successor, or when it is popped off the frontier. Correct A* tests when it is popped, not when it is generated — and the difference is not pedantry, it is the optimality guarantee.

At generation time a node carries whatever g the discovering route happened to have; nothing certifies that route as the cheapest. Only when the node's f is the smallest thing on the frontier is the certificate issued — that is the moment the stopping argument applies. Dijkstra's algorithm has exactly the same rule, and porting it wrongly is the single most common A* implementation bug.

The lesson graph fails loudly under the wrong test: the direct S→G edge generates the goal during the very first expansion, at cost 10. Accept it there and the search never learns that S→B→G finishes at 8.

Figure. Expanding S generates G on the direct edge at g = 10. Accept the goal at generation and the search returns 10. Test at pop and B pops first; G via B waits, then pops at 8 — S→B→G.

Where the certificate comes from

1. GeneratedA successor arrives carrying the g of whichever route found it — possibly a poor one.
2. WaitingOn the frontier its f competes; cheaper routes into the same node may still replace its g.
3. PoppedSmallest f anywhere: no waiting path can undercut it, so the goal test is now safe.

3What g and h each buy you

The two terms of f audit different things. g is the meter: cost actually paid from the start, so no forecast can hide a dear route already taken. h is the compass: where the remaining cost probably lies, so effort bends toward the goal instead of flooding outward evenly.

Delete either term and the algorithm degenerates into something with its own name. Setting h = 0 leaves f = g, which is uniform-cost search — still optimal, completely blind, expansion counts balloon. Dropping g leaves f = h, which is greedy best-first search — fast when the compass is good and unprotected when it lies, as the next concept demonstrates.

Between the poles lies a dial rather than a switch. Weighted A* ranks by f(n) = g(n) + w \cdot h(n) with w > 1, deliberately over-trusting the compass: it expands fewer nodes and returns a path guaranteed to cost at most w times the optimum when h is admissible. Production planners run it with w chosen on purpose; the defect is only ever in turning the dial without knowing.

Figure. The frontier the moment S is expanded, each bar an f-value: paid cost stacked under forecast remainder. Reading g alone chases 'via A' (2 paid); reading h alone pops the direct goal (0 left) and returns the dear 10; only the sum — shortest overall bar, via B at 8 — is protected in general.

4Greedy best-first, and when it fails

Greedy best-first search ranks the frontier by h alone: always expand whatever looks nearest the goal. It follows the compass and never reads the meter, so cost already sunk into a path counts for nothing.

That is exploitable by construction. Give S two roads: through X, costing 2 then 2, and through Y, costing 1 and then a 20-cost cliff. Set h(X) = 2 and h(Y) = 1 — both admissible, since the true remainders are 2 and 20. Greedy compares 1 against 2, dives through Y, meets the goal and returns a cost-21 path. The admissibility of both estimates protected nothing, because greedy never asks what has been paid.

A* on the same instance also tries Y first — f(Y) = 2 beats f(X) = 4 — but the cliff surfaces in g: the goal via Y waits at f = 21 while X pops at 4 and delivers the goal at f = 4. Optimism misleads both algorithms for a step; only the one carrying g recovers. Greedy earns its keep where h is excellent and any path will do — and in interviews, as the standard demonstration that an admissible heuristic does not make every search optimal.

Figure. The upper road through X costs 4 in total; the lower road through Y looks nearer (h = 1 against 2) and hides a 20-cost edge behind its first cheap step. Ranking by h alone commits to Y and never revisits the choice; carrying g lets the 20 surface before an answer is returned.

5Why the first goal pop is optimal

The theorem, stated the way an exam wants it: tree-search A* with an admissible heuristic is cost-optimal; graph-search A* is cost-optimal when the heuristic is consistent, or when inconsistency is repaired by reopening. Write C^* for the cost of an optimal solution.

The argument has two halves. First, some prefix of an optimal path is always sitting on the frontier, and admissibility keeps that entry's f at or below C^* — the estimate never overstates what the rest of that optimal path costs. Second, A* pops lowest f, and at a goal h is zero, so a popped goal's f equals the genuine cost of the path being returned. Pop a goal dearer than C^* and the two halves collide: the optimal prefix, waiting at f at most C^*, was strictly cheaper and would have popped first.

Each hypothesis is load-bearing, and the neighbouring lessons are what happens when one is removed. Overestimating h buries the optimal prefix behind an inflated f — the bad-heuristics concept runs those numbers. Inconsistency in graph search lets a node settle on a stale g — the reopening concept. And testing the goal at generation reads f before the certificate exists. The proof is short precisely because the definitions were built to make it short.

Figure. At the instant a goal reaches the front, its f is the fully-paid path cost (h = 0). A prefix of an optimal path is still waiting with f ≤ C* by admissibility. A goal popping above C* would mean that cheaper prefix was passed over — impossible under lowest-f-first.

The stopping argument, in order

1. Prefix on frontierSome node of an optimal path is always waiting, with f ≤ C* by admissibility.
2. Goal pops honestAt a goal h = 0, so its f is the true, fully-paid cost of the path about to be returned.
3. ContradictionA goal popping above C* would mean the cheaper optimal prefix was passed over — impossible under lowest-f-first.