3

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.

Vahid Najafi
  • 4,654
  • 11
  • 43
  • 88

2 Answers2

2

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.

Pieter Geerkens
  • 11,775
  • 2
  • 32
  • 52
  • As a graph theory TA, I wouldn't give full credit for such an answer, because it lacks some important explanation, why the fact that `h(n) <= c(n,a,n') + h(n')` is contradicting? There is no restriction to allowing `h(n') > h*(n')`, and the inequality holds. You need to look at the smallest value of `h` such that `h(n)>h*(n)` and follow the same logic on it to avoid this from happening (note however that you cannot assume "smallest value" for infinite graphs). – amit Jan 01 '15 at 09:14
  • @amit: Of course the proof outline above is incomplete; I am trying to lead a horse to water, not prying it's mouth open and pouring gallons down it's throat. BTW: Did you actually read paragraph 3 of my answer above? – Pieter Geerkens Jan 01 '15 at 13:42
2

If you add an additional condition on h (namely that h(goal) = 0), you can prove it by induction over the minimum cost path from n to the goal state.

For the base case, the minimum cost path is 0, when n = goal. Then h(goal) = 0 = h*(goal).

For the general case, let n be a node and let n' be the next node on a minimal path from n to goal. Then h*(n) = c(n, n') + h*(n') >= c(n, n') + h(n') >= h(n) using the induction hypothesis to get the first inequality and the definition of compatibility for the second.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
  • In addition, this assumption (h(goal) = 0) is a must, otherwise by definition, h(goal)>h*(goal), and the heuristic is not admissible. – amit Jan 01 '15 at 08:20
  • However, this answer fails for infinite graphs. Assume the graph where h(v1) = 1, h(v2) = 1/2, h(v3) = 1/4, h(v4) = 1/8, .... While on theory - this is an admissible heuristic, the inductive proof fail for such graphs. – amit Jan 01 '15 at 09:12
  • @amit "the A\* search algorithm" in the question precludes paths having infinite length. – Paul Hankin Jan 01 '15 at 12:31