Heuristic Functions and Memory-Bounded Search

The companion lesson, Informed Search and A*, 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$.

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:

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.

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.

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,\dots ,h_m$ are available and none is uniformly best, there is no need to choose. Take the pointwise maximum,

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.

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:

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:

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.

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

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)+wh(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.

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 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, 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 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 — the same priority-queue expansion, now called Dijkstra's algorithm in the 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 when the state space is too large to hold a frontier at all, 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.