# 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 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 on other sites
quick and precise answer, I thank you much.

##### Share on other sites
if the heuristic cost = 0 then the A* search is equivalent to Dijkstra's search

##### 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 on other sites
Quote:
 Original post by fupif 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 on other sites
Quote:
 Original post by TimkinActually, 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 on other sites
Quote:
 Original post by xorYes 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 xorAgain 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628383
• Total Posts
2982371

• 10
• 9
• 15
• 24
• 11