---
title: Heuristic Functions and Memory-Bounded Search
module: Search
moduleNumber: 2
lessonNumber: 4
order: 204
summary: >
  A* is only as good as its heuristic, so this lesson answers where good heuristics
  come from: relaxed problems, whose exact solution cost is an admissible heuristic,
  and pattern databases, which precompute subproblem costs. It measures heuristic
  quality with dominance and the effective branching factor, then tackles A*'s
  memory problem with IDA*, RBFS, and SMA*. It closes with modern heuristic search —
  weighted A*, learned and disjoint pattern-database heuristics, and bidirectional
  A*.
topics: [Search]
sources:
  - book: AIMA
    ref: "Ch. 3 — Solving Problems by Searching; §3.6 Heuristic Functions"
  - book: AIMA
    ref: "§3.5.3 Memory-bounded heuristic search"
---

The companion lesson,
[Informed Search and A*](/artificial-intelligence/search/informed-search),
built A* and proved it optimal when its heuristic $h$ is admissible (tree search)
or consistent (graph search). It left the practical question open: A* is only as
good as $h$, so where does a good one come from? This lesson answers that — with
relaxed problems and pattern databases — measures how good a heuristic is, and then
confronts the drawback that most limits A* in practice: not time, but memory.

## Inventing heuristics

A* is only as good as its heuristic, which raises the practical question: where does
$h$ come from? The classic testbed is the **8-puzzle** — slide numbered tiles into
the blank until the board matches a goal configuration. A random instance takes
about $22$ moves; the branching factor is roughly $3$, so blind search to depth $22$
touches around $3.1 \times 10^{10}$ states. A good heuristic is what makes this
tractable, and it must be admissible to keep A* optimal.

Two heuristics for the 8-puzzle are standard, and comparing them is the whole
lesson in miniature:

- $h_1$ = the **number of misplaced tiles.** Every out-of-place tile must move at
  least once, so $h_1$ never overestimates and is admissible. For a typical
  scrambled board $h_1 = 8$.
- $h_2$ = the **total Manhattan distance**, the sum over tiles of the horizontal
  plus vertical distance from each tile to its goal square. Since a move slides one
  tile one square, no single move can reduce this sum by more than one, so $h_2$ is
  also admissible. For the same board $h_2 = 18$.

$$
% caption: The 8-puzzle heuristics. For this start state $h_1 = 8$ (all eight tiles
% are misplaced), while $h_2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18$ sums each tile's
% Manhattan distance (city-block steps) to its goal square. Neither overshoots the
% true cost of 26.
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum size=8mm, font=\footnotesize},
  capt/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  % --- start board ---
  \begin{scope}[xshift=0cm]
    \node[cell] at (0,1.6) {7}; \node[cell] at (0.8,1.6) {2}; \node[cell] at (1.6,1.6) {4};
    \node[cell] at (0,0.8) {5}; \node[cell, fill=black!8] at (0.8,0.8) {};  \node[cell] at (1.6,0.8) {6};
    \node[cell] at (0,0) {8};   \node[cell] at (0.8,0) {3};   \node[cell] at (1.6,0) {1};
    \node[capt, anchor=north] at (0.8,-0.5) {Start State};
  \end{scope}
  % --- goal board ---
  \begin{scope}[xshift=4.2cm]
    \node[cell, fill=black!8] at (0,1.6) {};  \node[cell] at (0.8,1.6) {1}; \node[cell] at (1.6,1.6) {2};
    \node[cell] at (0,0.8) {3}; \node[cell] at (0.8,0.8) {4}; \node[cell] at (1.6,0.8) {5};
    \node[cell] at (0,0) {6};   \node[cell] at (0.8,0) {7};   \node[cell] at (1.6,0) {8};
    \node[capt, anchor=north] at (0.8,-0.5) {Goal State};
  \end{scope}
  \draw[->, acc, thick] (2.6,0.8) -- (3.8,0.8) node[midway, above, font=\scriptsize, text=acc] {solve};
\end{tikzpicture}
$$

