Googleマップへの不満

みんなが毎日使ってるGoogleマップ。目的地を入力すれば、あっという間に最短ルートを示してくれて、本当に便利ですよね。渋滞を避けたり、電車の乗り換えを考えたり、まるで魔法みたい。

ただし、時々すごく細い道や、「ここ通れるの？」という道を案内してくるときがあります。 Tetsuさんがよく文句を言っていたのを「ほーん」と何も考えずに聞いていました。

Tetsu

いや、ほんとそうなんだよ！この前も、クルマ一台がやっと通れるくらいの農道を案内されてさ。GoogleMapバカだよ。

最短経路アルゴリズム

最近、アルゴリズムを勉強する機会があり、なぜそのようなことが起きるのか何年越しに理解できました。ここであなたの最短経路センスへ挑戦状です！

以下のような経路図があるとします。各経路上の数字が次の地点までのコストです。スタートからゴールまで行くのに最短経路(コストが最も低い)はどうなるでしょうか。はい、考えて！！

graph LR
    A(スタート) -->|2| B; A -->|7| C;
    B -->|3| D; B -->|4| E;
    C -->|1| D; C -->|2| F;
    D -->|8| G;
    E -->|6| H;
    F -->|1| I;
    G -->|3| J;
    H -->|4| K(ゴール);
    I -->|1| J;
    J -->|1| K;

スタート → C → F → I → J → ゴール : 合計コスト 12

どうですか？解けましたか？15分以内で解けたあなたはShunより優秀です。すばらしい！おそらく全ての道のコストを計算して比較した結果最短のルートを暗算で導き出す優秀な脳を使ったんだと思います。

ではこれを現実世界に置き換えてみましょう。「全ての道はローマに通ず」と言いますが、世の中には目的地まで行くのにあらゆるパターンの経路がありますよね。これを今と同じような方法で全て計算して比較するのは現実的でしょうか。僕がやれと言われたら指示した人間をぶん殴ります。

ダイクストラ法

昔々、1959年にエドガー・ダイクストラというめちゃめちゃ賢い人間がおったそうな。彼は言いました。「すべての経路を計算するのがアホらしい？なら、もっと賢い方法で答えを見つければいいじゃない」。

彼が考え出した方法は、まさに革命的でした。総当たりで比較するのではなく、「スタート地点から近い順に、各地点までの最短距離を確定させていく」 というアプローチです。

イメージとしては、水面に石を投げたときの波紋が一番近いかもしれません。

まずスタート地点（石が落ちた場所）を「コスト0」で確定させる。
そこから一番近くにある地点（最初の波紋が届く場所）の最短距離を確定させる。
次に、確定した場所すべてから見て、一番近くにある未確定の地点の最短距離を確定させる。

これを繰り返すことで、計算量を爆発的に減らしながら、それでいて「絶対に最短経路である」と保証できる答えにたどり着けるのです。

では、この賢いアルゴリズムが、先ほどの意地悪な問題をどうやって解くのか、その思考プロセスを覗いてみましょう。

ステップ1：「安い方」と「高い方」

スタート(A)からの選択肢は、コスト「2」のBルートと、コスト「7」のCルート。アルゴリズムはまず、最も安いB（コスト2）を確定させ、そこからD（合計コスト5）とE（合計コスト6）への道を見つけます。

graph LR
    A(スタート);B;C;D;E;F;G;H;I;J;K(ゴール)
    A-->|2|B;A-->|7|C;B-->|3|D;B-->|4|E;C-->|1|D;C-->|2|F;D-->|8|G;E-->|6|H;F-->|1|I;G-->|3|J;H-->|4|K;I-->|1|J;J-->|1|K;
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style B fill:#f9f,stroke:#333,stroke-width:2px
    linkStyle 0 stroke:#0f0,stroke-width:4px;

ステップ2：罠への誘い

次に安いD（コスト5）、E（コスト6）を順に確定させ、その先のG（合計コスト13）、H（合計コスト12）への道を見つけます。ここまで、Bから始まるルートが順調に探索されています。 G（合計コスト13）、H（合計コスト12）よりスタートからC(合計コスト7)までのコストが低いため、いよいよ今まで放置されていたC（コスト7）の出番です。 Cからは、D（合計コスト 7+1=8）とF（合計コスト 7+2=9）へ行けます。ここで注目！アルゴリズムは、よりコストが低いDへ向かうルートを先にチェックします。 C→Fルートこそが正解への道なのに、一見安く見えるC→Dルートに先に進むのです。

