I believe using an overestimating heuristic with A* is not guaranteed to find the shortest path. Assuming an agent can travel as a bird using euclidean distances, the manhattan distance provides just such an overestimate; and hence is inadmissable. Can an example graph be provided wherein the use of A*, with a manhattan distance heuristic, can be shown to give a different result than it would by using the euclidean distance?
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
Imagine you're travelling from A to D:
The distance from A to C + the Manhattan distance from C to D (which is equal in this case to the distance from C to D) is less than the distance from A to B + the Manhattan distance from B to D.
I haven't included numbers, but hopefully this is apparent from looking at it -- the Manhattan distance from B to D is the equivalent of going down from B to C and then to D (assuming B and C line up on the vertical axis and C and D line up on the horizontal axis).
So, A* with Manhattan distance for the heuristic would return A->C->D, when it should return A->B->D
EDIT: In case anyone's wondering how we can be sure A->C->D is longer than A->B->D by just eyeballing it: angle B is wider than angle C (also eye-balling, unfortunately, but B is closer to A than C is to D, so hopefully that helps). So A->B->D is closer to a straight line than A->C->D. The shortest distance between two points is a straight line, so A->B->D is the shortest. By now you're probably wondering why I didn't just give each edge a length and be done with it -- and so am I.
