Optimality of A*

Question

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.

Answer 1

The heuristic is both admissible and consistent. However, the algorithm has found the path ABD, not ACD as you state. At step 3, although expanding B doesn't add any new nodes to the open list, it does update node D with the information that the cheapest route to it is via B.

To your description of the stages of the search, you should add the following actions, after updating the open and closed lists:

step 1: note that the cheapest path to B is from A
        note that the cheapest path to C is from A

step 2: note that the cheapest path to D is from C

step 3: note that the cheapest path to D is from B (not C)

After step 2, the algorithm believes that the cheapest path to D is via C. However, at step 3, it finds a cheaper path via B and updates its belief.