Informed Search and A*

An uninformed search knows only the problem definition: the start state, the actions, the goal test, and the step costs. It cannot tell a promising node from a hopeless one, so it expands the frontier by a fixed rule — shallowest first, cheapest-path first — and pays for that ignorance in nodes expanded. An informed search brings in problem-specific knowledge beyond the definition itself, and uses it to expand fewer nodes on the way to a solution.¹

The knowledge arrives as a single number attached to each node.

For route-finding across Romania, the natural heuristic is the straight-line distance $h_{SLD}(n)$ from a city to the destination: it is easy to compute, it correlates with actual road distance, and it can never exceed it because a straight line is the shortest path between two points. Notice what the definition does not require — $h_{SLD}$ cannot be read off the problem statement (you need a map with coordinates), and knowing that it is useful takes a little experience. That is the whole point: the heuristic is the channel through which extra knowledge enters the search.

This lesson develops the two informed strategies and proves the guarantees of the central one, A*. It leaves open the practical question of where good heuristics come from — relaxed problems, pattern databases, dominance — which is the subject of the companion lesson, Heuristic Functions and Memory-Bounded Search.

Best-first search

Both strategies in this lesson are instances of one scheme, best-first search: keep the frontier in a priority queue and always expand the node with the lowest value of an evaluation function $f(n)$, which we read as a cost estimate — small $f$ means promising. Underneath, this reuses the priority-queue graph search that uniform-cost search uses, with $f$ substituted for $g$ to order the queue. Everything below comes down to one choice: what is $f$?

Greedy best-first search

The most direct use of a heuristic is to trust it completely. Greedy best-first search expands the node that looks closest to the goal, ranking the frontier by the heuristic alone:

On the Romania map with $h_{SLD}$ and Bucharest as the goal, greedy search starting from Arad expands Sibiu first (closest of Arad's neighbours to Bucharest), then Fagaras (closest of Sibiu's), and Fagaras generates Bucharest. It reaches the goal having expanded only nodes on a single downhill run toward it — the search cost is minimal.²

But the path it returns, Arad–Sibiu–Fagaras–Bucharest, is $32$ km longer than the route through Rimnicu Vilcea and Pitesti. Greedy search is not optimal. The name is the diagnosis: at each step it grabs the node that gets closest to the goal right now, with no accounting for the cost already accumulated on the path. A short first hop toward the goal that commits you to a long detour later is invisible to a function that ignores $g$.

Greedy tree search is also incomplete, in the same way depth-first search is. Getting from Iasi to Fagaras, the heuristic points first at Neamt (closest to Fagaras), which is a dead end; the true first move is to Vaslui, a step that is farther from the goal by the heuristic. A greedy tree search that keeps re-expanding Neamt (returned to the frontier each time Iasi is reached) loops forever. The graph-search version, which refuses to re-expand a state, is complete in finite spaces but not in infinite ones. Worst-case time and space for the tree version are $O(b^m)$ with $m$ the maximum depth, though a good heuristic cuts this sharply in practice.

A* search

A* search fixes greedy search's blind spot by adding back the cost already paid. It evaluates a node by combining $g(n)$, the cost to reach $n$, with $h(n)$, the estimated cost to get from $n$ to the goal:

Since $g(n)$ is the actual path cost from the start to $n$ and $h(n)$ estimates the remaining cost, $f(n)$ estimates the cost of the cheapest solution that passes through $n$. Ranking the frontier by $f$ therefore expands, at each step, the node that lies on the currently most promising complete path. This is more than a sensible heuristic: provided $h$ meets a mild condition, A* is both complete and optimal. The algorithm is identical to uniform-cost search except that it orders the queue by $g+h$ rather than $g$ alone — and uniform-cost search is just the special case $h(n)=0$, in which A* has no heuristic guidance and reduces to Dijkstra's shortest-path expansion.³

Admissibility: optimality for tree search

The condition A* needs for tree search is that $h$ be admissible.

Admissible heuristics are optimistic by nature: they always think the goal is at least as close as it really is. Because $g(n)$ is the exact cost along the current path and $f(n)=g(n)+h(n)$, an admissible $h$ makes $f(n)$ a lower bound on the true cost of any solution through $n$. Straight-line distance is admissible for exactly this reason — no road is shorter than the straight line, so $h_{SLD}$ can never overshoot.

Here is the argument that admissibility gives optimality for tree search. Suppose a suboptimal goal node $G_2$, with cost $g(G_2)=f(G_2)>C^{\ast }$, sits on the frontier alongside a node $n$ that lies on an optimal path to the true goal $G$, with optimal cost $C^{\ast }$. Then

