559

マップ プロバイダー (Google や Yahoo! マップなど) はどのように道順を提案しますか?

つまり、彼らはおそらく距離を含む何らかの形で実世界のデータを持っているでしょうが、おそらく運転速度、歩道の存在、電車のスケジュールなども含まれています。しかし、データがより単純な形式であったとします。距離を反映するエッジ ウェイトを使用します。ある任意の点から別の点への方向をすばやく計算できるようにしたいと考えています。これらのポイントは、(1 つの都市内で) 近くにある場合もあれば、遠く離れている場合もあります (クロスカントリー)。

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

実際に実際に使用されているアルゴリズムは何ですか?

PS。この質問は、オンライン マッピングのルート案内で癖を見つけたことがきっかけでした。三角形の不等式とは反対に、 XYZのように中間点を使用するよりも、 XZの方が時間がかかり、遠いとGoogle マップが判断する場合があります。しかし、彼らの歩行経路も別のパラメータで最適化されているのではないでしょうか?

PPS。XZ対XYZという、ある種の階層化されたアプローチを使用していることを (私に) 示唆する三角形の不等式の別の違反を次に示します。前者は少し外れていますが、有名なセバストポール大通りを利用しているようです。

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

4

18 に答える 18

539

ルーティングアルゴリズムの作業を含む、マッピング会社で18か月間働いた人と言えば...はい、ダイクストラはいくつかの変更を加えて機能します。

  • ソースからデストまでダイクストラ法を1回実行する代わりに、両端から開始し、中央で出会うまで両側を拡張します。これにより、作業の約半分が削減されます（2 * pi *（r / 2）^2とpi* r ^ 2）。
  • 出発地と目的地の間のすべての都市の裏通りを探索しないようにするために、地図データの複数のレイヤーを作成できます。高速道路のみを含む「高速道路」レイヤー、二次道路のみを含む「二次」レイヤーなどです。次に、必要に応じて拡張しながら、より詳細なレイヤーの小さなセクションのみを探索します。明らかに、この説明では多くの詳細が省略されていますが、あなたはその考えを理解しています。

これらの線に沿って変更を加えることで、非常に合理的な時間枠でクロスカントリールーティングを行うこともできます。

于 2009-01-11T12:41:34.683 に答える
114

この問題は、ここ数年活発に研究されている分野です。主なアイデアは、グラフの前処理を1 回実行して、後続のすべてのクエリを高速化することです。この追加情報により、旅程を非常に高速に計算できます。それでも、ダイクストラのアルゴリズムはすべての最適化の基礎です。

Arachnidは、階層情報に基づく双方向検索とエッジ プルーニングの使用法について説明しました。これらの高速化手法は非常にうまく機能しますが、最新のアルゴリズムはこれらの手法よりも優れています。現在のアルゴリズムを使用すると、大陸の道路網で最短経路を1 ミリ秒よりもかなり短い時間で計算できます。Dijkstra の変更されていないアルゴリズムを高速に実装するには、約10 秒かかります。

記事Engineering Fast Route Planning Algorithmsは、その分野の研究の進歩の概要を示しています。詳細については、その論文の参考文献を参照してください。

最速の既知のアルゴリズムは、データ内の道路の階層状態に関する情報を使用しません。つまり、道路が高速道路か地方道路かということです。代わりに、ルート計画を高速化するために最適化された独自の階層を前処理ステップで計算します。次に、この事前計算を使用して検索を絞り込むことができます。ダイクストラのアルゴリズムでは、出発地と目的地から遠く離れた低速道路を考慮する必要はありません。利点は、パフォーマンスが非常に優れていることと、結果の正確性が保証されることです。

最初の最適化されたルート計画アルゴリズムは、静的な道路網のみを扱っていました。つまり、グラフのエッジには固定のコスト値があります。交通渋滞や車両に依存する制限などの動的な情報を考慮に入れたいため、これは実際には当てはまりません。最新のアルゴリズムもこのような問題に対処できますが、まだ解決すべき問題があり、研究が続けられています。

TSPの解を計算するために最短経路距離が必要な場合は、ソースと宛先の間のすべての距離を含む行列に関心がある可能性があります。これについては、 Highway Hierarchies を使用した多対多の最短パスの計算を検討できます。これは、過去 2 年間の新しいアプローチによって改善されたことに注意してください。

于 2009-02-21T22:12:28.193 に答える
19

三角形の不等式違反に対処するだけで、うまくいけば、彼らが最適化している追加の要因は常識です. 混沌 と 破壊につながる可能性があるため、必ずしも最短または最速のルートが必要なわけではありません。トラックにやさしく、ナビに従うすべてのドライバーに対応できる主要なルートを優先して道順を表示したい場合は、三角形の不等式をすぐに破棄します[1]。

