最短経路

1956年、オランダ。若い研究者が、婚約者と買い物の途中、喫茶店でひと休みしていました。

コーヒーを飲みながら、紙もペンも使わずに、20分ほどで、ある方法を思いつきます。それが、いまも、地図アプリの奥で動いています。

家から駅まで、いちばん近い道は。全部の道順を試せば、答えは出ます。

ただ、碁盤の目の街を、20ブロック四方、遠回りせずに斜めに横切るだけで、道順は、計算すると、およそ1400億通り。全部は、試せません。

喫茶店で生まれた方法は、こうです。出発点から、いちばん近い交差点を、ひとつ確定する。次に近い交差点を、確定する。

水が、低いほうから順に広がるように、近い所から、確実に塗りつぶしていく。ゴールに届いたとき、それが最短です。

遠回りは、最初から調べない。だから速い。考案者の名前から、ダイクストラ法と呼ばれます。

ただ、これだと、ゴールと反対の方向にも、律儀に広がってしまいます。1968年、改良版が出ました。ゴールの方角を、少しだけ、ひいきする。

さらに、道には格があります。遠くへ行くなら、路地より幹線道路。先に近道の表を作っておく工夫で、数百万の交差点がある道路網でも、答えは、1万分の1秒ほどで出ます。

でも、知りたいのは、距離より、時間です。道は、混みます。

そこで、今の混み具合と過去の傾向から、この先の渋滞を予測する。2020年には、AIを使って、到着時刻の予測の精度を、都市によっては最大で5割改善した、と報告されました。東京も、対象です。

ちなみに、衛星で位置を知るカーナビを、世界で初めて売り出したとされるのは、日本のメーカーです。1990年ごろのことです。

ただし、「最短」と「最適」は、違います。アプリが全員に同じ抜け道を教えると、静かな住宅街が、渋滞します。

アルゴリズムが見ているのは、あなたの到着時刻だけ。道ばたで遊ぶ子どもは、計算に入っていません。

20分の思いつきが、70年たったいまも、世界中の道案内を支えています。

いい考えは、案外、休憩中に来ます。行き詰まったら、コーヒーをどうぞ。最短で届くかは、保証しませんが。