graph LR
    A(スタート);B;C;D;E;F;G;H;I;J;K(ゴール)
    A-->|2|B;A-->|7|C;B-->|3|D;B-->|4|E;C-->|1|D;C-->|2|F;D-->|8|G;E-->|6|H;F-->|1|I;G-->|3|J;H-->|4|K;I-->|1|J;J-->|1|K;
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style B fill:#f9f,stroke:#333,stroke-width:2px
    style C fill:#f9f,stroke:#333,stroke-width:2px
    style D fill:#FFDAB9,stroke:#333,stroke-width:2px
    linkStyle 1 stroke:orange,stroke-width:4px;
    linkStyle 4 stroke:orange,stroke-width:4px;

ステップ3：罠からの脱出と逆転

アルゴリズムはC→Dルートを探索しますが、Dから先はG（合計コスト 8+8=16）となり、B経由のG（コスト13）より高いため、この道は捨てられます。罠は不発に終わりました。

ここでアルゴリズムは、Cから行けるもう一つの道、F（合計コスト9）を探索します！そして、F→I（合計10）、I→J（合計11）と、驚異的な追い上げが始まります。

Bから始まったどのルート（G経由もH経由も）よりも、このC→Fから始まるルートの方がJ地点に安く到達できることが判明しました！

graph LR
    A(スタート);B;C;D;E;F;G;H;I;J;K(ゴール)
    A-->|2|B;A-->|7|C;B-->|3|D;B-->|4|E;C-->|1|D;C-->|2|F;D-->|8|G;E-->|6|H;F-->|1|I;G-->|3|J;H-->|4|K;I-->|1|J;J-->|1|K;
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style C fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    style I fill:#f9f,stroke:#333,stroke-width:2px
    style J fill:#f9f,stroke:#333,stroke-width:2px
    linkStyle 1 stroke:#0f0,stroke-width:4px;
    linkStyle 5 stroke:#0f0,stroke-width:4px;
    linkStyle 8 stroke:#0f0,stroke-width:4px;
    linkStyle 10 stroke:#0f0,stroke-width:4px;

ステップ4：真の最短経路

最終的に、Jからゴールへコスト「1」で到達し、合計コスト12でゴール。これがこのマップの最短経路です。

スタート時点では最も高く、途中では罠のルートに気を取られながらも、最終的に最短経路を見つけ出す。これこそがダイクストラ法の真骨頂です。

graph LR
    A(スタート);B;C;D;E;F;G;H;I;J;K(ゴール)
    A-->|2|B;A-->|7|C;B-->|3|D;B-->|4|E;C-->|1|D;C-->|2|F;D-->|8|G;E-->|6|H;F-->|1|I;G-->|3|J;H-->|4|K;I-->|1|J;J-->|1|K;
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style C fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px
    style I fill:#f9f,stroke:#333,stroke-width:2px
    style J fill:#f9f,stroke:#333,stroke-width:2px
    style K fill:#f9f,stroke:#333,stroke-width:2px
    linkStyle 1 stroke:#0f0,stroke-width:4px;
    linkStyle 5 stroke:#0f0,stroke-width:4px;
    linkStyle 8 stroke:#0f0,stroke-width:4px;
    linkStyle 10 stroke:#0f0,stroke-width:4px;
    linkStyle 11 stroke:#0f0,stroke-width:4px;

まとめ

ダイクストラ法は、このようなアルゴリズムで不要な経路の計算量を排除し抑えることができるのです。 GoogleMapが細い道を示すのは現在地と目的地までの頂点の直近のコストが低いため優先して表示するのですね。 ※GoogleMapはダイクストラ法をさらに進化させたアルゴリズムを使っています

GoogleMapはバカだから細い道を案内してくれているわけではなく、寧ろスーパー賢いアルゴリズムで導き出されているんですね。 (道幅や路面状況などは計算対象に入ってないだろうと思うので直面直面で「え・・？」となるのはわかりますが。)

渡り鳥のスーパーナビゲーション

さて、ダイクストラ法という人間の作った素晴らしいアルゴリズムを見てきましたが、ここで視点を自然界に戻してみましょう。渡り鳥たちが何千年、何万年も前から実行しているナビゲーションは、人間のアルゴリズムが単純に見えてしまうほど、複雑で、動的で、そして美しいのです。

彼らがシベリアからオーストラリアまで、何千キロも旅をすることを想像してみてください。彼らの脳内で実行される「最適化計算」が考慮している「コスト」は、単なる距離だけではありません。

