---
title: Informed Search and A*
module: Search
moduleNumber: 2
lessonNumber: 3
order: 203
summary: >
  An informed search uses a heuristic $h(n)$, an estimate of the cost from a node
  to the goal, to decide what to expand next. Greedy best-first search follows the
  heuristic blindly and gives up optimality; A* corrects it by ranking nodes on
  $f(n) = g(n) + h(n)$, and is optimal when the heuristic is admissible (tree
  search) or consistent (graph search). This lesson defines the heuristic, builds
  best-first search, and proves why A* is optimal, with the contour picture that
  explains its pruning. Where good heuristics come from is the next lesson.
topics: [Search]
sources:
  - book: AIMA
    ref: "Ch. 3 — Solving Problems by Searching; §3.5 Informed (Heuristic) Search Strategies"
---

An [uninformed search](/artificial-intelligence/search/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.[^informed]

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

> **Definition (Heuristic function).** A function $h(n)$ that estimates the cost of
> the cheapest path from the state at node $n$ to a goal state. It is
> problem-specific, nonnegative, and satisfies $h(n) = 0$ whenever $n$ is a goal.
> Unlike the path cost $g(n)$, $h(n)$ depends only on the _state_ at $n$, not on
> how the search reached it.

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](/artificial-intelligence/search/heuristic-functions).

## 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](/artificial-intelligence/search/uninformed-search) uses,
with $f$ substituted for $g$ to order the queue. Everything below comes down to one
choice: what is $f$?

$$
% caption: Best-first search orders the frontier by an evaluation function $f(n)$.
% Greedy search sets $f = h$; A* sets $f = g + h$; uniform-cost search is the case
% $h = 0$.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=30mm, minimum height=11mm, align=center, font=\footnotesize},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (bf) at (0,0) {best-f\/irst search\\(order f\/rontier by f)};
  \node[box] (uc) at (-4.2,-2.6) {uniform-cost\\f = g};
  \node[box] (gr) at (0,-2.6)    {greedy\\f = h};
  \node[box] (as) at (4.2,-2.6)  {A-star\\f = g + h};
  \draw[->, black] (bf) -- (uc);
  \draw[->, black] (bf) -- (gr);
  \draw[->, acc, thick] (bf) -- (as);
  \node[lbl, anchor=north] at (-4.2,-3.35) {ignores the goal};
  \node[lbl, anchor=north] at (0,-3.35) {ignores cost so far};
  \node[lbl, anchor=north, text=acc] at (4.2,-3.35) {balances both};
\end{tikzpicture}
$$

## 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:

$$
f(n) = h(n).
$$

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.[^greedy]

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$.

