Search code examples
algorithma-star

A star algorithm optimal path criteria

Does the A star algorithm return definitely the path with the less cost ? I'm running this algorithm and it proposes a path which doesn't have the minimum cost (I found another one with a less cost) Why does it propose this path and not the other ( with less cost)? Does it have other criteria to choose the proposed path in addition of the cost criteria? This is an exmaple of what I'm asking about the green path have less cost but the algorithm propose the orange one enter image description here

Solution

  • Does the A star algorithm return definitely the path with the less cost ?

    Yes, as long as you have used a consistent heuristic. If so, there are two options,

    1. Your A* implementation is wrong, therefore the algorithm returns a suboptimal path.
    2. The heuristic function you are using is not consistent, ie it does not give an estimation for each node which is smaller or equal to the real shortest path to the goal.

    It must be one of these two, since A* is proved to always find the optimal path whenever a consistent heuristic function is used.

    Imagine that the first node in the green path, which has cost 1 to be reached from A, has a heuristic value according to whatever function you are using of h(green_1) = 20. That value overestimates the real shortest path from that node to the goal node B, which is 6. Let me now assume the heuristic estimations of all nodes in the orange path correspond to the real shortest path from that node to B. Thus,

    f(green_1)= g(green_1) + h(green_1) = 1 + 20 = 21

    All f(n) values corresponding to the orange path will have smaller f(n) values and therefore green_1 will not be selected for expansion. The goal node will also be added to the OPEN list with f(B) = g(B) + h(B) = 11 + 0 and expanded, and since our heuristic has only promised us a path with cost 21 from the green side, which is worse than the already found orange path, the algorithm will finish and return the suboptimal solution.
    .