will a star always return the least cost path?

user_16376983 0
Viewed 295

I have been implementing a star recently on one of my pathfinding visualisers. A common thing that i have noticed is that while it does return the shortest path, it sometimes fails to return the least cost path. Now i am unsure as to if, this is due to some implementation error or if this is not a characteristic of the algorithm on a whole. For reference, these are the outputs of the a star and dijkstras algo respectively: enter image description here

dijkstar

So, why is this the case? (PS:the weights are 10, normal cost is 1 for any direction of movement and, the grey patches are walls)

path-finding a-star math algorithm
4 Answers

A* is optimal. It will always return the least-cost path. But the heuristic value must be admissible.

user_118194330

A* gives a correct result provided the heuristic gives a lower bound to the true cost. Every possible path must have cost higher or equal to the value provided by the heuristic. The algorithm becomes identical to Dijkstra's if you use a trivial heuristic that always gives the value 0.

user_17965790

A* may not return the least cost path, that is correct. This is a feature of A* though, not a disadvantage. To answer your question,

Why is it the case?

A* has a heuristics function that allows the algorithm to sacrifice accuracy for much higher performance by significantly reducing the area of search. This can be seen in your image too, where the Dijkstra's area of search is much wider. A* is often more useful in real-time games, where you don't necessarily need the lowest-cost path, as long as it is "good enough". Refer to this article for more examples. I find it explains A* very clearly in simple language.

As to what is "good enough", you define this using the heuristics function. Using different function will result in different behavior, allowing you to tune the algorithm to be optimal for your needs (depending on your playing field and accuracy requirement). You can also remove the heuristics, in which case it becomes simply the Dijkstra's algorithm. Refer to this article from the same site for some examples of heuristics.

user_11159510

To add to the correct answers by Md Asaduzzaman and Henry:

If the heuristic function is admissible, then A* tree search will always find the least cost path.

(source)


An admissible heuristic is optimistic is an optimistic one: the heuristic cost should be less than or equal to the actual cost.

In other words, if your implementation does not return the lowest cost path, consider changing the heuristic to an admissible one.

user_39929390
Related