Consistency and Monotonicity
What you'll learn: Why consistent heuristics make A* even more efficient by guaranteeing it never needs to reopen nodes.
The Core Idea
You've learned that admissible heuristics guarantee A* finds optimal solutions. But there's a stronger property called consistency (or monotonicity) that goes further: it ensures A* never has to reconsider nodes it's already expanded.
A heuristic h(n) is consistent if, for every node n and its successor n', the estimated cost from n to the goal never exceeds the step cost to reach n' plus the estimate from n':
h(n) ≤ cost(n, n') + h(n')
This is the triangle inequality from geometry: the direct estimate can't be greater than taking a detour through a successor.
Why This Matters for A*
When a heuristic is consistent, f-values along any path are non-decreasing. Think of climbing a mountain where elevation (f-value) only goes up or stays level—never drops. This means:
- Once A* expands a node with f-value
f₁, it will never encounter a better path to that node later (which would have a higher f-value) - A never needs to reopen nodes*—once a node is explored, it's done
- The explored set acts as a true "closed list"
The Analogy
Imagine navigating with a GPS that estimates remaining distance. A consistent heuristic is like a GPS that never suddenly jumps upward after you drive closer—the estimate shrinks smoothly or stays accurate as you progress.
Consistency Implies Admissibility
Every consistent heuristic is also admissible (never overestimates), but not vice versa. Consistency is the stronger guarantee.
Key Takeaway: Consistent heuristics ensure A* expands nodes in order of increasing f-value and never reopens nodes, making the algorithm maximally efficient while preserving optimality.