距离度量的信息性

Question

在只允许水平和垂直移动的网格中搜索从a到b的最短路径时，您如何考虑曼哈顿距离和切比雪夫？

Answer 1

曼哈顿距离是两个独立轴上的距离之和，而切比雪夫距离只是这两个轴上的最大值：Chebyshev = max(|x_a - x_b|, |y_a - y_b|)。因此，曼哈顿距离总是至少和切比雪夫距离一样大，通常更大。

在网格上不允许对角移动的情况下，这两个距离都是可接受的(它们都不会高估真实距离)。

假设两个距离度量始终等于或小于真实距离，而曼哈顿距离始终等于或大于契比雪夫距离，则曼哈顿距离将始终至少是“接近真实”。换句话说，在这种特定情况下，曼哈顿距离将提供更多信息。

请注意，如果允许对角移动，或者如果您不是在谈论网格，那么情况可能会有所不同。