Y が X と Z の間の狭い住宅街の場合、ユーザーが明示的に XYZ を要求した場合にのみ、Y 経由のショートカットを使用したいでしょう。彼らが XZ を要求する場合は、たとえそれが少し遠く、少し時間がかかったとしても、主要道路に固執する必要があります。これは、ブレースのパラドックスに似ています。誰もが最短で最速のルートを選択しようとすると、渋滞が発生し、それが最速のルートではないことを意味します。ここから、グラフ理論からゲーム理論に移行します。

[1] 実際、生成される距離が数学的な意味での距離関数になるという希望は、一方通行を許可して対称性の要件を失うと無効になります。三角形の不等式をなくすことも、傷に塩をこすりつけるだけです。

于 2009-02-24T23:52:30.860 に答える
15

比較され、正確性が証明された世界最速のルーティングアルゴリズムは次のとおりです。

http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf

これがこのテーマに関するグーグルの技術トークです：

http://www.youtube.com/watch?v=-0ErpE8tQbw

schultesによって議論された高速道路階層アルゴリズムの実装は次のとおりです（現在ベルリンのみで、私はインターフェースを作成しており、モバイルバージョンも開発されています）：

http://tom.mapsforge.org/

于 2010-10-26T17:37:38.607 に答える
9

私はこれまで Google や Microsoft や Yahoo マップに取り組んだことがないので、それらがどのように機能するかはわかりません。

しかし、私はエネルギー会社向けにカスタム サプライ チェーン最適化システムを設計しました。このシステムには、トラックのフリート用のスケジューリングおよびルーティング アプリケーションが含まれていました。ただし、ルーティングに関する私たちの基準は、工事や渋滞、車線閉鎖などよりも、はるかにビジネス固有のものでした。

トラックのスケジュールと経路指定には、ACO (アリコロニー最適化) と呼ばれる手法を採用しました。この手法は、巡回セールスマン問題に適用され、ルーティングの問題を解決する AI 手法です。ACO の秘訣は、ルーティングの既知の事実に基づいてエラー計算を作成し、グラフ解法モデルがいつ終了するか (エラーが十分に小さいか) を知ることです。

このテクニックの詳細については、ACO または TSP をググってください。ただし、これにはオープンソースの AI ツールを使用したことがないため、提案することはできません (ただし、SWARM はかなり包括的なものだと聞きました)。

于 2009-02-25T14:50:36.957 に答える
8

ダイクストラのアルゴリズムのようなグラフ アルゴリズムは、グラフが巨大であるため機能しません。

ダイクストラは通常、完全なグラフではなく、非常に小さなサブセットのみを調べるため、この議論は必ずしも成立しません (グラフの相互接続が良好であるほど、このサブセットは小さくなります)。

ダイクストラは、実際には、適切に動作するグラフに対してかなりうまく機能する場合があります。一方、注意深いパラメーター化を行えば、A* は常に同等かそれ以上のパフォーマンスを発揮します。データに対してどのように機能するかをすでに試しましたか?

そうは言っても、私は他の人々の経験について聞くことにも非常に興味があります. もちろん、Google マップの検索などの顕著な例は特に興味深いものです。有向最近傍ヒューリスティックのようなものを想像できました。

于 2009-01-10T00:47:11.630 に答える
7

Floyd Warshall のアルゴリズムがここで言及されていないことに少し驚いています。このアルゴリズムは、ダイクストラのものと非常によく似ています。また、非常に優れた機能が 1 つあります。それは、さらに中間頂点を許可し続けたい限り、計算できるということです。そのため、州間高速道路や高速道路を使用するルートをかなり迅速に見つけることができます。

于 2009-12-09T00:04:39.660 に答える
6

私はこれを何度も行ってきましたが、実際にはいくつかの異なる方法を試しています。マップのサイズ (地理的) によっては、harsine 関数をヒューリスティックとして使用することを検討することをお勧めします。

私が行った最善の解決策は、ヒューリスティック関数として直線距離で A* を使用することでした。ただし、マップ上の各ポイント (交差点または頂点) には何らかの座標が必要です。ヒューリスティック関数のさまざまな重み付けを試すこともできます。

f(n) = k*h(n) + g(n)

ここで、k は 0 より大きい定数です。

于 2009-11-02T17:29:18.357 に答える
4

おそらく、主要な場所と階層化されたマップ間の事前計算されたルートに関する回答に似ていますが、私の理解では、ゲームでは、A* を高速化するために、マクロ ナビゲーション用の非常に粗いマップと、マクロ方向の境界へのナビゲーション。したがって、計算する 2 つの小さなパスがあるため、目的地までの単一のパスを単純に実行するよりも、検索スペースがはるかに小さくなります。そして、これを頻繁に行うビジネスをしている場合、事前に計算されたデータが大量にあるため、検索の少なくとも一部は、パスの検索ではなく、事前に計算されたデータの検索になります。

于 2009-02-26T01:21:10.140 に答える
3

