マンハッタン距離

ウィキペディア

マンハッタン距離

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/05 01:52 UTC 版)

マンハッタン距離の例：どの色のコースを辿っても同じ距離が決まっている

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

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

定義

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

$d_{1}({\boldsymbol {x}},{\boldsymbol {y}}):=\textstyle \sum \limits _{k=1}^{n}|x_{k}-y_{k}|.$

ただし、 ${\boldsymbol {x}}:=(x_{1},x_{2},\cdots ,x_{n})$, ${\boldsymbol {y}}:=(y_{1},y_{2},\cdots ,y_{n})$ とおいた。例えば、平面上において座標 $(x_{1},y_{1})$ に置かれた点 $P_{1}$ と、座標 $(x_{2},y_{2})$ に置かれた点 $P_{2}$ 間のマンハッタン距離は

$|x_{1}-x_{2}|+|y_{1}-y_{2}|$

となる。

例

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

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

外部リンク

• 『L1距離（マンハッタン距離）の意味と性質』 - 高校数学の美しい物語