A* Search

Last lesson left us holding the honest estimate h(n) and a choice of how to use it — and it warned that greedy best-first, which grabs whichever node merely looks closest, charges blindly down short-looking corridors that dead-end. The fix was named there too: weigh what you have already spent against what you estimate is left. A* is the small idea that does exactly that — at every step, expand the node whose total estimated path cost (cost paid so far, plus the heuristic’s guess of cost remaining) is smallest.

Think of it as planning a drive: the worth of a route-in-progress is the miles already driven plus the miles your GPS says remain, and you always extend the route with the smallest such total. Uniform-cost search used only the first half (the miles driven, ignoring the goal); greedy used only the second (the miles remaining, ignoring how far you have come). A* adds them, and that one sum is why it is the textbook search algorithm: with an admissible heuristic it still returns the cheapest path, yet usually expands far fewer nodes than UCS. The same f = g + h rule plans the shortest drive in a maps app and the path a game character walks across a map.

The evaluation function

• g(n) — actual cost of the cheapest path found so far from start to n.
• h(n) — heuristic estimate of cost from n to the nearest goal.
• f(n) — the priority key. Expand the smallest f from the frontier.

The two heuristic properties from last lesson decide A*‘s guarantees:

• Admissible — h(n) never overestimates the true cost (h(n) <= h*(n)). With an admissible h, A* is optimal: the first goal it pops lies on the cheapest path.
• Consistent (monotonic) — for every edge n -> n' with cost c, h(n) <= c + h(n'). Consistency implies admissibility and guarantees every node is expanded at most once.

A small graph to expand

Five nodes, a few weighted edges, one start S and one goal G. Each node carries its heuristic value; we will walk the frontier step by step.

How GATE asks this

A real NAT/MCQ pattern: a tiny weighted graph with heuristic values printed on each node, and “List the order in which A* expands nodes” or “What is the f-value when node X is expanded?”. Standing convention: alphabetical tie-break when two frontier nodes share the lowest f. This pattern appeared in both GATE DA 2024 and 2025.

Worked example — tracing the expansion order

Using the graph above (start S, goal G), list the order A* expands nodes and the cost of the path it returns.

Initialise the frontier with S.

Step 1. Frontier: {S(g=0, f=0+4=4)}. Expand S and push its neighbours:

• A via S: g = 0 + 1 = 1, f = 1 + 3 = 4
• B via S: g = 0 + 2 = 2, f = 2 + 1 = 3

Frontier: {A(f=4), B(f=3)}.

Step 2. Lowest f is B (f = 3). Expand B and push G via B:

• G via B: g = 2 + 3 = 5, f = 5 + 0 = 5

Frontier: {A(f=4), G(f=5)}.

Step 3. Lowest f is A (f = 4). Expand A and push G via A:

• G via A: g = 1 + 5 = 6, f = 6 + 0 = 6

But G is already on the frontier with g = 5, which is cheaper — so the new path through A is worse and is discarded. Frontier: {G(f=5)}.

Step 4. Pop G — goal reached on the path S -> B -> G with total cost 5.

So the expansion order is S, B, A, G, the optimal path cost is 5, and it matches the f-value of G when it was popped. Notice B was expanded before A even though A sat closer in g — A* trusted B’s smaller total f, exactly the balance the prediction prompt invited you to spot.

In one breath

A* fuses uniform-cost and greedy search by expanding, from a priority queue, the node with the smallest f(n) = g(n) + h(n) — the known cost-so-far g plus the estimated cost-to-go h — so it is optimal whenever h is admissible (the first goal popped lies on a cheapest path) and never re-expands a node when h is consistent; h = 0 collapses it to UCS, and on ties you break alphabetically by GATE convention.

Practice

A question to carry forward

Every search in this chapter so far — blind or informed, BFS through A* — shared one quiet assumption: there is exactly one mover, you, against a world that holds still. The maze does not rearrange its walls to thwart you; the road network does not lengthen an edge the moment you choose it. You plan a path, and the path stays put.

Now sit down across a chessboard. After every move you make, a second player makes the move that hurts you most. There is no fixed path to find any more, because the future depends on choices that are not yours — and an opponent who is, by assumption, just as clever as you. The whole “cheapest path to a goal” frame collapses. Here is the thread onward: how do you reason about your best move when someone is actively trying to defeat you — how do you plan for the worst reply to every plan, and read off the best you can guarantee against a perfect adversary?