Course contentsShow
← Computer Science
Lesson 1004 of 2,87223. Shortest Path AlgorithmsFree lesson

Consistent (Monotonic) Heuristics

Explore consistency property where h(n) ≤ cost(n,n') + h(n') and its impact on A* efficiency.

Consistent (Monotonic) Heuristics

What you'll learn: How the consistency property strengthens admissible heuristics and makes A* more efficient.

The Core Idea

A consistent (or monotonic) heuristic goes beyond being merely admissible—it satisfies a triangle inequality-like property. Formally, for every node n and every successor n':

h(n) ≤ cost(n, n') + h(n')

This means the estimated cost from n to the goal can't be greater than the cost to move to n' plus the estimate from n' to the goal.

Think of it like a GPS navigation system: if you're 10 miles from your destination, and you drive 3 miles closer, your new estimate shouldn't say you're now 15 miles away. The estimates must "make sense" as you move through the graph.

Why Consistency Matters for A*

When a heuristic is consistent, A* gains a powerful guarantee: the first time A expands a node, it has found the shortest path to that node*. No re-expansions are needed.

This happens because consistency ensures that f(n) values are non-decreasing along any path. Since f(n) = g(n) + h(n), and the heuristic "decreases smoothly," A* explores nodes in optimal order.

The Efficiency Impact

  • No duplicate work: Each node is expanded at most once
  • Optimality preserved: Consistency implies admissibility, so solutions remain optimal
  • Cleaner implementation: You can skip the "reopen" logic where nodes get re-added to the priority queue with better paths

Every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency is the stronger, more desirable property.

Key Takeaway: A consistent heuristic satisfies h(n) ≤ cost(n,n') + h(n'), ensuring A* expands each node only once while maintaining optimality—a major efficiency win.