Clever Geek Handbook

A * search (no target with 0 heuristic)

I have a graph and I need to apply the A * algorithm on it. but this plot has no target with heuristic value 0. Now I'm confused if this is correct. Is it possible to have a non-target value with a heuristic value of 0?

+3


source to share


2 answers


To accept an edge case, what happens if each node has a heuristic value of 0? In this case, you expand the nodes in ascending order of distance, and you essentially now have Dijkstra's algorithm instead of looking for A *.



It is always safe to have a heuristic of 0 when node is looking for A *, as the heuristic just has to underestimate the distance to the target. Lower heuristic values ​​make A * run longer, while higher (but still valid) values ​​make the algorithm take less time to find the target.

+2


source


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



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

+1


source






More articles:


All Articles