Optimality of A*

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.

1 Answer

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.

• In that book I read: When a heuristic is consistent, A* algorithm selects a node n for expansion, the optimal path to that node has been found.But I don't pay attention to "for expansion", and I think when A* saw a node n,the optimal path to that node has been found. You are right. – Ahmad Apr 2 '14 at 17:39
• I reading and thinking again...It's true, but there is one problem:if graph-search update the path, then for Optimality of A*(graph-search), a admissible heuristic is enough(not just consistent heuristic). But if graph-search does not update the path, then A*(graph-search) isn't optimal, even with consistent heuristic.Isn't it true? – Ahmad Apr 2 '14 at 19:46
• @Ahmad I'm not sure what you mean. A* is optimal. If you did something different to A*, then yes, you might not be optimal -- but you wouldn't be A*. – David Richerby Apr 2 '14 at 23:06
• Let's suppose graph-search update paths. OK, I focus on optimality of graph-search version of A*. My question is "When graph-search version of A* is optimal?". My answer is "A admissible heuristic is enough for optimality of graph-search version of A*". But Russel and Norvig in their book wrote:"For optimality of graph-search version of A*, a heuristic function must be consistent". I have problem with this.Do you have an example that a heuristic is admissible and not consistent but A* is not optimal? – Ahmad Apr 3 '14 at 7:33
• I don't know... So description of A* in that book isn't very accurate. :( – Ahmad Apr 3 '14 at 10:17