Sign in to follow this  
athena

A* heuristic

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by Timkin
Actually, I'd prefer to say that if you omit the heuristic estimate from your cost function, A* reduces to greedy search.
Omitting heuristic reduces A* to Dijkstra, omitting path cost up to this point reduces A* to greedy search.

Share this post


Link to post
Share on other sites
Quote:
Original post by xor
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.
You should've believed fup. The "correction" is wrong.
Quote:
Original post by xor
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.
Exactly the opposite. A heuristic that underestimates (e.g. is zero like OP asked) will give you optimal paths, one the overestimates might not.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this