[解決済み] 地図上のA地点からB地点への道順を計算するアルゴリズムは？

質問

地図プロバイダー（GoogleやYahoo！地図など）は、どのように道順を提案するのですか？

距離だけでなく、走行速度や歩道の有無、電車の時刻表など、何らかの形で実世界のデータを持っているはずです。 しかし、そのデータがもっと単純な形式、たとえば距離を反映したエッジの重みを持つ非常に大きな有向グラフであったとしましょう。 ある任意の点から別の点への方向を素早く計算したい。 これらの点は、あるときは近くにあり（1つの都市内）、あるときは遠くにある（国をまたぐ）。

ダイクストラのアルゴリズムのようなグラフアルゴリズムは、グラフが巨大になるため、うまくいきません。 幸いなことに、A*のようなヒューリスティックなアルゴリズムなら、おそらくうまくいくでしょう。 しかし、私たちのデータは非常に構造化されており、おそらく何らかの階層的なアプローチが有効ではないでしょうか？ (例えば、遠く離れた特定のquot;key"点間の事前計算された方向と、いくつかのローカルな方向を保存します。 その場合、離れた2つの点の方向は、キーポイントへのローカルな方向、別のキーポイントへのグローバルな方向、そして再びローカルな方向を含むことになります)。

実際にどのようなアルゴリズムが使われているのでしょうか？

PS. この質問の動機は、オンライン地図の道順に癖があることを見つけたからです。 三角形の不等式に反して、時々Google Mapsは次のように考えています。 X-Z のように中間地点を使うよりも時間がかかり、距離も長くなります。 X-Y-Z . でも、もしかしたら、彼らの歩く方向は、別のパラメータにも最適化されているのかも？

PPSです。 これも三角形の不等式に違反していることから、ある種の階層的なアプローチを使っていることを（私には）示唆しています。 X-Z 対 X-Y-Z . 前者は、少し外れるが目立つBoulevard de Sebastopolを使うようだ。

編集 : これらの例はどちらももう動作しないようですが、元の投稿の時点ではどちらも動作していました。

どのように解決するのですか？

地図製作会社で18ヶ月間働き、その間にルーティング・アルゴリズムに携わった者として言えば...そうですね。 ダイクストラの は、いくつかの修正を加えても動作します。

• を行う代わりに ダイクストラの を元から先まで1回ずつ、両端から始めて、真ん中で合流するまで両側を拡張します。これにより、およそ半分の作業（2*pi*(r/2)^2 vs pi*r^2）を省くことができます。
• 出発地と目的地の間にあるすべての都市の裏路地を探索することを避けるために、地図データのレイヤーを複数持つことができます。高速道路だけを集めた「ハイウェイ」レイヤー、裏通りだけを集めた「セカンダリー」レイヤー、といった具合だ。そして、より詳細なレイヤーの小さな部分のみを探索し、必要に応じて拡張していくのです。もちろん、この説明では多くの詳細が省かれていますが、イメージはつかめると思います。

このような工夫をすれば、国土横断的なルーティングも非常に合理的な時間で行うことができます。