Heuristic quality: monotonicity, informedness, and the 8-puzzle

◈ 3 cards

Monotone (consistent) heuristics, what makes one heuristic more informed than another, and comparing two admissible 8-puzzle heuristics.

Two ways to grade a heuristic

Admissibility tells you a heuristic is safe (it won't break optimality). Two finer properties tell you how good it is.

### Monotonicity (consistency)

A heuristic $h$ is monotone (a.k.a. consistent) if for every state $n_{i}$ and any descendant $n_{j}$ ,

$h (n_{i}) - h (n_{j}) \leq cost (n_{i}, n_{j}), h (goal) = 0.$

That is, the estimate never drops by more than the actual step cost between the states. Monotonicity is a stronger, local version of admissibility: every monotone heuristic is admissible (sum the inequality along any path), but not every admissible heuristic is monotone.

The practical pay-off: with a monotone heuristic, the first time best-first reaches a state it has already reached it by an optimal path. So a re-discovered state can simply be discarded — no path-length comparison needed — and the $f$ values of successively expanded states are non-decreasing.

### Informedness

For two admissible heuristics $h_{1}$ and $h_{2}$ , $h_{2}$ is more informed than $h_{1}$ if $h_{2} (n) \geq h_{1} (n)$ for all $n$ (while both stay $\leq h^{*}$ ). A more informed heuristic gives a tighter lower bound, so A\* with $h_{2}$ expands a subset of the states it expands with $h_{1}$ — it reaches the optimum examining fewer states. (Caveat: a more informed heuristic can cost more to compute; the saving in states must outweigh the per-state cost.)

Worked example: two 8-puzzle heuristics

For the 8-puzzle, two classic admissible heuristics:

Tiles out of place — count how many tiles are not in their goal cell. Each move fixes at most one tile, so this can never exceed the true number of moves ⇒ admissible.
Manhattan distance — sum, over all tiles, the grid distance (rows + columns) each tile must travel. Tiles can't teleport, so this also never overestimates ⇒ admissible — and it is a tighter count, so it is more informed.

Take a scrambled board and a goal board. Counting gives tiles-out-of-place $= 4$ and Manhattan $= 5$ . Manhattan $\geq$ tiles-out-of-place on this state (and in general), confirming Manhattan dominates — it is the more informed of the two while remaining admissible.

Tiles-out-of-place counts the highlighted cells: <strong>4</strong>. Manhattan sums how far each of them must travel — tile 2 moves one column, tile 8 moves a row and a column, tile 1 moves one row, tile 6 moves one row — giving 1 + 2 + 1 + 1 = <strong>5</strong>. Both undercount the real work (neither notices that tiles block one another), so both are admissible; Manhattan counts more of it, so it is the more informed of the two.

Every row is admissible, so every row keeps A* optimal — they differ only in how much work each saves. A tighter lower bound prunes more, so A* with Manhattan expands a subset of what it expands with tiles-out-of-place, which in turn expands a subset of blind BFS. The ladder stops at h*, which would expand only the states on the optimal path.