Definitions

# 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\left(N\right) leq c\left(N,P\right) + h\left(P\right)$ and
$h\left(G\right) = 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\left(N_m\right) leq h^*\left(N_m\right)$, where $h^*\left(n\right)$ denotes the cost of the shortest arc from n to the goal. Therefore,

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