Carrying $h_2$ through tile by tile shows the "no move helps two tiles" intuition.
Number the goal squares $0$–$8$ in reading order (top-left is $0$), so tile
$t$ belongs at square $t$. In the start board tile $7$ sits at square $0$ but belongs at
square $7$: that is two rows down and one column across — a Manhattan distance of $3$.
Doing this for all eight tiles:

| Tile | At square | Goal square | Row $\Delta$ | Col $\Delta$ | Distance |
| --- | --- | --- | --- | --- | --- |
| $7$ | $0$ | $7$ | $2$ | $1$ | $3$ |
| $2$ | $1$ | $2$ | $0$ | $1$ | $1$ |
| $4$ | $2$ | $4$ | $1$ | $1$ | $2$ |
| $5$ | $3$ | $5$ | $0$ | $2$ | $2$ |
| $6$ | $5$ | $6$ | $1$ | $2$ | $3$ |
| $8$ | $6$ | $8$ | $0$ | $2$ | $2$ |
| $3$ | $7$ | $3$ | $1$ | $1$ | $2$ |
| $1$ | $8$ | $1$ | $2$ | $1$ | $3$ |

The distances sum to $3 + 1 + 2 + 2 + 3 + 2 + 2 + 3 = 18$, so $h_2 = 18$. Every one
of the eight tiles is out of place, so $h_1 = 8$. Both are below the true optimal
cost of $26$ moves for this board, so both are admissible here — and $h_2 = 18 \ge 8
= h_1$, the dominance relation that will make $h_2$ the better heuristic.

### Relaxed problems

Neither heuristic was pulled from thin air — each is the _exact_ cost of a
**relaxed problem**, a version of the puzzle with restrictions removed. Write the
legal move as: "a tile can move from A to B if A is adjacent to B **and** B is
blank." Drop conditions:

- Drop both ("a tile can move from A to any B"): the cost to solve is the number of
  misplaced tiles — this is $h_1$.
- Drop only the blank requirement ("a tile can move to any adjacent square"): the
  cost is the total Manhattan distance — this is $h_2$.

A relaxed problem has fewer edges removed from the state space, so its graph is a
_supergraph_ of the original: every real solution is still a solution when the rules
are loosened, and the relaxation may admit cheaper shortcuts. Hence the cost of an
optimal solution to a relaxed problem is an admissible heuristic for the original —
and because it is an _exact_ cost, it automatically satisfies the triangle
inequality and is consistent as well.

> **Definition (Relaxed problem).** A problem obtained by dropping restrictions on
> the actions of the original, so its state-space graph is a supergraph of the
> original's. The optimal solution cost of a relaxed problem is an admissible,
> consistent heuristic for the original — provided the relaxation can be solved
> without search.

This is a general recipe: state a problem in a formal language, mechanically delete
preconditions, and read off a heuristic. The one requirement is that the relaxed
problem be _easy_ — solvable essentially without search (here each tile moves
independently) — or the heuristic costs as much to evaluate as the original search.

### Pattern databases

A second source of admissible heuristics is the exact solution cost of a
**subproblem**. Take the 8-puzzle and care only about getting tiles 1, 2, 3, 4 into
place, treating the others as blank; the cost of solving this subproblem is a lower
bound on solving the whole puzzle, because the full solution must at least place
those tiles.

