A* heuristic
Author
these questions are rather newbish I fear... sorry for that!
If time is not a constraining factor, can I drop the heuristic part when calculating the lowest cost for a given node?
is no heuristic better than a bad heuristic?
I read that its better to have the heuristic underestimate the distance compared to one that overestimate it, is it true?
Thanks in advances
If you don't use a heuristic you'll get a correct anwser. If you use an overestimating heuristic you can get a wrong anwser.
The better (closer to the true distance) the heuristic the faster you get the correct result.
The better (closer to the true distance) the heuristic the faster you get the correct result.
Quote:
If time is not a constraining factor, can I drop the heuristic part when calculating the lowest cost for a given node?
Yes you can, like fup said, you get a Dijkstra's search, wich will use a lot of cpu power compared to a A* with an heuristic.
Quote:
is no heuristic better than a bad heuristic?
Depends on what you mean by bad heuristic.
If by bad heuristic you mean an heuristic that might give you non optimal paths, then yes it is, if you mean an heuristic that might waste a lot of cpu power, then no it isn't.
Quote:
I read that its better to have the heuristic underestimate the distance compared to one that overestimate it, is it true?
Again depends, an heuristic that underoverestimates will hurt precision in favor of performance, an heuristic that overunderestimates, will hurt performance in favor of precision. An heuristic that overestimates will give you optimal paths, one that underestimates might not.
My personal sugestion is, if you don't care about how much time it takes to process each path, just calculate it using an underestimating heuristic, there is no need though to completely remove it.
[Edited by - xor on February 16, 2005 4:27:37 PM]
Quote:Original post by fup
if the heuristic cost = 0 then the A* search is equivalent to Dijkstra's search
Actually, I'd prefer to say that if you omit the heuristic estimate from your cost function, A* reduces to greedy search.
Timkin
Quote:Original post by TimkinOmitting heuristic reduces A* to Dijkstra, omitting path cost up to this point reduces A* to greedy search.
Actually, I'd prefer to say that if you omit the heuristic estimate from your cost function, A* reduces to greedy search.
Quote:Original post by xorYou should've believed fup. The "correction" is wrong.
Yes you can, like fup Timkin said, you get a Dijkstra's greedy search, wich will use a lot of cpu power compared to a A* with an heuristic.
Quote:Original post by xorExactly the opposite. A heuristic that underestimates (e.g. is zero like OP asked) will give you optimal paths, one the overestimates might not.
Again depends, an heuristic that underestimates will hurt precision in favor of performance, an heuristic that overestimates, will hurt performance in favor of precision. An heuristic that overestimates will give you optimal paths, one that underestimates might not.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
