地図アプリやカーナビでルート検索をすると、いちばん早い道がすぐに出ます。入れるのは、出発点と目的地だけです。町には交差点がたくさんあり、行き方は数えきれないほどあります。
地図アプリは、その中から、どうやって一瞬でいちばん早い道を見つけているのでしょうか。
小さな町の地図です。交差点が12個あり、道でつながっています。左下に出発点、右上に目的地の印があります。
光っている線が、いちばん早い道です。出発点と目的地をどこに置いても、光る道はすぐに出ます。
道の1本1本に、通るのにかかる分数を書きました。ここでは、道の長さではなく、かかる分数で比べます。
ある行き方にかかる時間は、通る道の分数を足した合計です。いちばん早い道は、この合計がいちばん小さい行き方です。
行き方Aは、8+2+4+3+1で18分です。行き方Bは、8+7+5+2+1で23分です。2つのうちでは、5分早いAが残ります。
全部の行き方の中で、合計がいちばん小さい行き方を、最短経路と呼びます。
最短経路を探すには、行き方を1本ずつ数えて、合計を比べればよさそうです。同じ交差点を2度通らない行き方を、1本ずつ重ねていきます。
この町の行き方は、全部で38通りあります。
地図の右に、交差点を縦に1列、3個足しました。38通りだった行き方が、125通りに増えます。
交差点が3個増えただけで、行き方は3倍あまりになりました。列を足すたびに、行き方はこうして何倍にも増えます。交差点の多い町で1本ずつ数えていたら、終わりません。
交差点Pに、2つの来かたが着きました。来かたAは、出発点から右へ進み、Pまで10分です。来かたBは、上へ進み、Pまで15分です。
Pから目的地までは、どちらの来かたも同じ道を通ります。4分、3分、1分と足していくと、Aは18分、Bは23分です。
両方に同じ数を足すので、差は5分のまま変わりません。Pに遅く着いたBは、この先どう進んでもAに追いつけません。
だから、交差点ごとに覚えておく数は1つで足ります。「出発点からここまで何分」の数を、交差点の札に書きます。
出発点の札は 0 です。すぐ隣の2つは、道の分数のまま 6 と 8 になります。ほかの札は、まだ空です。
Pの札には、はじめ上から来た 6+9 で 15 が書かれました。そこへ、右から来た 8+2 で 10 の来かたが見つかりました。
10 のほうが小さいので、札を 10 に書き直します。遅いほうの来かたの道は、もう覚えておかなくてかまいません。
まだ決まっていない札は、6 と 8 です。いちばん小さい 6 の交差点を、決まった色に変えました。
出発点の真上の交差点へは、6分より早く来る方法が無い、ということです。
6 の交差点へ、ほかの道から回る線を引きました。回り道は、札が 8 の交差点を通ります。そこに着いた時点で、もう8分です。
道の分数は、どれも 0 より大きい数です。8分から先へ足しても、6分より小さくはなりません。回り道の合計は19分です。だから、いちばん小さい札は、その数のまま決めてよいのです。
いま決まった 6 の交差点から、まだ決まっていない交差点へ、道が2本出ています。
6+3 で、上の交差点の札は 9 になります。6+9 で、右の交差点の札は 15 になります。
いちばん小さい札を決めて、隣の札を書き直す。これをくり返します。札が 8 の交差点が決まると、Pの札が 15 から 10 に書き直されます。
交差点に付いた番号は、決まった順番です。決まった色は、出発点から近い順に、波のように広がります。
目的地の札が 18 で決まり、ここで止めます。札を書き直すたびに、どこから来たかの矢印を残してありました。目的地から矢印を逆にたどると、18分の道が光ります。
この探し方を、考えた人の名前から、ダイクストラ法と呼びます。1959年に発表されました。
試してみよう
いちばん早い道の上の1本を、混んでいる道として色を変えました。いまは3分で通れます。
混んでいる道の分数も、ほかの道と同じように足します。いちばん早い道は18分で、目的地は10番目に決まります。
混んでいる道を20分にしました。前の18分の道は、35分に延びます。代わりに、下の道を回る23分の道が光ります。この道は、混んでいる道を通りません。
決まる順番も変わり、目的地が決まるのは12番目になりました。1本の道の分数が変わるだけで、いちばん早い道が変わります。
交差点が縦に18、横に24並んだ、大きな町です。交差点は432個あり、隣の交差点へは、どこも1分で動けます。
同じ探し方で、決まった色がひし形に広がります。1つの交差点を決めるのは1回だけなので、手間は多くても432回です。目的地が決まるまでに、408個が決まりました。
試してみよう
町の真ん中に、縦に壁を1本置きました。壁のマスは通れません。
いまは、出発点から目的地まで32分の道が光っています。決まった交差点は264個です。
壁の無いときの広がりを、薄い線で重ねました。決まった色は壁の手前で止まり、壁の端を回って広がります。
初めの壁1本のままなら、道は壁の端を回り、30分が32分に延びます。決まった交差点の数は、壁の置き方で増えることも減ることもあります。
1つの交差点から目的地まで、壁を無視して、マス目に沿った線を引きました。横に何マス、縦に何マスかを足した数が、「目的地まで少なくとも何分」です。
壁を回る本当の道は、それより長いか同じです。横と縦に離れた分だけは、どう回っても必ず動くからです。
すべての交差点に、「目的地まで少なくとも何分」の数を付けました。目的地に近いほど数が小さく、色が濃くなります。
どの交差点の数も、そこから壁を回って目的地へ行く本当の分数より大きくなりません。
札に、「ここまで」と「少なくとも何分」を足した値を出しました。今度は、この足した値がいちばん小さい交差点から決めます。
足した値が同じ札が、いくつも並びました。そのときは、「ここまで」の数がいちばん大きい交差点を選びます。出発点から遠く、目的地に近い交差点です。
試してみよう
足した値の順に決めると、決まった色は、目的地へ向かって細く伸びます。初めの壁1本のままなら、決まった交差点は129個です。近い順の探し方の264個の半分ほどです。
この探し方を、A*(エースター)と呼びます。1968年に発表されました。
目的地が決まったところで止めました。札に数が付いたまま、まだ決まっていない交差点があります。その足した値は、どれも目的地の札より小さくありません。
そのどれかを通る道の合計は、足した値より大きいか同じです。「少なくとも何分」が本当の残りより大きくならないからです。だから、近い順の探し方と道の形が違っても、合計の分数は同じです。
遊んでみよう
交差点が縦横6個ずつ並んだ、小さなマス目の町です。まだ決まっていない札には、「ここまで」と「少なくとも何分」の2つの数だけが書いてあります。
足した値の順に決めるとき、次に決まる交差点はどれでしょうか。3回続けて当てられるでしょうか。
1回目は、出発点の下の交差点です。1+5 で 6 です。上の交差点は 1+7 で 8 でした。2回目は、その右の交差点で、2+4 で 6 です。
3回目は、足した値が 8 の札が3つ並びます。「ここまで」の数は 1・2・3 で、いちばん大きい 3 の交差点が当たりです。
小さな町の行き方は、38通りありました。それでも決まった交差点は10個で、18分の道が見つかりました。
壁の無い大きな町の交差点は432個です。近い順の探し方では408個、足した値の順では31個を決めて、どちらも30分の道が見つかりました。