0
$\begingroup$

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.

enter image description here

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

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What if heuristic value at M is 20? Then its shorter than 30..will the heuristic still not be admissible then? $\endgroup$ – Pavindu Mar 10 '20 at 15:36
  • $\begingroup$ 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). $\endgroup$ – Zach Langley Mar 10 '20 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.