Heuristics

A heuristic $h(n)$ estimates the cost from node $n$ to the nearest goal. The right heuristic turns intractable searches into routine ones.

Admissibility

A heuristic is admissible if it never overestimates the true cost:

where $h^*(n)$ is the true optimal cost from $n$ to a goal. Admissibility is what guarantees A* finds the optimal solution.

Consistency (monotonicity)

Stronger property: for every node $n$ and successor $n'$ reachable by action with cost $c$:

Equivalently: the estimated cost decreases by at most the actual step cost. Consistent heuristics are admissible (set $n'$ to be on the optimal path to a goal). With a consistent heuristic, A* never re-opens a closed node.

Most natural heuristics — Manhattan distance, straight-line distance — are consistent. Constructing admissible-but-not-consistent heuristics requires effort.

Examples

• 8-puzzle, misplaced tiles: count of tiles in wrong positions. Admissible (each misplaced tile takes at least 1 move). Loose.
• 8-puzzle, Manhattan distance: sum of horizontal+vertical distances of each tile from its goal. Admissible and consistent. Much tighter than misplaced tiles.
• Route planning: straight-line distance is admissible (you can't be faster than going in a straight line at top speed).
• Pancake flipping: number of "burnt" boundaries (consecutive pancakes in wrong order) is admissible.

Dominance

Heuristic $h_1$ dominates $h_2$ if $h_1(n) \geq h_2(n)$ for every $n$ (and both are admissible). A dominant heuristic produces strictly fewer node expansions in A*. More informed is always better — as long as you don't sacrifice admissibility or consistency.

Relaxations as heuristic sources

The most reliable way to construct admissible heuristics: solve a *relaxed* version of the problem where some constraints are removed.

• Remove "can only move into adjacent empty cell" → Manhattan distance falls out.
• Remove "can only fly between cities with direct flights" → straight-line distance.
• Remove preconditions in planning → delete-relaxation heuristics ($h^{\text{add}}$, $h^{\text{max}}$, $h^{\text{FF}}$).

Pattern databases

Precompute true costs for a subset of features (a "pattern"), then use as a heuristic. The 15-puzzle gets solved fast this way — store true costs for fringe-tile patterns and additive combinations of disjoint patterns.