CODEWITHSUNDEEP
artificial-intelligence
Jason Per
Jason Per

Reputation: 149

Informedness of distance metrics

How would you consider Manhattan distance and Chebyshev in terms of which is more informed and admissable in searching the shortest path in a grid from a to b, where only horizontal and vertical movements are allowed ?

Upvotes: 0

Views: 204

Answers (1)

Dennis Soemers
Dennis Soemers

Reputation: 8478

The Manhattan distance is the sum of the distances on the two separate axes, Manhattan = |x_a - x_b| + |y_a - y_b|, whereas the Chebyshev distance is only the maximum of those two: Chebyshev = max(|x_a - x_b|, |y_a - y_b|). So, the Manhattan distance is always at least as big as the Chebyshev distance, typically bigger.

In the case where diagonal movement on a grid is not allowed, both of the distances are admissible (neither of them ever overestimates the true distance).

Given that both distance metrics are always equal to or smaller than the true distance, and the Manhattan distance is always equal to or greater than the Chebyshev distance, the Manhattan distance will always be at least as ''close to the truth''. In other words, the Manhattan distance will be more informative in this specific case.

Note that if diagonal movement is allowed, or if you're not talking about a grid, then the situation can be different.

Upvotes: 1

Related Questions