$$
% caption: A pattern-database subproblem for the 8-puzzle. Only tiles 1-4 are
% tracked (dark); tiles 5-8 are treated as indistinguishable blanks (light). The
% exact cost to slide 1-4 into place, over every configuration of those four tiles,
% is precomputed and stored, then read back as a lower bound during the real search.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  keep/.style={draw, fill=acc!15, draw=acc, minimum size=8mm, font=\footnotesize, text=acc},
  dontcare/.style={draw=black, fill=black!10, text=black, minimum size=8mm, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[keep] at (0,1.6) {2}; \node[dontcare] at (0.8,1.6) {x}; \node[keep] at (1.6,1.6) {4};
  \node[dontcare] at (0,0.8) {x}; \node[keep] at (0.8,0.8) {1}; \node[dontcare] at (1.6,0.8) {x};
  \node[keep] at (0,0) {3}; \node[dontcare] at (0.8,0) {x}; \node[dontcare] at (1.6,0) {x};
  \node[anchor=west, font=\footnotesize] at (2.4,1.6) {track tiles 1-4 (blue)};
  \node[anchor=west, black, font=\footnotesize] at (2.4,0.8) {tiles 5-8 = blanks (x)};
  \node[anchor=west, acc, font=\footnotesize] at (2.4,0) {stored cost = lower bound};
\end{tikzpicture}
$$

A **pattern database** stores the exact subproblem cost for _every_ configuration of
the chosen tiles, precomputed once by searching backward from the goal. At search
time $h_{DB}(n)$ is a table lookup: read off the pattern of tiles 1–4 in state $n$
and return its stored cost. The construction cost is amortized over every future
instance of the puzzle. Building databases for several disjoint tile groups (1-2-3-4
and 5-6-7-8) and taking the maximum — or, if the move counts are kept disjoint,
their _sum_ — yields a **disjoint pattern database** that dwarfs Manhattan distance:
random 15-puzzles that were slow under $h_2$ solve in milliseconds, a node-count
reduction of roughly $10^4$.

### Combining heuristics and dominance

When several admissible heuristics $h_1, \ldots, h_m$ are available and none is
uniformly best, there is no need to choose. Take the pointwise maximum,

$$
h(n) = \max\{h_1(n), \ldots, h_m(n)\},
$$

which is still admissible (each component is a lower bound, so their max is too),
still consistent if the parts are, and at least as accurate as any single one. This
raises the question of what "more accurate" buys us, answered by **dominance**.

> **Definition (Dominance).** A heuristic $h_2$ **dominates** $h_1$ if
> $h_2(n) \ge h_1(n)$ for every node $n$ (both admissible). A* with a dominant
> heuristic never expands more nodes than A* with the dominated one, except
> possibly some tie-breaking on the goal contour.

The reasoning is short. A* surely expands every node with $f(n) < C^\ast$, i.e. every
node with $h(n) < C^\ast - g(n)$. Since $h_2 \ge h_1$ everywhere, any node A* is forced
to expand under $h_2$ it is also forced to expand under $h_1$ — and $h_1$, being
smaller, may force _extra_ expansions besides. For the 8-puzzle $h_2 \ge h_1$ always
holds (a misplaced tile contributes at least one to the Manhattan sum), so $h_2$
dominates $h_1$, and higher heuristic values are the thing to want, as long as they
stay admissible and cheap to compute.

### Effective branching factor

Dominance is a qualitative ordering; the **effective branching factor** $b^\ast$ turns
heuristic quality into a single number you can measure. If A* generates $N$ nodes to
find a solution at depth $d$, then $b^\ast$ is the branching factor a _uniform_ tree of
depth $d$ would need to hold $N + 1$ nodes:

$$
N + 1 = 1 + b^\ast + (b^\ast)^2 + \cdots + (b^\ast)^d.
$$

A perfect heuristic drives $b^\ast$ toward $1$ — the search marches almost straight
down the solution path — while an uninformed search leaves $b^\ast$ near the raw
branching factor. Because $b^\ast$ is roughly constant across instances of a given
problem, measuring it on a handful of small cases predicts the heuristic's value on
large ones.

The numbers make the case. Averaging $1200$ random 8-puzzle instances at each
solution depth $d$, iterative-deepening search, A\* with $h_1$ (misplaced tiles),
and A\* with $h_2$ (Manhattan distance) generate the following node counts, with the
implied effective branching factors alongside:

| $d$ | IDS nodes | A\*($h_1$) | A\*($h_2$) | $b^\ast$ IDS | $b^\ast$ $h_1$ | $b^\ast$ $h_2$ |
| --- | --- | --- | --- | --- | --- | --- |
| $2$ | $10$ | $6$ | $6$ | $2.45$ | $1.79$ | $1.79$ |
| $6$ | $680$ | $20$ | $18$ | $2.73$ | $1.34$ | $1.30$ |
| $8$ | $6384$ | $39$ | $25$ | $2.80$ | $1.33$ | $1.24$ |
| $10$ | $47{,}127$ | $93$ | $39$ | $2.79$ | $1.38$ | $1.22$ |
| $12$ | $3{,}644{,}035$ | $227$ | $73$ | $2.78$ | $1.42$ | $1.24$ |
| $16$ | — | $1301$ | $211$ | — | $1.45$ | $1.25$ |
| $20$ | — | $7276$ | $676$ | — | $1.47$ | $1.24$ |
| $24$ | — | $39{,}135$ | $1641$ | — | $1.48$ | $1.23$ |

Read the $d = 12$ row: uninformed iterative deepening generates $3.6$ million nodes,
A\* with $h_1$ only $227$, and A\* with $h_2$ just $73$ — a factor of about $50{,}000$
between blind search and the Manhattan heuristic. The effective branching factor
tells the same story more compactly: IDS holds near $2.8$ (barely below the true
branching factor of the puzzle), A\* with $h_1$ near $1.4$, and A\* with $h_2$ near
$1.25$. Because these factors are almost flat down the column, a value measured at
$d = 6$ predicts node counts out at $d = 24$, where IDS is hopeless and A\* with
$h_2$ still finishes in under two thousand nodes.

$$
% caption: Effective branching factor $b^*$ on the 8-puzzle: iterative-deepening
% search stays near the raw branching factor while the two A* heuristics collapse
% it toward 1, with the dominant Manhattan heuristic $h_2$ lowest across depths.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.2,0) node[right, font=\scriptsize, text=black] {depth d};
  \draw[->, black] (0,0) -- (0,3.4) node[above, font=\scriptsize, text=black] {b*};
  \foreach \x/\lab in {0.5/2, 1.7/6, 2.9/10, 4.1/14, 5.3/18, 6.5/22}
    \node[font=\scriptsize, text=black, anchor=north] at (\x,-0.05) {\lab};
  \foreach \y/\lab in {0.4/1.0, 1.4/1.5, 2.4/2.0, 3.0/2.8}
    \node[font=\scriptsize, text=black, anchor=east] at (-0.05,\y) {\lab};
  % IDS curve (near 2.8, only defined to d=12)
  \draw[black, thick]
    (0.5,3.1) .. controls (1.7,2.95) and (2.3,3.0) .. (2.9,2.98);
  \node[font=\scriptsize, text=black, anchor=west] at (2.95,3.0) {IDS};
  % A*(h1) curve (~1.4)
  \draw[acc, thick]
    (0.5,1.6) .. controls (1.7,1.28) and (2.9,1.35) .. (6.5,1.36);
  \node[font=\scriptsize, text=acc, anchor=west] at (6.6,1.36) {A*(h1)};
  % A*(h2) curve (~1.25, lowest)
  \draw[red, thick]
    (0.5,1.6) .. controls (1.7,1.1) and (2.9,1.14) .. (6.5,1.12);
  \node[font=\scriptsize, text=red, anchor=west] at (6.6,1.12) {A*(h2)};
