地図上のA地点からB地点までの方向を計算するアルゴリズムは何ですか? 質問する

地図プロバ​​イダー（Google マップや Yahoo! マップなど）はどのようにして道順を提案するのでしょうか?

つまり、彼らはおそらく何らかの形で現実世界のデータを持っているでしょう。そこには距離はもちろん、運転速度、歩道の有無、電車のスケジュールなども含まれているでしょう。しかし、データがより単純な形式、たとえば、距離を反映したエッジの重みを持つ非常に大きな有向グラフだったとします。任意の 1 つのポイントから別のポイントへの方向をすばやく計算できるようにしたいのです。これらのポイントは、互いに近い場合 (1 つの都市内) もあれば、離れている場合もあります (国をまたいで)。

ダイクストラのアルゴリズムのようなグラフ アルゴリズムは、グラフが巨大であるため機能しません。幸い、A* のようなヒューリスティック アルゴリズムはおそらく機能します。ただし、データは非常に構造化されているため、何らかの階層化アプローチが機能する可能性があります (たとえば、遠く離れた特定の「キー」ポイント間の事前計算された方向といくつかのローカル方向を保存します。すると、2 つの遠く離れたポイントへの方向には、キー ポイントへのローカル方向、別のキー ポイントへのグローバル方向、そして再びローカル方向が含まれます)。

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

追記：この質問は、オンラインマップの道順の奇妙な点を発見したことがきっかけでした。三角不等式とは逆に、Googleマップは時々次のように考えます。XZ中間点を使うよりも時間がかかり、距離も長くなります。XYZしかし、彼らの歩行方向は別のパラメータも最適化しているのでしょうか?

PPS. ここに、三角不等式のもう一つの違反があります。これは、（私には）彼らが何らかの段階的なアプローチを使用していることを示唆しています。XZ対XYZ前者は、少し外れではあるものの、目立つセバストポル通りを使用しているようです。

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