4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

Imagine you're travelling from A to D:

Path 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.