Heuristics
Motivation
Uninformed search treats every node the same: BFS expands by depth, DFS by recency, neither using any sense of which nodes are closer to a goal. A heuristic function supplies that missing sense — a cheap, approximate estimate of the remaining cost from a node to the nearest goal — and lets informed algorithms like A* search focus exploration on promising branches instead of expanding outward blindly (Russell and Norvig 2020).
The quality of a heuristic determines almost everything about the resulting search: a perfect heuristic walks straight to the goal in a straight line, a bad one wastes work hunting in the wrong direction, and the wrong kind of heuristic destroys optimality guarantees.
Setup
A search problem has a graph \(G = (V, E)\) with non-negative edge costs \(c(n, n') \ge 0\), a start node \(s\), and a set of goal nodes \(\mathcal{G} \subseteq V\). Let
\[ h^*(n) = \min_{g \in \mathcal{G}} \, \text{(cost of cheapest path from } n \text{ to } g\text{)} \]
denote the true cost-to-go from \(n\), with \(h^*(n) = \infty\) if no goal is reachable.
A heuristic function is any \(h : V \to \mathbb{R}_{\ge 0}\) with \(h(g) = 0\) for every goal \(g\). It is meant to approximate \(h^*\).
Admissibility
A heuristic is admissible if it never overestimates:
\[ h(n) \le h^*(n) \quad \text{for every } n \in V. \]
Admissibility is the property that makes A* optimal: a heuristic that occasionally overstates the true cost can fool the algorithm into ignoring a cheap path it has not yet noticed (Hart et al. 1968). (proof)
The trivial admissible heuristic is \(h \equiv 0\), which reduces A* to uniform-cost search (Dijkstra). Useful admissible heuristics retain the “no overestimate” guarantee while being substantially larger.
Consistency
A heuristic is consistent (or monotone) if for every edge \((n, n')\) with cost \(c(n, n')\),
\[ h(n) \le c(n, n') + h(n'). \]
This is a triangle inequality: the heuristic estimate from \(n\) is no larger than the cost of one step plus the estimate from the successor.
Consistency implies admissibility. Iterating along any path from \(n\) to the nearest goal \(g\) telescopes to \(h(n) \le h^*(n) + h(g) = h^*(n)\), so every consistent heuristic is admissible. (proof)
The converse is false: some admissible heuristics are not consistent. But almost every heuristic that arises from a natural relaxation is consistent in practice, and the distinction matters only for graph search, where consistency lets A* close nodes permanently — without it, nodes may need to be re-opened when a cheaper path is discovered. (proof)
Dominance
If \(h_1\) and \(h_2\) are both admissible and \(h_2(n) \ge h_1(n)\) for every \(n\), then \(h_2\) dominates \(h_1\). A dominating heuristic is uniformly better for A*: it expands no more nodes than the dominated one. Among admissible heuristics, larger is always better — closer to \(h^*\) means tighter \(f\)-values means more pruning.
Two corollaries:
- \(h_{\max}(n) = \max(h_1(n), h_2(n))\) is admissible if both are, and dominates both. Combining heuristics this way is free.
- The perfect heuristic \(h^*\) would expand only nodes on an optimal path. Every admissible \(h\) is bounded above by \(h^*\), so \(h^*\) is the best possible — but computing it is exactly the search problem we are trying to solve.
Constructing Heuristics
The standard recipe is problem relaxation: drop a constraint of the original problem to make it easy, then use the optimal cost in the relaxed problem as the heuristic. Because every solution to the original problem is a solution to the relaxation (just with extra constraints satisfied), the relaxed cost is a lower bound on the original cost — automatically admissible.
Examples:
- 8-puzzle, misplaced tiles. Relax the constraint that a tile can only move to an adjacent blank square; let any tile teleport. The optimal cost is the number of misplaced tiles. Admissible.
- 8-puzzle, Manhattan distance. Relax the constraint that only one tile may occupy a square; let tiles slide independently. The optimal cost is the sum of Manhattan distances from each tile to its goal. Admissible and dominates misplaced tiles.
- Pathfinding on a grid. Straight-line (Euclidean) distance to the goal, ignoring obstacles. Admissible; consistent if movement costs satisfy the triangle inequality.
- Pattern databases. Precompute the exact optimal cost of solving a subset of the puzzle’s tiles, indexed by their configuration. The original problem’s cost is at least the subset’s cost, so the lookup is admissible.
A more advanced technique uses landmarks and bidirectional bounds: precompute exact distances from a few selected nodes and combine via the triangle inequality.
Inadmissible Heuristics
Heuristics that occasionally overestimate sacrifice optimality but can still be useful:
- Weighted A*. Use \(f(n) = g(n) + w \cdot h(n)\) with \(w > 1\). Faster but returns solutions within a factor \(w\) of optimal rather than exactly optimal.
- Greedy best-first search. Use \(f(n) = h(n)\) alone. Often very fast, no optimality guarantee, and not even complete on infinite graphs.
- Learned heuristics. Neural networks trained on solved instances may produce non-admissible estimates that nonetheless guide search effectively in practice.
Heuristics for Adversarial and Stochastic Settings
In minimax search, the evaluation function applied at depth-limited leaves plays the same role a heuristic plays in single-agent search: a quick estimate that stands in for an exact value the algorithm cannot afford to compute. Construction, evaluation, and tuning concerns largely transfer; the main difference is that admissibility has no analogue, since both players are estimating and the estimate is two-sided.