マンハッタン距離ヒューリスティックは、おそらく歴史上最も広く使われたヒューリスティック探索手法です。1960年代に15パズルのために非公式に導入され、1968年のA*論文で形式化され、今もすべてのAI教科書が最初に教えます。本記事では、なぜ機能するのか、何が得意か、そしてどこで限界を迎えるかを解説します。
定義
N×Nのスライドパズルにおいて、各タイル（空きマスは除く）について以下を計算します：
距離 = | 現在行 − ゴール行 | + | 現在列 − ゴール列 |
すべてのタイルの値を合計したものが、現在の盤面のゴールからのマンハッタン距離です。
なぜ「マンハッタン」なのか？マンハッタンの街路は規則的なグリッドです。ある交差点から別の交差点へ移動するには、東西にいくつかのブロック、南北にいくつかのブロックを歩きます。斜めには進めません。歩いたブロック数の合計がマンハッタン距離——タクシー距離またはL¹ノルムとも呼ばれます。
タイルも同じ論理です。1回の移動で上下左右に1マスだけ動けて、斜めには動けません。現在位置からゴール位置まで到達するのに必要な最小手数は、行方向の距離と列方向の距離の和です。
許容性（Admissibility）
Aがヒューリスティックに要求する条件が許容性です。実際の残り手数を決して過大評価してはいけないということです。ヒューリスティックが過大評価すると、Aは最適経路を早期に切り捨てて最適でない解を返す可能性があります。
マンハッタン距離が許容性を持つ理由：
- 各タイルは少なくとも行方向の距離＋列方向の距離だけ移動しなければなりません。なぜなら手は行または列の1マス移動だからです。
- すべてのタイルを合計しても超過しません。なぜなら1回の手で1つのタイルがちょうど1マス進むからです（空きマスも動きますが、カウントしません）。
- 実際の距離はマンハッタン距離以上です。なぜなら他のタイルが通路を塞いで迂回が必要になることがあるからです——しかし以下になることはありません。
したがってマンハッタン距離 ≤ 実際の距離。許容性あり。
一貫性（Consistency）
より強い性質が一貫性（単調性とも呼ばれます）です。ヒューリスティックが一貫性を持つのは、すべての状態sと手mによる後継状態s'について以下が成り立つときです：
h(s) ≤ cost(m) + h(s')
日本語で言えば：1手を指したとき、ヒューリスティック値は1以上下がらないということです。
マンハッタン距離が一貫性を持つ理由：1回の手でマンハッタン距離はちょうど+1か−1変化します（1つのタイルが1マス動くのでその寄与が±1変化し、他のタイルの寄与は変わりません）。
一貫性が重要な理由：A*が一度クローズした状態を再オープンしないことが保証されます。実装は非一貫性のケースを処理する必要がなく、コードと証明が単純になります。
実用上なぜこれほど優れているか
3つの具体的な特性：
計算コストが低い。 盤面1つあたりO(N²)——すべてのタイルを合計し、各タイルの計算は定数時間。現代のコンピュータではh(s)の計算はマイクロ秒で終わります。
深く枝刈りできる。 15パズルにおいて、マンハッタン距離の値は実際の距離の平均75〜90%です。これほど精度の高いヒューリスティックを使ったA*は、状態空間のごく一部しか探索しません。
線形コンフリクトとの相性が良い。 「線形コンフリクト」（同じ行にある2つのタイルが、その行に属すべきだが逆順になっている）ごとに2手を加えると、わずかな計算コストで厳密に精度の高いヒューリスティックになります。
限界
マンハッタン距離はタイルが互いをすり抜けられるかのように扱います。実際にはすり抜けられません。最大の盲点：
行または列内のコンフリクト。 タイル2と3が同じ行1にあって逆順になっている場合、マンハッタン距離は直線距離だけを見て何も気づきません。実際には一方をいったん行外に出し、もう一方を通過させ、最初のタイルを戻す必要があります。少なくとも2手余分にかかりますが、マンハッタンはそれを見逃します。線形コンフリクトがこれを補います。
「ウォーキング」構造。 マンハッタン距離は、行や列にすべて属すべきタイルが同じ行・列に揃っているときの相互関係を無視します。4枚のタイルが誤った順番で並んでいる場合、複数の「行スワップ」が必要になります——この構造をウォーキング距離が捉えます。
互いに素な部分集合の相互作用。 タイルをどのように分割しても、各部分を正しく並べる最適コストの合計はマンハッタン距離（タイルを1枚ずつの集合に分割した場合）より厳密な下限となります。加算パターンデータベースがこれを活用します。
改善の系譜は：マンハッタン距離 → マンハッタン距離＋線形コンフリクト → ウォーキング距離 → パターンデータベース。各段階が厳密な改善です。
大きな盤面でより多くが必要な理由
マンハッタン距離は15パズルの実際の距離の平均約75〜90%です。24パズルでは約65%、35パズルでは約55%になります。
理由：盤面が大きくなるにつれ、タイルのコンフリクトと「ウォーキング構造」が直線距離に対してより重要になります。両方を無視するマンハッタン距離は、大きな盤面ほど大きく過小評価します。
これが、24パズルや35パズルの解法でパターンデータベースが事実上必須となる理由です。マンハッタン距離は15パズルと8パズルには十分ですが、それより大きなサイズでは情報損失が大きすぎます。
幾何学的な直観
マンハッタン距離を直感的に理解するには：平面の上にタイルが1枚置かれていると想像してください。そのタイルがk手で到達できる点の集合は、辺の長さがkのダイヤモンド形（マンハッタン距離≤kの点）になります（ユークリッド距離なら半径kの円に対応）。
マンハッタン距離はグリッド移動の自然な幾何学です。グリッドのステップに制約された移動モデルを持つとき、マンハッタン距離が正しい幾何学であり、ユークリッド距離は無関係です。
アプリ開発者への示唆
ミリ秒以内に動作するヒントボタンをスライドパズルアプリに実装するなら：
- 3×3 — マンハッタン距離＋線形コンフリクトで十分。A*が探索する状態数は数十、マイクロ秒で完了。
- 4×4 — マンハッタン距離＋線形コンフリクトはヒント（最適解全体ではなく次の1手）には十分高速。最適解全体が必要なら、ウォーキング距離が適切。
- 5×5以上 — パターンデータベース必須。マンハッタン距離ではヒントボタンの時間予算に収まりません。
Slide Puzzleは、3×3と4×4のヒントボタンにマンハッタン距離＋線形コンフリクトを使い、4×4の難易度調整にウォーキング距離を使い、5×5・6×6の調整には5+5+5+9パターンデータベースを使っています。マンハッタン距離ヒューリスティックはそのすべての基盤です。
最後の直観
マンハッタン距離ヒューリスティックは、スライドパズルを探索可能にする存在です。これがなければ、AもIDAもBFSに退化します——そしてBFSでは15パズルを宇宙の寿命以内に解くことはできません。
そのヒューリスティックが、手に負えない問題をミリ秒の計算に変える一行のコードです。深く理解する価値があります。