\end{tikzpicture}
$$

## Memory-bounded search

A*'s memory cost, not its time, is what makes it impractical on large problems,
and the fix is to spend a little extra time to bound the space. The simplest such
variant carries the idea of iterative deepening into the heuristic setting:
**iterative-deepening A\*** (IDA*). Instead of a depth cutoff it uses an $f$-cost
cutoff. Each round runs a depth-first search that prunes any node whose $f = g + h$
exceeds the current limit; the next round's limit is the smallest $f$-value that
_exceeded_ the previous limit. IDA* keeps only the current path in memory — linear
space — and works well when step costs are integers, though real-valued costs make
the limit inch up one tiny node at a time.[^idastar]

$$
% caption: IDA* runs successive depth-first passes under a rising f-cost limit.
% Pass 1 (limit f = 12) explores only nodes with f <= 12; the smallest f that
% exceeded it (14) becomes pass 2's limit, and so on until a goal appears. Only the
% current root-to-leaf path is ever in memory.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  inb/.style={circle, draw, fill=acc!12, draw=acc, minimum size=5mm, inner sep=0pt, font=\scriptsize},
  cutb/.style={circle, draw, black, fill=black!5, minimum size=5mm, inner sep=0pt, font=\scriptsize},
  goalnd/.style={circle, draw, fill=acc, text=white, minimum size=5mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\scriptsize, anchor=south] at (1.1,1.9) {limit 12};
  \node[font=\scriptsize, anchor=south] at (6.1,1.9) {limit 14};
  % pass 1: root f=12 explored, children f=14 cut off
  \node[inb] (a0) at (1.1,1.4) {12};
  \node[cutb] (b0) at (0.5,0.4) {14}; \node[cutb] (c0) at (1.7,0.4) {16};
  \draw (a0)--(b0); \draw (a0)--(c0);
  % pass 2: limit 14, deeper, goal found
  \node[inb] (a1) at (6.1,1.4) {12};
  \node[inb] (b1) at (5.5,0.4) {14}; \node[cutb] (c1) at (6.7,0.4) {16};
  \node[goalnd] (g1) at (5.5,-0.6) {14};
  \draw (a1)--(b1); \draw (a1)--(c1); \draw (b1)--(g1);
