マンハッタン距離

提供: miniwiki
2018/8/19/ (日) 17:28時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索
ファイル:Manhattan distance bgiu.png
マンハッタン距離の例: どの色のコースを辿っても同じ距離が決まっている

マンハッタン距離(マンハッタンきょり、Manhattan distance)またはL1-距離は、幾何学における距離概念のひとつ。各座標の差(の絶対値)の総和を2点間の距離とする。

ユークリッド幾何学における通常の距離ユークリッド距離)に代わり、この距離概念を用いた幾何学はタクシーの幾何 (taxicab geometry) と呼ばれる。19世紀ヘルマン・ミンコフスキーによって考案された。

定義

より形式的には、2点間の距離を直交する座標軸に沿って測定することで一般の [math]n[/math] 次元空間においてマンハッタン距離 [math]d_1[/math] が定義される。

[math]d_1(\mathbf{x},\mathbf{y}):=\sum_{k=1}^n|x_k-y_k|.[/math]

ただし、[math]\mathbf{x} := (x_1, x_2, ..., x_n), \mathbf{y} := (y_1, y_2, ..., y_n)[/math] とおいた。例えば、平面上において座標 [math](x_1, y_1)[/math] に置かれた点 [math]P_1[/math] と、座標 [math](x_2, y_2)[/math] に置かれた点 [math]P_2[/math] 間のマンハッタン距離は

[math]|x_1 - x_2| + |y_1 - y_2|[/math]

となる。

マンハッタン距離は、都市ブロック距離(city block distance, 市街地距離)としても知られている。マンハッタン距離の名は、マンハッタンのような正方形のブロックに区分された都市で、自動車が運転される距離に由来する。ある角から東に 3 ブロック、北に 6 ブロックの位置にある角まで移動するには、いかなる経路を辿っても最低 9 ブロックを通過せねばならない。

チェスでは、ルークにとってのマス間の距離はマンハッタン距離によって測られる(キングクイーンビショップチェビシェフ距離を用いる)。