compatible heuristics (h) is the one that has below condition:
h(n) <= c(n,a,n') + h(n')
****************************************************
admissible heuristics (h) is the one that has below condition:
0 <= h(n) <= h*(n)
h*(n) is the real distance from node n
to the goal
If a heuristic is compatible, how to prove it is admissible ?
Thanks a lot.
Assume that h(n) is not admissible, so there exists some vertex n such that h(n) > h*(n).
But because of the compatibility of h(n), we know that for all n` it holds that h(n) <= c(n,a,n') + h(n').
Now combine these two predicates when n` is the vertex G to deduce a contradiction, thus proving the required lemma reduction ad absurdum.