# Why doesn't A* give the optimal path for navigating from A to R in this state space?

Well, I have heard that the A* algorithm is optimal and complete. However, when trying to navigate from A to R using A*, it outputs the path, A --> E --> R, although there is a shorter path, A --> M --> R. My question is, is that possible for A* to be not optimal sometimes? if not, what am I doing wrong here? Any helpful advice is highly appreciated.

The question: In the following diagram, A is the start node and R is the goal node. Arcs are labeled with the value of the cost function; the number gives the cost of traversing the arc. Heuristic function value for each node is given within brackets. Using A*, find the route from A to R.

This is what I tried. But what I'm getting is not the optimal path.

## 1 Answer

For A* to be optimal, the heuristic needs to be admissible (and this example shows why). This heuristic is not admissible because the heuristic value at M is 40, while the shortest path from M to R has length 30.

• What if heuristic value at M is 20? Then its shorter than 30..will the heuristic still not be admissible then? Mar 10, 2020 at 15:36
• It will still not be admissible because there are still paths from other nodes whose value is not underestimated by the heuristic (e.g., D -> R). Mar 10, 2020 at 21:34