3 ms·

In my first bit of play, I just tried to find cases where Manhattan lost to the others. It seems like Manhattan is not as good when faced with a plausible path

by jMyles 12y ago

In my first bit of play, I just tried to find cases where Manhattan lost to the others. It seems like Manhattan is not as good when faced with a plausible path only to be thwarted at the end - is this right? Can you show a few cases where Manhattan loses by a landslide?

roryokane 12y ago
Manhattan is a heuristic for measuring distance, not an algorithm to find a path, so I wouldn’t really say it “loses”, rather it “is less applicable”. Manhattan, Euclidean, and Chebyshev are all just different ways of measuring distance (https://en.wikipedia.org/wiki/Taxicab_geometry https://en.wikipedia.org/wiki/Taxicab_geometry, https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance, https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance). Each algorithm uses the heuristic to measure how promising each possible path is (how close each path is to the goal according to that definition of distance, ignoring walls), and prioritizes the most promising paths. Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.
- jMyles 12y ago
  I have found one example where Euclidean wins: http://imgur.com/FgQ04k0 http://imgur.com/FgQ04k0
applekor 12y ago
Because Manhattan distance isn't an admissible heuristic for an 8-connected grid I think it breaks the A*'s guarantee of optimality. I don't have an example, but it might be a place to start looking.

by jMyles 12y ago

roryokane 12y ago

Manhattan is a heuristic for measuring distance, not an algorithm to find a path, so I wouldn’t really say it “loses”, rather it “is less applicable”. Manhattan, Euclidean, and Chebyshev are all just different ways of measuring distance (https://en.wikipedia.org/wiki/Taxicab_geometry https://en.wikipedia.org/wiki/Taxicab_geometry, https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance, https://en.wikipedia.org/wiki/Chebyshev_distance https://en.wikipedia.org/wiki/Chebyshev_distance). Each algorithm uses the heuristic to measure how promising each possible path is (how close each path is to the goal according to that definition of distance, ignoring walls), and prioritizes the most promising paths. Based on those definitions, I would guess that “Chebyshev” distance is almost always the most accurate heuristic to use when you check “Allow Diagonal”, because it will always be perfectly accurate if there are no walls in the way, unlike the others. Similarly, when “Allow Diagonal” is unchecked, “Manhattan” distance is the most accurate. And “Euclidean” distance is always the least accurate in this demo, because in this demo, paths are always constrained to 45° or 90° turns so that they stay on the grid, whereas Euclidean distance assumes that it is possible to move at arbitrary angles like 18.2° right from east.

jMyles 12y ago
I have found one example where Euclidean wins: http://imgur.com/FgQ04k0 http://imgur.com/FgQ04k0

applekor 12y ago

Because Manhattan distance isn't an admissible heuristic for an 8-connected grid I think it breaks the A*'s guarantee of optimality. I don't have an example, but it might be a place to start looking.