# Thread: A* heuristic estimate question

1. ## A* heuristic estimate question

Hi! I recently read the wikipedia article about the A* search algorithm, which is basically a generalization of Dijkstra's algorithm, which also takes a heuristic function (called h) to evaluate the distance from a node to the goal (in Dijkstra's this heuristic would always be 0). However the algorithm requires the heuristic function to be admissible, i.e. the estimated cost of getting to the goal may never be greater than the actual cost of getting to the goal.

What I wonder about, doesn't the heuristic function have to be consistent as well? I.e. the decrease in the heuristic estimate when moving one step cannot be greater than the actual cost of taking that step. However, it says on wikipedia that the heuristic just has to be admissible for the algorithm to return an optimal path.

Burt what about this example?

Here, the heuristic function is admissible, since it never overestimates the cost of getting to the goal (although it's not consistent). Yet, i my opinion, the A* algorithm would take the suboptimal path here (the lower path), since it thinks the heuristic evaluation there (that in node C) is much more optimistic than in the upper path given in node B.

Am I right or wrong?

2. I'm not claiming any expertise here, never having wanted to solve this type of problem in a real program. Clearly, if the algorithm fails for your example, which it certainly looks like it might, then either the claim that the heuristic only needs to be admissible is wrong, or you understanding of what it means to be admissible is not correct, or possibly you are not meant to have 0 cost paths. The wikipedia article you link to seems to imply there is more to both the algorithm and the function f(x) than just your heuristic. If I were you I would take the trouble to implement the algorithm - the Wikipedia pseudo-code looks like a good basis, and there look to be links to C++ implementations.

In my experience one gets a much better understanding of a complex algorithm by really implementing it and tracing through the decisions made by the computer than by trying to work through an example in one's head, because it is all too easy to make a mistake that way. Often you will find the computer does something you did not expect, and when you come to study it you will find there was a flaw in your understanding.