using admissibility for the first inequality. So $n$ has strictly smaller $f$ than $G_2$, and A* expands $n$ before it would ever select $G_2$. Every node on the optimal path is expanded ahead of any suboptimal goal, so the first goal A* removes from the frontier must be an optimal one.

A traced A* expansion

The figure names the $f$-values; the trace shows how the priority queue produces them. Take the Bucharest search from Arad with $h_{SLD}$, whose values (in km, straight-line to Bucharest) are $h(\text{Arad})=366$, $h(\text{Sibiu})=253$, $h(\text{Timisoara})=329$, $h(\text{Zerind})=374$, $h(\text{Fagaras})=176$, $h(\text{Rimnicu})=193$, $h(\text{Oradea})=380$, $h(\text{Pitesti})=100$, and $h(\text{Bucharest})=0$. Each row selects the lowest-$f$ frontier node and lists what it generates with $g$, $h$, and $f=g+h$.

The decisive rows are $4$ and $5$. In step $4$ a Bucharest node appears at $f=450$ (reached via Fagaras), but A* does not stop: Pitesti at $f=417$ is smaller and sits ahead of it in the queue. Expanding Pitesti in step $5$ generates a second Bucharest node at $f=418$, cheaper than the first, and it jumps to the front. Only in step $6$, when Bucharest at $418$ is selected, does A* return — Arad-Sibiu-Rimnicu-Pitesti-Bucharest, cost $418$. The suboptimal $450$ goal sat on the frontier the whole time and was never selected, exactly as the admissibility argument promised: $f(\text{Pitesti})=417<450=f(G_2)$, so the node on the optimal path is expanded first. Note also Timisoara at $447$ and Zerind at $449$: both have $f>C^{\ast }=418$, so A* never expands either — that is pruning in action.

Consistency: optimality for graph search

For graph search, where we discard repeated states, admissibility alone is not quite enough; A* needs the slightly stronger property of consistency (also called monotonicity).

This is a form of the triangle inequality: the side from $n$ to the goal cannot exceed the sum of the other two sides, $n\to n^{\prime }$ and $n^{\prime }\to \text{goal}$. Every consistent heuristic is admissible (take a whole path of steps and the inequalities telescope to $h(n)\le h^{\ast }(n)$), though the converse can fail; still, essentially every admissible heuristic one meets in practice is also consistent, $h_{SLD}$ included.

Consistency buys the key structural fact: $f$ is nondecreasing along any path. If $n^{\prime }$ is a successor of $n$, then $g(n^{\prime })=g(n)+c(n,a,n^{\prime })$, so

with the inequality from consistency. So the sequence of nodes A* expands has nondecreasing $f$. Combined with the graph-search rule that the first time we expand a state we have already found the cheapest path to it, this makes the first goal node A* selects an optimal solution: goal nodes have $h=0$, so their $f$ equals their true cost, and any later goal is at least as expensive.

The contour picture

Nondecreasing $f$ lets us picture A* geometrically. Because $f$ never drops along a path, we can draw contours in the state space, exactly like the level curves of a topographic map: the region $f(n)\le 400$ forms one band, $f(n)\le 420$ a larger band containing it, and so on. A* expands the frontier in concentric bands of increasing $f$-cost, fanning outward from the start.

Let $C^{\ast }$ be the cost of the optimal solution. The contour picture makes two facts immediate:

• A* expands every node with $f(n)<C^{\ast }$.
• A* expands no node with $f(n)>C^{\ast }$; it may expand some nodes right on the goal contour $f(n)=C^{\ast }$ before selecting a goal.

The second fact is pruning: A* safely ignores whole subtrees whose $f$ exceeds $C^{\ast }$ (Timisoara, a child of Arad in the Bucharest search, is never expanded) without any risk to optimality. With uniform-cost search the bands are circular around the start; a more accurate heuristic stretches them toward the goal and narrows them onto the optimal path — that narrowing is precisely the work the heuristic does. Among all algorithms of this kind that use the same heuristic, A* is optimally efficient: no such algorithm is guaranteed to expand fewer nodes, because any algorithm that skips a node with $f<C^{\ast }$ risks missing the optimal solution.

The catch is memory. Like every graph search, A* keeps all generated nodes, and for hard problems the number of nodes on the goal contour is still exponential in the solution length. A* usually exhausts memory long before it runs out of time.

A* is only as good as its heuristic — the narrower those contours, the less work it does — which raises the question its optimality proof left open: where does a good $h$ come from, and what do you do when even A*'s memory bill is too high? This continues in Heuristic Functions and Memory-Bounded Search.