Informed search and heuristics
Ask a phone for directions across a city and it does not blindly flood every street in all
directions until one path happens to reach your destination. It leans toward the goal: it
prefers roads that head roughly the right way, and only doubles back when it has to. That single
instinct — "this looks closer, try it first" — is the difference between uninformed
search, which knows nothing about where the goal is, and informed search, which is
given a hint.
The hint has a name: a heuristic function h(n), an
estimate of the cost still remaining from a node n to the goal.
It is a guess, not a measurement — cheap to compute, and usually wrong by a little — but a good guess
transforms search from a blind sweep into a focused beeline. This page is about that one idea: how a
heuristic guides search, and what property a heuristic needs so that the guidance never costs us the
best answer.
You have already met uninformed
search (which expands nodes with no sense of direction), the mechanics of
A* search, and the
priority queue that
every informed search leans on to always pull out the "most promising" node next. Here we focus on
the theory of the heuristic itself.
Greedy best-first: chase the estimate
The simplest way to use a heuristic is to trust it completely. Greedy best-first
search keeps a priority queue of frontier nodes ordered by h(n)
alone, and always expands the node that looks closest to the goal. Nothing else — not how
far you have already travelled — enters the decision.
On the grid below, the goal sits in the top-right and the number written in each cell is its
heuristic estimate: the Manhattan distance to the goal,
h = |\Delta x| + |\Delta y| (how many horizontal plus vertical steps a
rook would take on an empty board). Greedy search simply rolls "downhill" on these numbers.
Greedy best-first is often blisteringly fast — it charges straight at the goal. But it is
not optimal, and it is easy to fool: because it ignores the distance already
travelled, it will happily dive down a corridor that looks close but is actually a long
detour behind a wall, committing to a bad route just because the estimate briefly dipped. To fix
that, we must stop ignoring the past.
A*: balance the past against the future
A* search makes one change with enormous consequences: it orders the frontier not by
the estimate to come, but by the whole journey — the cost already paid plus the cost still
estimated to remain.
A* expands the frontier node with the smallest value of
- f(n) = g(n) + h(n)
- g(n) — the cost so far: the actual cost of the best
path found from the start to n;
- h(n) — the cost to go: the heuristic estimate of the
cheapest path from n onward to the goal;
- so f(n) estimates the total cost of the cheapest solution that is
forced to pass through n.
That extra g(n) term is what stops A* being fooled: a node down a scenic
detour may have a tempting small h, but its g
has grown large, so its f is honest about the total. Two special cases
pin down the spectrum: drop the past and keep only h and you are back to
greedy best-first; drop the future and keep only g and you have
uniform-cost search, the uninformed algorithm that expands by cheapest-cost-so-far. A* sits
between them, using both halves.
Admissibility: the promise that buys optimality
A* is only as trustworthy as its heuristic. The crucial property is admissibility:
the heuristic is allowed to be optimistic, but never pessimistic. It may guess that the goal is
closer than it is, but it must never claim the goal is farther than it truly is.
- A heuristic h is admissible if for every node
h(n) \le h^{*}(n), where h^{*}(n) is the
true cheapest cost from n to the goal — it never
overestimates.
- With an admissible heuristic, A* tree search returns an optimal solution: the
first goal it removes from the frontier is guaranteed to be a cheapest path.
The intuition is short. Because h never overestimates,
f(n) = g(n) + h(n) never overestimates the true cost of the best solution
through n. So A* will never settle on a costly goal while a cheaper path is
still sitting on the frontier with a smaller f — that cheaper path always
gets pulled out and finished first. Manhattan distance on a grid is admissible: ignoring walls, you
genuinely cannot reach the goal in fewer than |\Delta x| + |\Delta y|
four-way steps, so the estimate can only ever be too small, never too big.
Consistency: admissibility's stronger cousin
Real implementations do not use pure tree search — they keep an explored set (a
"closed list") so they never re-expand a node. That optimisation can quietly break admissible A*
unless the heuristic satisfies a stronger condition: consistency (also called
monotonicity).
- A heuristic is consistent if for every node
n and every successor n' reached by an
action of cost c(n, n'),
h(n) \le c(n, n') + h(n').
- This is a triangle inequality: the estimate from n is no bigger than
the step to n' plus the estimate from n'.
- Consistency implies admissibility, and it guarantees A* stays optimal even
with graph search and an explored set — because f
never decreases along a path, so a node is never reached later by a cheaper route after it has
been expanded.
Most natural heuristics — Manhattan distance, straight-line distance — are consistent, so in practice
the two conditions usually arrive together. But they are not identical: every consistent heuristic is
admissible, yet a contrived admissible heuristic can fail consistency, and then graph-search A* may
need to re-open closed nodes to stay optimal.
Choosing a heuristic: dominance
On a grid you have a choice of admissible heuristics. For four-way movement, two classics are:
- Manhattan distance, h = |\Delta x| + |\Delta y| —
the number of horizontal plus vertical steps.
- Straight-line (Euclidean) distance,
h = \sqrt{\Delta x^{2} + \Delta y^{2}} — the crow-flies distance.
Both are admissible, but they are not equally good. Between two admissible heuristics, the
one that returns larger values (while staying admissible) is said to
dominate — and a dominant heuristic expands fewer nodes, because
its bigger, more accurate estimates prune more of the frontier. For four-way grid movement Manhattan
distance dominates straight-line distance (it is always at least as large, yet still never
overestimates), so it is the better choice.
Here is a compact A* on our little grid. It orders the frontier by f = g + h
using Manhattan h, finds a shortest path around the wall, and prints it.
Change the walls or the goal and re-run.
type Cell = { c: number; r: number };
const COLS = 6, ROWS = 5;
const walls = new Set(["3,1", "3,2", "3,3"]); // a vertical wall
const start: Cell = { c: 0, r: 0 };
const goal: Cell = { c: 5, r: 4 };
const key = (c: number, r: number) => c + "," + r;
const h = (c: number, r: number) => Math.abs(c - goal.c) + Math.abs(r - goal.r); // Manhattan
const g = new Map<string, number>([[key(start.c, start.r), 0]]);
const cameFrom = new Map<string, string>();
const open: Cell[] = [{ c: start.c, r: start.r }];
while (open.length > 0) {
// pull the frontier cell with the smallest f = g + h (the priority queue)
open.sort((a, b) => (g.get(key(a.c, a.r))! + h(a.c, a.r)) - (g.get(key(b.c, b.r))! + h(b.c, b.r)));
const cur = open.shift()!;
if (cur.c === goal.c && cur.r === goal.r) break;
const gc = g.get(key(cur.c, cur.r))!;
for (const [dc, dr] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nc = cur.c + dc, nr = cur.r + dr;
if (nc < 0 || nr < 0 || nc >= COLS || nr >= ROWS) continue; // off the board
if (walls.has(key(nc, nr))) continue; // blocked
const ng = gc + 1; // every step costs 1
const known = g.has(key(nc, nr)) ? g.get(key(nc, nr))! : Infinity;
if (ng < known) {
g.set(key(nc, nr), ng);
cameFrom.set(key(nc, nr), key(cur.c, cur.r));
open.push({ c: nc, r: nr });
}
}
}
const path: string[] = [];
let at: string | undefined = key(goal.c, goal.r);
while (at) { path.unshift(at); at = cameFrom.get(at); }
console.log("path:", path.join(" -> "));
console.log("cost:", g.get(key(goal.c, goal.r)), "steps");
It is tempting to think "a heuristic is just a hint, so a slightly aggressive one that
overestimates a bit will only push A* toward the goal faster." That reasoning quietly
throws away the one guarantee that makes A* worth using. An inadmissible heuristic
— one that ever claims the goal is farther than it truly is — can make A* return a
sub-optimal path: the algorithm may inflate the f of the
true best route so much that it never bothers to finish it, and commits to a worse goal instead.
Admissibility is exactly what buys optimality; give it up and you keep the speed
but lose the promise. And do not confuse A* with greedy best-first: greedy search ignores
g(n) entirely, so it is never optimal even with a perfect
admissible heuristic. Optimality comes from combining an admissible h
with the honest g — not from either half alone.
The two ends of the dial are illuminating. Set h(n) = 0 everywhere: it is
trivially admissible (zero never overestimates), and f = g + 0 = g, so
A* degenerates into uniform-cost search — correct and optimal, but uninformed, with
no pull toward the goal, exploring in all directions.
Now set the perfect heuristic h(n) = h^{*}(n), the exact true
cost-to-go. Then A* walks straight to the goal, expanding only nodes on an optimal path — no wasted
work at all. Real heuristics live between these extremes, and the whole art is buying accuracy
cheaply. A standard trick is a relaxed problem: solve an easier version exactly and
use its cost as the estimate. Manhattan distance is such a relaxation — it is the true cost
on a grid with all the walls removed, which is why it is admissible and quick to compute.