Consistent Heuristic

A consistent heuristic (or monotonic heuristic) is a heuristic function h(n) that satisfies the triangle inequality: for every node n and every successor n' generated by action a, the estimated cost h(n) is no greater than the step cost c(n, a, n') plus the estimated cost h(n'). Formally: h(n) ≤ c(n, a, n') + h(n'). Consistency implies admissibility, but not vice versa.

The significance of consistency for A* search is that it guarantees the algorithm never needs to re-expand a node. Once a node is removed from the open set, its f-score is final. This simplifies implementation and improves performance, though many practical heuristics are admissible without being strictly consistent.

Consistency is a geometric property: it requires that the heuristic respects the metric structure of the search space. Euclidean distance and Manhattan distance are consistent on their respective spaces because the triangle inequality holds. The zero heuristic is trivially consistent.

See also: Admissible Heuristic, A* Search, Heuristic Function, Triangle Inequality, Heuristic search