Skip to main content

Proof: every consistent heuristic is also admissible

Proof: Let h(x) be any consistent heuristic, and let c(x,y) be the corresponding step cost of moving from the state x to another state y. Then h(x)c(x,y)+h(y) by the definition of consistency. To show that h is admissible, we must show that h(x)p(x) where p is the path cost of x.

Suppose there is no path from x to the goal state. In this case, p(x) is infinite, and satisfies that h(x)p(x) for any finite h(x).

Now suppose that there is some path form x to a goal state g. Let us call intermediate nodes of a shortest path w1,w2,wn. So the shortest path from x to g is expressed as (x,w1,w2,wn,g).

Now consider h(wn). Since h is consistent, h(wn)c(wn,g)+h(g)=c(wn,g) since h(g)=0. Similarly, h(wn1)c(wn1,wn)+h(wn)c(wn1,wn)+c(wn). By induction on n, we obtain h(wk)c(wk,wk+1)++c(wn1,wn)+c(wn,g) for any k between 1 and n-1. But because (x,w1,w2,wn,g) is a shortest path, p(wk)=c(wk,wk+1)++c(wn1,wn)+c(wn,g) so that h(wk)p(wk) as desired.

Q.E.D.