Can someone give me an example of admissible heuristic that is not consistent?

Question

In this figure:

 

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

Answer 1

CONSISTENT HEURISTIC:

A heuristic in the algorithm is consistent if the cost from the current node to a successor node, plus the estimated cost from the successor node to the goal is less than or equal to the estimated cost from the current node to the goal.

In an equation, it would look like this: C(n, n’) + h(n’) ≤ h(n)

ADMISSIBLE HEURISTIC:

A heuristic function is admissible if the estimated cost is never more than the actual cost from the current node to the goal node.

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.

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.

Answer 2

The example that I would like to present for admissible heuristic that is not consistent goes like this:

So, basically the admissible heuristic is that algorithm that never overestimates the cost of finding the path, this means that the cost of reaching a point X from a point Y will always be less than or equal to the actual cost.

Now, let’s say there exists a heuristic function h(x), that will help us estimate the cost for reaching to a node Y. Now, as far as the definition goes, admissible heuristic is that algorithm that never overestimates. So, if we imagine ourselves standing in a place where we can go up, down, left and right in one 1 box. Then the function would be behaving something like this:

• For a given node assuming that it’s in centre, then if we have go south or north, then h(X) will be a vertical distance for the goal

• If we have go east or west from that node, then h(X) will be a horizontal distance for the goal

• If we are going in another direction then it will be 0.

Now, let’s say we have two nodes, C and D which are adjacent to each other, and they both have the same goal of reaching to the north. Then in this case we would be having an inconsistent admissible heuristic