algorithmartificial-intelligencea-startree-search

how to prove a compatible heuristics can be a admissible heuristics in A* search algorithm


compatible heuristics (h) is the one that has below condition:

h(n) <= c(n,a,n') + h(n')

compatible heuristic

****************************************************

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.


Solution

  • 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.