距離メトリックの正確性

Question

マンハッタン距離とチェビシェフは、グリッドの最短経路をaからbへと、水平方向と垂直方向の動きのみが許可されていることを知り、認めることはできますか？

Answer 1

マンハッタン距離は、2つの別々の軸上の距離の合計です。Manhattan = |x_a - x_b| + |y_a - y_b|ですが、チェビシェフ距離は、これらの2つの最大値です。Chebyshev = max(|x_a - x_b|, |y_a - y_b|)です。したがって、マンハッタンの距離は、少なくともチェビシェフの距離と同じくらい大きく、通常は大きくなります。

グリッド上での対角線移動が許可されていない場合は、両方の距離が許容されます（どちらも真の距離を過大評価するものではありません）。

両方の距離メトリックが常に真の距離以下であり、マンハッタン距離が常にチェビシェフ距離以上であるとすれば、マンハッタン距離は常に少なくとも「真実に近い」 ''。言い換えれば、マンハッタンの距離は、この特定のケースではより有益である。

斜め方向の移動が許可されている場合、またはグリッドについて話していない場合は、状況が異なる可能性があります。