1. 究極の燃費計算：エネルギー消費

鳥にとって、長距離飛行の最大の敵は「エネルギー切れ」です。そのため、彼らは驚くほど高度な燃費計算を行います。

追い風を捉える: 彼らは単にまっすぐ飛ぶのではなく、上空の気流を読み、最も効率の良い追い風が吹いている高度やルートを選択します。少し遠回りになったとしても、追い風に乗った方が圧倒的にエネルギーを節約できることを知っているのです。これは、高速道路が多少遠回りでも一般道より早く着くのと似ていますね。
「無料」の上昇気流: ワシやタカ、コウノトリのような大型の鳥は、羽ばたきを最小限にするために「サーマル」と呼ばれる上昇気流を探し出して利用します。地面が太陽で暖められて発生するこの気流に乗って、まるでエレベーターのように高度を稼ぎ、そこから滑空して距離を伸ばすのです。まさに「コスト0」で移動する技術です。

2. 生存を賭けたリスク計算：安全性

最短経路が、必ずしも安全な経路とは限りません。鳥たちは、ルート上の潜在的な危険をコストとして計算に組み込んでいます。

天敵の回避: ある山脈を越えるのが最短距離でも、そこにハヤブサのような天敵が多く生息している場合、彼らは迂回してでも安全な平野部を飛ぶルートを選びます。これは、Googleマップが「治安の悪いエリア」を避けて案内してくれるようなものです（そんな機能はありませんが！）。
天候の予測: 鳥たちは気圧の変化に敏感で、嵐や悪天候のエリアを予測して回避します。悪天候の中を無理に飛ぶのは、エネルギーの無駄遣いであり、命の危険に直結するからです。

3. 完璧なタイミングでのピットイン：補給地点

長大な旅路の途中には、エネルギーを補給するための「ノード（中継点）」が不可欠です。しかし、鳥たちのすごいところは、その中継点の「状態」まで計算に入れていることです。

例えば、シギやチドリの仲間は、アラスカからニュージーランドへの数千キロの旅の途中、特定の干潟に立ち寄ります。なぜなら、その時期、その場所の干潟が、ちょうど潮が引いて餌が最も豊富になるタイミングであることを知っているからです。場所（ノード）だけでなく、「時間」という要素まで加えた、四次元的なナビゲーションと言えるでしょう。

4. 生まれつきの複合センサー：地形と磁場

そして、彼らはこれらをどうやって実現しているのか。鳥たちは、私たちにはない特殊な感覚を複数持っています。

視覚的な地図: 人間と同じように、海岸線や山脈、川の流れといった地形を目印にします。
太陽と星のコンパス: 昼は太陽の位置、夜は星々の配置から方角を正確に把握します。
地磁気コンパス: 最も驚くべき能力の一つが、地球の磁場を「見る」能力です。鳥の眼には「クリプトクロム」という特殊なタンパク質があり、これが磁場に反応することで、彼らは磁力線をまるで風景の一部のように認識できる、という説が有力です。VRゴーグルでナビが表示されているようなものでしょうか。

このように、渡り鳥のナビゲーションは、単一の最短経路を探すだけでなく、エネルギー、安全性、食料、時間、そして複数のセンサー情報をリアルタイムで統合し、生存確率が最も高くなる「最適解」を導き出す、超高度なアルゴリズムなのです。これって、Googleマップが目指すべき、究極の未来だと思いませんか？

自然から学ぶ「バイオミメティクス」

このように、自然の生物の仕組みを真似て、新しい技術を生み出すことを「バイオミメティクス」と呼びます。新幹線のパンタグラフにフクロウ、先端にカワセミなどは有名ですね。

鳥たちのナビゲーションは、まさに何百万年もかけて最適化された究極のアルゴリズム。もしかしたら、未来のナビアプリは、渡り鳥のルート選びを参考にして、「景色の良さ」や「歩きやすさ」なんていう新しい指標（コスト）まで考慮してくれるようになるかもしれませんね。

次にツバメや白鳥の群れが空を飛んでいるのを見かけたら、彼らが地球上で最も洗練されたナビアプリを使いこなす、ベテランパイロットなんだって思ってみてください。なんだか、ワクワクしませんか？

ちなみに僕の生態を技術に組み込んだら「今日はめんどくさいので出かけるのはやめましょう」と回答してくるナビアプリができるでしょう。

未来のナビシステムについて考えてみた