$$
% caption: Greedy search chases the smallest $h$ and takes Arad-Sibiu-Fagaras
% (h drops 366, 253, 176, 0), a route 32 km longer than the optimal
% Arad-Sibiu-Rimnicu-Pitesti path it never considers.
\begin{tikzpicture}[>=stealth, font=\small,
  city/.style={draw, ellipse, minimum width=17mm, minimum height=7mm, font=\footnotesize, inner sep=1pt},
  hlbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[city] (a) at (0,0)      {Arad};
  \node[city, draw=acc, text=acc] (s) at (3,0)      {Sibiu};
  \node[city, draw=acc, text=acc] (f) at (6,0.9)    {Fagaras};
  \node[city] (r) at (6,-0.9)   {Rimnicu};
  \node[city] (p) at (9,-0.9)   {Pitesti};
  \node[city, draw=acc, text=acc] (b) at (9.4,0.6)  {Bucharest};
  \draw[->, acc, thick] (a) -- (s);
  \draw[->, acc, thick] (s) -- (f);
  \draw[->, acc, thick] (f) -- (b);
  \draw[->, red, thick, dashed] (s) -- (r);
  \draw[->, red, thick, dashed] (r) -- (p);
  \draw[->, red, thick, dashed] (p) -- (b);
  \node[hlbl] at (0,-0.75)   {h=366};
  \node[hlbl, text=acc] at (3,-0.75)   {h=253};
  \node[hlbl, text=acc] at (6.6,1.55) {h=176};
  \node[hlbl, text=red] at (5.4,-1.65) {h=193};
  \node[hlbl, text=red] at (9,-1.65)   {h=100};
  \node[font=\scriptsize, text=acc, anchor=west] at (7.4,1.9) {greedy: 450 km};
  \node[font=\scriptsize, text=red, anchor=west] at (7.4,-2.35) {optimal: 418 km};
\end{tikzpicture}
$$

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:

$$
f(n) = g(n) + h(n).
$$

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](/artificial-intelligence/search/uninformed-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.[^astar]

```algorithm
caption: $\textsc{A*-Search}$ — best-first search on $f(n) = g(n) + h(n)$
input: a problem with start state $s_0$, goal test, step costs $c$, heuristic $h$
$n_0 \gets$ node for $s_0$ with $g(n_0) = 0$
frontier $\gets$ priority queue ordered by $f(n) = g(n) + h(n)$, containing $n_0$
explored $\gets$ empty set
loop do
  if frontier is empty then return failure
  $n \gets$ pop the node with lowest $f$ from frontier
  if $n$ passes the goal test then return the path to $n$
  add state of $n$ to explored
  for each action $a$ available at $n$ do
    $n' \gets$ child of $n$ via $a$, with $g(n') \gets g(n) + c(n, a, n')$
    if state of $n'$ is not in explored and not in frontier then
      add $n'$ to frontier
    else if $n'$ reaches a frontier state at higher $g$ then
      replace that frontier node with $n'$
```

### Admissibility: optimality for tree search

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

> **Definition (Admissible heuristic).** A heuristic $h$ is admissible if
> $h(n) \le h^\ast(n)$ for every node $n$, where $h^\ast(n)$ is the true cheapest cost
> from $n$ to a goal. An admissible heuristic never _overestimates_ the cost to
> reach the goal.

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

$$
f(n) = g(n) + h(n) \le g(n) + h^\ast(n) = C^\ast  < f(G_2),
$$

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.

$$
% caption: A* tree search for Bucharest with $h_{SLD}$. Every node carries
% $f = g + h$. Bucharest first appears on the frontier at $f = 450$ (via Fagaras),
% but Pitesti's $f = 417$ is smaller, so A* expands Pitesti first and finds the
% cheaper route -- it will not settle for the 450 solution.
\begin{tikzpicture}[>=stealth, font=\small,
  city/.style={draw, ellipse, minimum width=16mm, minimum height=6.5mm, font=\scriptsize, inner sep=1pt},
  fl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[city] (a) at (0,0) {Arad};
  \node[city] (s) at (0,-1.7) {Sibiu};
  \node[city] (t) at (3.3,-1.7) {Timisoara};
  \node[city] (z) at (6.3,-1.7) {Zerind};
  \node[city] (f) at (-3.0,-3.4) {Fagaras};
  \node[city] (rv) at (0,-3.4) {Rimnicu};
  \node[city] (o) at (2.7,-3.4) {Oradea};
  \node[city] (p) at (0,-5.1) {Pitesti};
  \node[city, draw=red, text=red] (b1) at (-3.0,-5.1) {Bucharest};
  \node[city, draw=acc, text=acc] (b2) at (0,-6.7) {Bucharest};
  \draw[->] (a) -- (s);  \draw[->] (a) -- (t);  \draw[->] (a) -- (z);
  \draw[->] (s) -- (f);  \draw[->] (s) -- (rv); \draw[->] (s) -- (o);
  \draw[->] (f) -- (b1);
  \draw[->] (rv) -- (p);
  \draw[->, acc, thick] (p) -- (b2);
  \node[fl] at (0,0.55) {366 = 0 + 366};
  \node[fl, anchor=east] at (-0.95,-1.7) {393};
  \node[fl] at (3.3,-2.35) {447};
  \node[fl] at (6.3,-2.35) {449};
  \node[fl, anchor=east] at (-3.85,-3.4) {415};
  \node[fl] at (1.15,-3.4) {413};
  \node[fl] at (2.7,-4.05) {671};
  \node[fl, text=acc] at (1.15,-5.1) {417};
  \node[fl, text=red] at (-3.0,-5.75) {450};
  \node[fl, text=acc] at (0,-7.35) {418 = 418 + 0};
\end{tikzpicture}
$$

### 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$.

| Step | Select ($f$) | Generates: state, $g + h = f$ | Frontier by $f$ |
| --- | --- | --- | --- |
| $1$ | Arad ($366$) | Sibiu $140{+}253{=}393$; Timisoara $118{+}329{=}447$; Zerind $75{+}374{=}449$ | Sibiu $393$, Timisoara $447$, Zerind $449$ |
| $2$ | Sibiu ($393$) | Rimnicu $220{+}193{=}413$; Fagaras $239{+}176{=}415$; Oradea $291{+}380{=}671$ | Rimnicu $413$, Fagaras $415$, Timisoara $447$, Zerind $449$, Oradea $671$ |
| $3$ | Rimnicu ($413$) | Pitesti $317{+}100{=}417$; Craiova $366{+}160{=}526$ | Fagaras $415$, Pitesti $417$, Timisoara $447$, … |
| $4$ | Fagaras ($415$) | Bucharest $450{+}0{=}450$ | Pitesti $417$, Timisoara $447$, Zerind $449$, Bucharest $450$, … |
| $5$ | Pitesti ($417$) | Bucharest $418{+}0{=}418$ | **Bucharest $418$**, Timisoara $447$, Zerind $449$, … |
| $6$ | Bucharest ($418$) | — goal selected | — return |

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**).

> **Definition (Consistent heuristic).** A heuristic $h$ is consistent if, for
> every node $n$ and every successor $n'$ generated by an action $a$,
> $$h(n) \le c(n, a, n') + h(n'),$$
> where $c(n, a, n')$ is the step cost. The estimate at $n$ is no larger than the
> real step to $n'$ plus the estimate from $n'$.

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'$ and $n' \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'$ is a successor of $n$, then $g(n') = g(n) + c(n, a, n')$, so

$$
f(n') = g(n') + h(n') = g(n) + c(n, a, n') + h(n') \ge g(n) + h(n) = f(n),
$$

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.

$$
% caption: A* fans out in contours of increasing $f$-cost from the start (Arad).
% With a perfect heuristic the contours stretch into a narrow corridor along the
% optimal path to the goal (B); with $h = 0$ (uniform-cost search) they are
% circular. A* expands every node with $f < C^*$ and no node with $f > C^*$.
\begin{tikzpicture}[>=stealth, font=\small,
  dot/.style={circle, fill=black, inner sep=1.6pt},
  clbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % contours as nested rotated ellipses, elongated toward the goal
  \foreach \r in {1.1, 1.9, 2.8}
    \draw[black, rotate=-14] (-0.6,0) ellipse ({\r*1.55} and \r);
  % contour value labels above each band's top edge, clear of the node dots below
  \node[clbl, text=black] at (-0.3,1.42)  {f = 380};
  \node[clbl, text=black] at (0.9,2.30)   {f = 400};
  \node[clbl, text=black] at (2.2,3.22)   {f = 420};
  % start and goal
  \node[dot, fill=acc] (start) at (-2.35,0.05) {};
  \node[font=\scriptsize, text=acc, anchor=east] at (-2.5,0.05) {start (Arad)};
  \node[dot, fill=red] (goal) at (4.35,-1.55) {};
  \node[font=\scriptsize, text=red, anchor=west] at (4.5,-1.55) {goal (B)};
  % a few interior nodes on the lower diagonal, spaced off the labels
  \foreach \p in {(-1.3,-0.35),(-0.4,-0.7),(0.6,-1.0),(1.6,-1.25),(2.7,-1.55)}
    \node[dot] at \p {};
\end{tikzpicture}
$$

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](/artificial-intelligence/search/heuristic-functions).

[^informed]: **Russell & Norvig**, _Artificial Intelligence: A Modern Approach_ (3rd ed.), §3.5 — Informed (Heuristic) Search Strategies: best-first search as an instance of the general tree/graph search that orders the frontier by an evaluation function $f(n)$, with the heuristic $h(n)$ as the channel for problem-specific knowledge.
[^greedy]: **Russell & Norvig**, §3.5.1 — Greedy best-first search: $f(n) = h(n)$; efficient but neither optimal (the 32-km-longer Bucharest route) nor complete for tree search (the Iasi–Fagaras loop).
[^astar]: **Russell & Norvig**, §3.5.2 — A* search: $f(n) = g(n) + h(n)$; optimality via admissibility (tree search) and consistency/monotonicity with nondecreasing $f$ and the contour argument (graph search); optimal efficiency and the memory drawback.