カーナビ経路探索実験室
架空の街の道路網で、カーナビがルートを決める仕組みを観察。ダイクストラ法・A*・双方向探索を動かし、渋滞や通行止めでルートが変わる様子を確かめよう。
入力や実験結果は送信・保存しません。ページへの通常のアクセス記録は残ります。
1. 街の地図と道路状況
交差点が約500m間隔で並ぶ架空の街です。地図をクリックして、出発地・目的地の移動や、渋滞・通行止めの設置ができます（もう一度クリックで解除）。
2. ルートを探索する
ルート案内
表示のため、1フレームに数か所ずつ実際に探索を進めています。アニメーションの時間は計算速度ではありません。所要時間は上記の架空の速度から計算した値です。
3. 4つの探し方を一括比較
いまの地図・出発地・目的地・条件で、4方式をすべて最後まで計算します。「確定した交差点」が少ないほど、少ない手間でルートを決められたことを意味します。
| 探し方 | 確定した交差点 | 距離 | 所要時間 | 最適との差 | 最短の保証 |
|---|
カーナビは地図を「グラフ」として持っている
カーナビの地図データでは、交差点が点（ノード）、交差点どうしを結ぶ道路が線（リンク）です。それぞれの線には「長さ」「制限速度や平均速度」「一方通行」「右折できるか」などの情報が付いています。
ルート探索とは、線ごとにコスト（距離優先なら長さ、時間優先なら通過にかかる秒数）を決め、出発地から目的地までのコストの合計が最小になる線のつなぎ方を探す問題です。条件を変えるとコストの付け方が変わるので、同じ地図でも別のルートが選ばれます。
ダイクストラ法
出発地から「コストの合計が小さい順」に交差点を1つずつ確定していきます。確定した交差点から伸びる道を見て、隣の交差点までのコストが今の記録より小さければ書き換えます。目的地が確定した瞬間に、それが最小コストのルートです。
地図上では、出発地を中心に水たまりが広がるように確定が進みます。目的地と反対方向も同じように調べるので、手間は多めです。
A*（エースター）
「ここまでのコスト＋目的地までの見積もり」が小さい順に確定します。このページの見積もりは、時間優先なら「目的地までの直線距離 ÷ 最高速度80km/h」です。
見積もりが実際のコストを上回らない限り、最短のルートが保証されます。目的地の方向に細長く探索が伸び、確定する交差点が減ります。
双方向ダイクストラ
出発地（青）と目的地（ピンク）の両側から同時に探し、2つの探索が出会ったところでつなぎます。両側の「まだ確定していない最小のコスト」の合計が、見つけたルートのコスト以上になった時点で、それより良いルートはないと判断して終了します。
半径rの円2つは、半径2rの円1つより面積が小さいため、探索範囲が狭くなります。
簡易階層探索（近似）
出発地と目的地の近く（黄色い円）以外では一般道を使わず、幹線道路と高速道路だけで探します。人が地図を見るときの「近くの大通りに出て、高速に乗る」という考え方に近い方法です。
調べる交差点はさらに減りますが、裏道の近道を見落とすことがあり、最短の保証はありません。表の「最適との差」で確かめてみましょう。
実際のカーナビがしている工夫
日本全国の道路地図には、交差点が数千万か所あります。そのままダイクストラ法をかけると時間もメモリも足りないため、一般に知られている手法として次のような工夫が組み合わされます。メーカーごとの細かな実装は公開されていない部分も多く、ここで紹介するのは代表的な考え方です。
- 道路の階層化と事前計算：地図を道路の格に応じて階層に分け、遠くでは上位の道路だけを探します。研究・Web地図の分野では、事前に「近道（ショートカット）」を計算しておく Contraction Hierarchies などが知られており、大陸規模でも短時間で最短経路を求められます。
- 右左折・信号・Uターンのコスト：交差点を曲がる動作にも時間のコストを付けます。対向車を待つ右折は、左折より重くするのが一般的です（このデモでは省略）。
- 渋滞情報と予測：道路交通情報（VICSなど）や、走行中の車から集めたプローブ情報で、道路ごとの通過時間を更新します。過去の統計から「出発時刻に応じた混み具合」を予測に使うこともあります。
- リルート（再探索）：ルートを外れたり、新しい渋滞情報が届いたりすると、現在地から探し直します。上の「事故渋滞」ボタンで渋滞を置いてから探索し直すと、同じことを体験できます。
- ルートの「使いやすさ」：最小コストだけでなく、細い道・生活道路を避ける、有料道路の料金を考える、複数の候補ルートを並べて選ばせる、といった調整も行われます。
このデモでの単純化
速度は一般道30km/h・幹線道路50km/h・高速道路80km/hで一定、渋滞は通過時間を3倍にするだけです。一方通行、右左折のコスト、信号待ち、料金、時間帯による変化は含みません。街は乱数から作った架空の地図で、実在の地図データは使っていません。
ダイクストラ法の手順（擬似コード）
コスト[出発地] = 0、それ以外 = ∞
候補リスト = {出発地}
候補リストが空でない間:
u = 候補リストでコスト最小の交差点を取り出す
u が確定済みなら次へ
u を確定する
u が目的地なら終了（記録をたどればルートになる）
u から伸びる道 (u→v, 道のコスト c) それぞれについて:
コスト[u] + c < コスト[v] なら
コスト[v] = コスト[u] + c、ひとつ前[v] = u
v を候補リストに入れる
A* は「取り出す順番」を コスト[v] + 見積もり(v→目的地) に変えるだけ。