CODEWITHSUNDEEP
grapha-starheuristics
Usman
Usman

Reputation: 901

A* search (non goal with 0 heuristic)

I have a graph and i need to apply A* algorithm on it. but this graph has a non goal with heuristic value 0. I am now confused if this is correct. Is it possible to have a non goal with heuristic value 0?

Upvotes: 3

Views: 3217

Answers (2)

templatetypedef
templatetypedef

Reputation: 372724

To take an extreme case, what happens if every node has a heuristic value of 0? In that case, you'll expand out nodes in increasing order of distance, and you essentially now have Dijkstra's algorithm instead of A* search.

It's always safe to have a heuristic value of 0 at a node in A* search, since the heuristic just has to underestimate the distance to the goal. Lower heuristic values cause A* to run longer, and higher (but still admissible) values make the algorithm take less time to find the goal.

Upvotes: 2

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

Yes that's fine. As long as the heuristic is admissible, A* will work.

However, your heuristic will not be consistent. This means that that the algorithm may run slower than you'd probably expect, because it may need to expand the same node multiple times.

Upvotes: 1

Related Questions