The Monotone (Consistency) Condition

The Simplest Explanation

A heuristic $h$ is monotone (consistent) if across every edge from node m to node n:

$h(m) - h(n) \;\leq\; c(m, n)$

In words: the heuristic never drops faster than real cost accrues. Equivalently, h never overestimates the cost of any single edge.

Consequence 1 — f Never Decreases Along a Path

For successor n of m:

$h(m) \leq h(n) + c(m,n)$

Add $g(m)$ to both sides:

$g(m) + h(m) \leq \underbrace{g(m) + c(m,n)}_{=\,g(n)} + h(n) = f(n)$

So $f(m) \leq f(n)$: f values are non-decreasing along every path A* explores. This matches observed A* traces where f creeps upward toward the goal.

Consequence 2 — First Path Found to Any Node Is Optimal

When A* selects node n from Open, $g(n) = g^*(n)$ exactly.

Proof sketch by contradiction: if $g(n) > g^*(n)$, some node on the true optimal path to n would still be on Open with $f \leq g^*(n) + h(n) \leq f(n)$, contradicting that n was the minimum choice. Hence no cheaper route to n exists.

The Payoff: Case 3 Vanishes

Recall A*'s three cases for neighbors:

1. New → add to Open
2. On Open with cheaper g → update
3. On Closed with cheaper g → update + propagate improvement to descendants

Under monotonicity, Case 3 never arises. Once a node moves to Closed, it stays put — no reopening, no propagation. A* degenerates into Dijkstra-style bookkeeping: close once, done.

Why This Unlocks Memory Pruning

If Closed nodes are final, they can be safely deleted or compressed (Frontier Search / SMGS rely on this). With an inconsistent heuristic you must keep Closed around — a reopened node might need its old parent chain.