1 定義
マンハッタン距離は、各座標軸に沿った移動量の合計で二点間の隔たりを表す距離である。格子状の街路を進む移動にたとえられることから、この名で広く知られている。平面だけでなく、高次元空間でも自然に定義でき、成分ごとの差を基礎にするため、計算が単純で解釈もしやすい。
1.1 一般的な定義
n 次元の点 x=(x1, x2, …, xn) と y=(y1, y2, …, yn) の間のマンハッタン距離は、各成分の差の絶対値を足し合わせたものとして定義される。つまり、各方向にどれだけ動いたかを個別に測り、その総和を距離とみなす。
1.2 座標ごとの差の絶対値による表現
| この距離は、 | x1−y1 | + | x2−y2 | +…+ | xn−yn | という形で表される。符号の違いは絶対値によって打ち消されるため、方向ではなく変化量そのものが重視される。座標系における各軸の寄与が明示的で、データの解釈にも適している。 |
|---|
1.3 距離関数としての性質
マンハッタン距離は、距離関数に求められる基本的な公理を満たす。そのため、単なる計算式ではなく、数学的に整った距離空間を構成する要素として扱える。
1.3.1 非負性
距離の値は常に 0 以上である。絶対値の和で構成されるため、負の値になることはない。
1.3.2 同一性
二点が完全に一致するとき、距離は 0 になる。逆に、距離が 0 であれば各成分の差がすべて 0 であり、点は同じ位置にある。
1.3.3 対称性
x と y の順序を入れ替えても距離は変わらない。各成分の差は絶対値で扱われるため、向きによる違いが生じない。
1.3.4 三角不等式
ある点を経由して移動する距離は、直接結ぶ距離より短くならない。これは絶対値の和に関する基本性質から導かれ、距離空間としての整合性を支えている。
2 幾何学的性質
マンハッタン距離は、ユークリッド距離とは異なる形の等距離集合を生む。軸に平行な移動を重ねるため、見かけ上の対称性や球面の形が独特になる。
2.1 平面における形状
平面では、ある点から一定距離にある点の集合は菱形になる。これは、水平・垂直方向の移動を組み合わせたときに、境界が直線的な辺で構成されるためである。
2.2 高次元空間における等距離集合
高次元では、等距離集合は多面体的な形状を示す。各軸方向の制約が重なり合い、滑らかな曲面ではなく、面と稜を持つ境界が現れる。
2.2.1 菱形と多面体
二次元では菱形、三次元以上ではその高次元版に相当する多面体が距離 1 の集合を表す。軸ごとの寄与が等しく扱われるため、各面は座標軸に対応した平坦な構造をとる。
2.2.2 球面との比較
ユークリッド距離の球面が円や球として現れるのに対し、マンハッタン距離の等距離集合は角張った輪郭をもつ。両者は「同じ距離」の定義の違いによって、幾何学的印象が大きく変わる。
2.3 直線距離との違い
直線距離は二点を最短の一直線で結ぶ長さだが、マンハッタン距離は軸に沿った折れ曲がりの経路を前提とする。したがって、同じ二点でも一般にマンハッタン距離のほうが大きいか等しく、両者の差は空間の構造に依存する。
3 計算方法
マンハッタン距離は、座標差の絶対値を順に求めて加算するだけなので、計算手順は比較的明快である。実装面でも扱いやすく、大規模なデータにも適用しやすい。
3.1 二次元での求め方
| 二点 (x1, y1) と (x2, y2) の距離は、 | x1−x2 | + | y1−y2 | で求められる。まず各軸の差を取り、それぞれを絶対値に変換し、最後に加えるだけでよい。 |
|---|
3.2 高次元での求め方
高次元でも基本は同じで、対応する成分の差の絶対値をすべて合計する。次元が増えても手順は一定で、各方向の寄与を独立に集計できる点が特徴である。
3.3 座標変換との関係
座標変換を行うと、マンハッタン距離の見え方は変わる場合がある。特に回転を加えると、軸に沿った測り方が前提なので、直感的な形状や値の解釈が変化しやすい。直交的な座標系との相性が良い一方で、一般の変換では単純さが失われることがある。
4 応用
マンハッタン距離は、離散的な構造や成分比較を扱う場面で有用である。計算負荷が低く、軸ごとの差分を直接反映できるため、理論研究と実務の双方で利用される。
4.1 格子上の経路計算
都市の街路や格子状の盤面では、上下左右にしか進めない状況が多い。このような環境では、移動回数や歩数の見積もりにマンハッタン距離が自然に対応する。
4.2 最適化問題
最適化では、目的関数や制約に絶対値項が含まれることがある。マンハッタン距離はそのような問題の評価尺度として働き、解の探索や誤差の抑制に役立つ。
4.3 情報検索と近傍探索
検索や推薦の分野では、対象同士の近さを測る基準として使われる。多次元特徴を持つデータでも計算が容易で、候補の順位付けや近傍抽出に向いている。
4.4 機械学習における利用
機械学習では、距離に基づく分類や異常検知で参照されることがある。外れ値の影響を受けにくい場面もあり、データの性質に応じて有効な選択肢となる。
4.4.1 特徴量比較
複数の特徴量をもつ対象を比べる際、各成分の差をそのまま積み上げられる。これにより、どの属性がどれだけ違うかを把握しやすい。
4.4.2 類似度評価
距離が小さいほど類似しているとみなす評価法で用いられる。数値の増減を素直に反映するため、解釈のしやすさが利点となる。
5 関連する距離
マンハッタン距離は、距離の一族の中で特定の p 値に対応する例として位置づけられる。比較対象を知ることで、その特徴がより明瞭になる。
5.1 ユークリッド距離
ユークリッド距離は、二点間を直線で結ぶ長さに対応する。滑らかな回転対称性をもち、最短経路の自然なモデルとして広く知られている。
5.2 チェビシェフ距離
チェビシェフ距離は、各成分差の最大値で定義される。すべての軸を同時に意識するのではなく、最も大きいずれを重視する点が特徴である。
5.3 ミンコフスキー距離
ミンコフスキー距離は、絶対値の p 乗の和から定義される一般形である。p=1 がマンハッタン距離、p=2 がユークリッド距離に対応し、両者を統一的に見る枠組みを与える。
5.4 一般化された距離空間
距離空間は、距離の公理を満たす集合の構造を指す。マンハッタン距離はその代表例の一つであり、抽象的な空間論の中でも具体的な標本として扱われる。
6 歴史
マンハッタン距離の考え方自体は、座標ごとの変化を足し合わせるという単純な発想に根ざしている。名称や位置づけは、応用の広がりとともに定着していった。
6.1 名称の由来
名称は、碁盤目状に区画された都市の街路網を連想させることに由来する。直進と折れ曲がりを繰り返す移動様式が、格子上の経路に似ているためである。
6.2 数学的発展
距離の公理化やノルム空間の研究が進む中で、マンハッタン距離は形式的に整理された。絶対値和の構造は解析学、幾何学、統計的手法の各分野で再解釈され、理論的基盤が整えられた。
6.3 現代における位置づけ
現在では、幾何学の基本概念であると同時に、計算機科学やデータ分析でも実用的な尺度として認識されている。単純な式でありながら、格子構造や高次元データに適した性質を備えている点が評価されている。