ホーム › Googleマップはなぜ爆速で最短経路が分かるの？
ゆるラジオindex 編集部より
Googleマップは、なぜあんなに速く最短経路を出せるのでしょうか。
ダイクストラ法という考え方を、実際に手で解きながら理解していきます。数学的帰納法での説明までたどり着きます。
地図が階層に分かれている、という工夫も顔を出します。
この回の内容
- 0:00Googleマップの中身を理解しよう
- 1:18最短経路問題を解くGoogleマップ
- 6:52ダイクストラ法で解いてみよう
- 13:55数学的帰納法で説明できる
- 18:48ダイクストラ法は応用されている
- 22:59階層化された地図
- 32:54アルゴリズムは人の直観に近づく
- 34:38パワーアップした「パスカル」お試しください
この回に出てくる言葉
番組でくり返し語られる言葉です。押すと、その語が話題になった回が並びます。
この回で紹介された本・参考文献
- ダイクストラ法Dijkstra’s Algorithm
- アルゴリズムとデータ構造
- アルゴリズム図鑑
- From A to B: Algorithms That Power Google Maps Navigation
- Routing Faster Than Dijkstra Thanks to Contraction Hierarchies