私はこれについてさらにいくつかの考えを持っていました：

1) マップは物理的な組織を表すことに注意してください。すべての交差点の緯度/経度を保存します。ターゲットの方向にあるポイントをはるかに超えてチェックする必要はありません。自分がブロックされていることに気付いた場合にのみ、これを超える必要があります。優れた接続のオーバーレイを保存する場合は、さらに制限することができます。通常、最終目的地から離れてそれらの 1 つを通過することはありません。

2) 制限された接続によって定義されたゾーン全体に世界を分割し、ゾーン間のすべての接続ポイントを定義します。ソースとターゲットがどのゾーンにあるかを見つけて、現在地から各接続ポイントまでの開始ゾーン ルートと終了ゾーン ルート、接続ポイント間の単純なマップ間のゾーンを見つけます。（後者の多くはすでに事前に計算されていると思います。）

ゾーンは大都市圏よりも小さい場合があることに注意してください。それを分割する地形機能 (たとえば、川) を持つ都市は、複数のゾーンになります。

于 2009-02-21T23:31:16.380 に答える
3

これは私の推測ですが、検索ドメインを絞り込むために、有向マップにオーバーレイするインフルエンス マップ データ構造を使用している可能性があります。これにより、目的の移動が長い場合に、検索アルゴリズムがパスを主要なルートに誘導できるようになります。

これが Google アプリであることを考えると、大規模なキャッシュによって多くの魔法が行われていると考えるのも妥当です。:) 最も一般的な上位 5% の Google マップ ルート リクエストをキャッシュすることで、リクエストの大部分 (20%? 50%?) が単純なルックアップで応答できるようになったとしても、私は驚かないでしょう。

于 2009-01-09T23:48:02.310 に答える
3

しばらく前に、サンタローザ近くの同じ出発地からヨセミテ国立公園の 2 つの異なるキャンプ場へのルートを取得したとき、使用されたヒューリスティックに非常に興味がありました。これらの異なる目的地は、まったく異なるルート (I-580 または CA-12 経由) を生成しましたが、両方のルートが最後の 100 マイル (CA-120 に沿って) で収束し、最後に数マイル分岐しました。これはかなり再現性がありました。2 つのルートは最大 50 マイル離れていて、約 100 マイル離れていましたが、距離と時間は予想どおりかなり近かったです。

残念ながら、それを再現することはできません。アルゴリズムが変更されたに違いありません。しかし、アルゴリズムに興味がありました。私が推測できるのは、遠くから見た目的地間の小さな角度の違いに非常に敏感な方向性の刈り込みがあったか、最終目的地の選択によって選択された異なる事前計算されたセグメントがあったということだけです。

于 2011-01-08T03:52:10.997 に答える
2

私はルーティングに数年間取り組んできましたが、最近では私のクライアントのニーズによってアクティビティが爆発的に増加しています。最適化やより複雑なアルゴリズムを探す必要はまったくありません。巨大なグラフをルーティングすることは問題ではありません。

しかし、速度は、ルーティング ネットワーク全体 (つまり、ルート セグメントとジャンクションをそれぞれ表すアークとノードの有向グラフ) がメモリに存在するかどうかに依存します。主な時間オーバーヘッドは、このネットワークの作成にかかる時間です。Windows を実行している通常のラップトップに基づく大まかな数値と、スペイン全体のルーティング: ネットワークの作成にかかった時間: 10 ～ 15 秒。ルートの計算にかかった時間: 測定するには短すぎます。

もう 1 つの重要な点は、ネットワークを何度でもルーティング計算に再利用できることです。アルゴリズムが何らかの方法でノードをマークして、最適なルート (現在のノードまでの総コスト、およびそのノードまでの最適なアーク) を記録している場合 (A* の場合と同様)、この古い情報をリセットまたは消去する必要があります。何十万ものノードを経由するよりも、世代番号システムを使用する方が簡単です。各ノードにそのデータの世代番号を付けます。新しいルートを計算するときに世代番号を増やします。世代番号が古いノードは古く、その情報は無視できます。

于 2012-07-20T13:43:47.723 に答える
1

OPのマップがどうなっているのかわかります。

中間点が指定されたルートを見てください。道路がまっすぐではないため、ルートは少し後方に移動します。

彼らのアルゴリズムがバックトラックしない場合、それはより短いルートを見ることはありません。

于 2009-01-10T01:53:41.840 に答える
-4

マップでは、マップ全体が考慮されることはありません。私の推測は次のとおりです:- 1. あなたの場所に応じて、場所とその場所のランドマークを読み込みます。2.目的地を検索すると、地図の他の部分が読み込まれ、2 つの場所からグラフが作成され、最短経路アルゴリズムが適用されます。

また、最短経路の計算に使用されていると思われる動的計画法の重要な手法があります。それも参照できます。

于 2015-11-03T00:33:09.890 に答える