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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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, 2020 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, 2020 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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