18

In this figure:

enter image description here let's assume that h(C)=1 If f(A)=g(A)+h(A)=0+4=4, and f(C)=g(C)+h(C)=1+1=2 Then f(C) is NOT greater than or equal to f(A) Therefore this example is consistent and admissible, but can someone give me an example of admissible heuristic that is not consistent? please

Wajahat
  • 1,593
  • 3
  • 20
  • 47
user3880907
  • 271
  • 2
  • 4
  • 10
  • Possible duplicate of [Consistent and Admissible Heuristics](http://stackoverflow.com/questions/20516027/consistent-and-admissible-heuristics) – Don Reba Oct 02 '15 at 11:42
  • 1
    isn't your example heuristics admissible? it never overestimates the real cost. `4 = h(A) <= real cost from A to G = 4` ,`1 = h(C) <= real cost from C to G = 3` – sve Oct 02 '15 at 11:45
  • @svs yes you are right, my mistake. – user3880907 Oct 02 '15 at 11:50
  • 1
    But again since `f(A) > f(C)` your example heuristics is not consistent. Then your heuristics `h(A)=4, h(C)=1, h(G)=0` is admissible and not consistent - exactly what you are looking for :) – sve Oct 02 '15 at 11:55

2 Answers2

29

if you want your heuristics to be admissible then you should have that h(n) <=h*(n) for every node n where h* is the real cost to the goal. In your case you want:

h(A) <= 4
h(C) <= 3
h(G) <= 0

If you want your heuristics to be consistent then you should have that h(G) = 0 and h(n) <= cost(n, c) + h(c) where the node c is a child of node c. So in your case

h(A) <= 1 + h(C)
h(C) <= 3 + h(G) = 3

If you want inconsistency and since h(C) <= 3 for the admissibility condition then you should have that h(A) > 1 + h(C). So any heristics that satisfies:

h(A) > 1 + h(C)
h(C) <= 3
h(G) = 0

is admissible and not consistent. You gave

h(A) = 4
h(C) = 1
h(G) = 0

which is a valid candidate.

sve
  • 4,336
  • 1
  • 19
  • 30
  • Thank you very much!! I am really grateful, now it is clear to me ! :) – user3880907 Oct 02 '15 at 13:30
  • 1
    @user3880907 you are welcome, I'm always happy to help :) – sve Oct 02 '15 at 13:31
  • 1
    Sorry to bring this up so late but in the list of conditions that are to be satisfied for the heuristic to be admissible and inconsistent, shouldn’t h(A)<=4 also be included ? – Hani Sep 13 '19 at 14:34
0

If you assign a decreasing heuristic function of the depth of the optimal soution path (but attempt to do not violate overestimate condition for admissibility), thereby the result heuristic is admissible but is not consistent.

saeed foroutan
  • 1