\end{tikzpicture}
$$

Two further algorithms use all available memory rather than a fixed sliver.
**Recursive best-first search** (RBFS) mimics best-first expansion in linear space:
it follows the best path but tracks the $f$-value of the best _alternative_, and
when the current path exceeds it, the recursion unwinds, backing up each node's
$f$-value to the best $f$ among its children so a forgotten subtree can be recreated
later if it becomes worth revisiting. **SMA\*** (simplified memory-bounded A*)
proceeds exactly like A* until memory fills, then drops the frontier leaf with the
_worst_ $f$-value, backing that value up to its parent so the ancestor still
remembers how good the forgotten subtree was. All three trade repeated
re-expansions for a memory bound; RBFS is optimal when $h$ is admissible, SMA* when
the optimal solution is reachable within the memory budget. On genuinely hard
problems even SMA* can thrash, regenerating the same nodes as it switches among
candidate paths — the standing lesson that memory limits can make a problem
intractable in _time_.

## Modern heuristic search

A\* is fifty years old (Hart, Nilsson, and Raphael, 1968, _IEEE Trans. Systems
Science and Cybernetics_) and its optimal efficiency was proved by Dechter and Pearl
(1985). The research since then has pushed on the two pressure points these lessons
exposed: memory and heuristic strength.

**Trading optimality for speed.** When a solution merely needs to be _good_, not
provably optimal, **weighted A\*** ranks the frontier by $f(n) = g(n) + w\,h(n)$ with
$w > 1$, inflating the heuristic to drive the search harder toward the goal. The
returned solution is guaranteed within a factor $w$ of optimal, and in practice the
node count drops by orders of magnitude for modest $w$. Anytime variants —
**Anytime Repairing A\*** (Likhachev, Gordon, and Thrun, 2003, NIPS) — start with a
large $w$ to get a solution fast, then shrink $w$ and reuse prior work to tighten
toward optimal as time allows, reporting the best solution found so far at any
interruption.

$$
% caption: Weighting the heuristic narrows the explored region. Uniform-cost search
% (w = 0, no heuristic) sweeps a wide disk; A* (w = 1) stretches it toward the goal;
% weighted A* (w > 1) squeezes it into a narrow corridor, expanding far fewer nodes
% at the cost of a solution up to a factor w above optimal.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \begin{scope}[xshift=0cm]
    \draw[acc, thick, fill=acc!8, rotate=-18] (0,0) ellipse (1.2 and 1.2);
    \fill[acc] (-0.75,0.2) circle (1.6pt); \fill[red] (0.85,-0.3) circle (1.6pt);
    \node[font=\scriptsize, anchor=north] at (0,-1.55) {w = 0};
    \node[acc, font=\scriptsize, anchor=south] at (0,1.4) {uniform-cost};
  \end{scope}
  \begin{scope}[xshift=3.5cm]
    \draw[acc, thick, fill=acc!8, rotate=-18] (0,0) ellipse (1.35 and 0.85);
    \fill[acc] (-0.75,0.2) circle (1.6pt); \fill[red] (0.85,-0.3) circle (1.6pt);
    \node[font=\scriptsize, anchor=north] at (0,-1.55) {w = 1};
    \node[acc, font=\scriptsize, anchor=south] at (0,1.4) {A-star};
  \end{scope}
  \begin{scope}[xshift=7.0cm]
    \draw[acc, thick, fill=acc!8, rotate=-18] (0,0) ellipse (1.5 and 0.5);
    \fill[acc] (-0.75,0.2) circle (1.6pt); \fill[red] (0.85,-0.3) circle (1.6pt);
    \node[font=\scriptsize, anchor=north] at (0,-1.55) {w $>$ 1};
    \node[acc, font=\scriptsize, anchor=south] at (0,1.4) {weighted A-star};
  \end{scope}
