I'm reading a text book "Artificial Intelligence - A Modern Approach (3rd Edition)".
In page 95, the book mentions that "A* has the following properties: the tree-search version of A* is optimal if h(n) is admissible, while the graph-search version is optimal if h(n) is consistent."
But there's no clear proof why admissible h(n) only guarantees optimality in the tree search version of A*.
Can someone explain why the graph version of A* with an admissible heuristic doesn't guarantee optimality?
The reason why an admissible heuristic only guarantees optimality for the tree-search version of A* is due to the possibility of revisiting nodes in the graph-search version.
In the tree-search version, each node is expanded only once, and the algorithm never revisits a node. Therefore, an admissible heuristic (which never overestimates the true distance to the goal) ensures that A* will always choose the optimal path.
However, in the graph-search version, A* may revisit nodes, and an admissible heuristic does not guarantee that the algorithm will not revisit a node with a higher cost than previously estimated. This can lead to non-optimal solutions.
A consistent heuristic, on the other hand, ensures that the estimated cost of reaching a node is always less than or equal to the true cost, even if the node is revisited. This property ensures optimality for the graph-search version of A*. Here's a simple example to illustrate this:
Suppose we have a graph with nodes A, B, and C, where A is the start node, C is the goal node, and h(A) = 2, h(B) = 1, and h(C) = 0. The true distances are d(A, B) = 2, d(B, C) = 1, and d(A, C) = 3.
If we use an admissible heuristic (h(n) ≤ d(n, goal)), the graph-search version of A* may expand node B first, then node A, and then revisit node B with a higher cost (3) than previously estimated (2). This can lead to a suboptimal solution.
On the other hand, a consistent heuristic would ensure that the estimated cost of reaching node B is always less than or equal to the true cost, avoiding this problem.
I hope this explanation helps clarify the difference!