距離度量的信息

Question

您會如何考慮曼哈頓距離和切比雪夫？在搜索網格中從a到b的最短路徑方面，哪些信息更具知情性和可接受性？只允許水平和垂直移動？

Answer 1

曼哈頓距離是兩個獨立軸上距離的總和，Manhattan = |x_a - x_b| + |y_a - y_b|，而切比雪夫距離僅爲這兩個軸的最大值：Chebyshev = max(|x_a - x_b|, |y_a - y_b|)。所以，曼哈頓距離總是至少和切比雪夫距離一樣大，一般比較大。

在不允許在網格上進行對角線移動的情況下，兩個距離都是允許的（它們都沒有過高估計真實距離）。

鑑於兩個距離度量總是等於或小於真實距離，並且曼哈頓距離總是等於或大於切比雪夫距離，曼哈頓距離將總是至少與真值接近''。換句話說，在這個特定的情況下，曼哈頓距離將會更具信息性。

請注意，如果允許對角線移動，或者如果您不是在討論網格，則情況會有所不同。