Googleマップの秘密の経路探索アルゴリズムを10年かけて理解した話
Differential Heuristics
2007年にGoogleマップが導入したドラッグで経路を再計算する機能は、当時の技術では驚異的でした。著者はその裏にある「差分ヒューリスティックス」という最適化手法を理解しようと、2015年から断続的にチュートリアル執筆を試みますが、納得のいく説明ができず、2024年に学習と実験に切り替えます。その結果、ヒューリスティックを矢印で視覚化する新しい説明方法を考案し、改善領域の可視化も追加しました。本記事は、この手法の解説ページ公開までの試行錯誤と、理解を深めるプロセスを綴っています。
「私はアルゴリズムを理解してはいたが、教えられるほど十分には理解していなかった」
- plomme
Red Blob氏による、いつもながら素晴らしい記事です。Googleマップの経路探索に関する私の高レベルの前提を覆されました。アルゴリズムの授業を思い出すと、Googleマップがこんなに速いのは、最短経路探索の「最適部分構造」によるものだと思っていました。つまり、AからCまでの最短経路がBを経由する場合、AからB、BからCの最短経路も同時に得られ、任意の経路の大部分について、事前計算された「中間点」の経路をいくつか経由してルーティングできる、という考えです。この記事を読んで、その考えが覆されました。ランドマークは経路の途中ではなく、目的地の背後にあるのです！非常に便利なツールです。
- simonw
5日前にここで議論されました：https://news.ycombinator.com/item?id=49079995
（正直なところ、これは非常に素晴らしい成果なので、2回目の議論に値します。前回はコメントが40件しか付きませんでしたから。）
- inigyou
良い記事とデモでした。色について少し混乱しました。少なくとも一度、テキストが青いタイルはランドマークのおかげでチェックする必要がないと言っているのに、実際には緑色で、青いタイルはそもそもチェックされなかったものです。私は色覚異常ではありません。
あなたのマップの多くは、いくつかの地点で接続された部屋で構成されています。まず部屋のグラフで経路探索を行い、その後各部屋を個別に探索することを検討したことはありますか？部屋の一方のポータルからもう一方のポータルまでのすべての経路を事前計算することもできますが、おそらくその必要はないでしょう。ただし、それらのコストを事前計算する必要はあります。これは、各部屋にランドマークを置くのとほぼ同じ経路探索コストになるでしょう。