I read in the artificial-intelligence book of Russel and Norvig that The tree-search version of A* is optimal if heuristic function is admissible, while the graph-search version is optimal if heuristic function is consistent(monotone). An admissible heuristic is one that never overestimates the cost to reach the goal. A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plus the estimated cost of reaching the goal from $n'$ : $h(n) ≤ c(n, a, n') + h(n')$.
My question is about this graph and heuristic.
Suppose this graph is a state space of a problem in Artificial intelligence. $A$ is the start node(initial state),and $D$ is the goal. Numbers on the edges are path costs. Numbers on the nodes are value of heuristic function for this problem. I think this heuristic function is consistent. So A* can find the optimal path from start to goal.
step 1: g(A)=0, h(A)=5, so f(A)=5 Expand A : B, C add A to close list. add B and C to open list. step 2: g(B)=10, h(B)=1, so f(B)=11 g(C)=1, h(C)=8, so f(C)=9 f(C) < f(B) so: Expand C : D add C to close list add D to open list. step 3: g(D)=1+16=17,h(D)=0, so f(D)=17 f(B) < f(D) so: Expande B : nothing because D is already in open list. step 4: Just D in open list so Expand D : D is goal Result: path:ACD, cost=17
A* found the path ACD but optimal path is ABD.