Consistent heuristic

In computer science, a heuristic is consistent (or monotone) if, for every node n and every successor p of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to p plus the estimated cost of reaching the goal from p. In other words:

$h(N)\leq c(N,P)+h(P)$ and

$h(G)=0.\,$

where

• h is the consistent heuristic function
• N is any node in the graph
• P is any child of N
• G is any goal node.

A consistent heuristic is also admissible. This is proved by induction. By assumption, $h(N_{m})\leq h^{*}(N_{m})$. Therefore,

$h(N_{m+1})\leq c(N_{m+1},N_{m})+h(N_{m})\leq c(N_{m+1},N_{m})+h^{*}(N_{m})=h^{*}(N_{m+1})$,

making it admissible.

Note: not all admissible heuristics are consistent.