\end{tikzpicture}
$$
This is standard in robot motion planning, where a feasible plan now
beats an optimal plan too late.

**Stronger heuristics, automatically built.** The
[pattern-database](/artificial-intelligence/search/heuristic-functions) idea sketched
above became a research program. Culberson and Schaeffer (1996, 1998) introduced
pattern databases; Korf and Felner (2002) showed that _disjoint_ (additive) pattern
databases solve random 15-puzzles in milliseconds — a factor of $10^4$ fewer nodes
than Manhattan distance — and give roughly a millionfold speedup on the 24-puzzle.
The relaxed-problem recipe itself was automated: Prieditis (1993) built a system
that mechanically derives admissible heuristics by dropping preconditions from a
formal problem description, so the heuristic-invention step this lesson does by hand
can be done by machine.

**Learning the heuristic.** Rather than derive $h$ from a relaxation, one can learn
it from solved instances. Each optimal solution supplies (state, true-cost-to-go)
pairs, and a regression model — historically over hand-built features, now over
neural networks — fits $h$ to them. Learned heuristics need not be admissible, so
they are typically paired with weighted or bounded-suboptimal search; the same
regression idea reappears as the value function in
[reinforcement learning](/reinforcement-learning/foundations/markov-decision-processes),
where the estimated cost-to-go _is_ the thing being learned.

**Bidirectional heuristic search, finally practical.** Combining A\* with the
bidirectional idea from
[uninformed search](/artificial-intelligence/search/uninformed-search) resisted a
clean treatment for decades, because ensuring the first frontier meeting is optimal
is subtle. Holte, Felner, Sharon, and Sturtevant (2017, _Artificial Intelligence_
252) resolved it with **MM**, a bidirectional search whose two halves are guaranteed
to meet no deeper than the midpoint of the optimal path, making bidirectional
heuristic search competitive with A\* on hard instances for the first time. And on
uniform grids, **jump point search** (Harabor and Grastien, 2011, AAAI) accelerates
A\* by an order of magnitude — not with a better heuristic but by exploiting path
symmetry to skip the interior grid nodes A\* would otherwise expand — which is why it
is the default in modern game pathfinding.

## Where this sits

A* is the meeting point of two threads. Set $h = 0$ and it is uniform-cost search
from
[uninformed search](/artificial-intelligence/search/uninformed-search) — the same
priority-queue expansion, now called Dijkstra's algorithm in the
[shortest-paths](/algorithms/graphs/shortest-paths) setting, where $g(n)$ is the
tentative distance and the frontier is the priority queue. The heuristic $h$ is the
one addition graph algorithms usually lack: a domain-specific lower bound that pulls
the expansion toward the goal instead of spreading it uniformly. Everything that
follows in search — [local search](/artificial-intelligence/search/local-search)
when the state space is too large to hold a frontier at all,
[adversarial search](/artificial-intelligence/search/adversarial-search) when an
opponent moves too — either abandons the systematic frontier or shares it with
another agent, but the idea of an evaluation function scoring how good a position is
carries straight through.

[^idastar]: **Russell & Norvig**, §3.5.3 — Memory-bounded heuristic search: IDA* with an $f$-cost cutoff, RBFS with backed-up $f$-values in linear space, and SMA* dropping the worst leaf when memory fills.