Suboptimal solution given by A* search

Question

I don't understand how the following graph gives a suboptimal solution with A* search.

The graph above was given as an example where A* search gives a suboptimal solution, i.e the heuristic is admissible but not consistent. Each node has a heuristic value corresponding to it and the weight of traversing a node is given. I don't understand how A* search will expand the nodes.

Answer 1

The heuristic h(n) is not consistent.

Let me first define when a heuristic function is said to be consistent.

h(n) is consistent if  
– for every node n
– for every successor n' due to legal action a 
– h(n) <= c(n,a,n') + h(n')

Here clearly 'A' is a successor to node 'B' but h(B) > h(A) + c(A,a,B)

Therefore the heuristic function is not consistent/monotone, and so A* need not give an optimal solution.