Google マップのようなマップ ルーティング?
https://stackoverflow.com/questions/2798
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はマップ ルーティングに常に興味を持っていますが、それに関する入門 (または上級!) レベルの優れたチュートリアルを見つけたことがありません。誰かが何か指針やヒントなどを持っていますか？
アップデート： 私は主に、マップ システムがどのように実装されるか (データ構造、アルゴリズムなど) に関するポインタを探しています。
解決
を見てください。 オープンストリートマッププロジェクト ユーザーが提供し、ライセンスを取得したデータのみを使用して、真のフリー ソフトウェア プロジェクトでこの種のことにどのように取り組んでいるかを確認し、 興味深い内容が含まれる Wiki.
数年前、彼らはかなり気楽に関わってくれて、私の質問にたくさん答えてくれたので、彼らが今でもいい人たちではない理由がわかりません。
他のヒント
Google マップのルート検索機能のエンジニアの 1 人である Barry Brumitt が、興味深いトピックについて次のような投稿を書きました。
より良い経路探索への道2007/11/06 03:47:00 PM
A* は、実際には実稼働マッピング アルゴリズムにはるかに近いものです。Dijikstra の元のアルゴリズムと比較して、探索がかなり少なくて済みます。
マップ ルーティングとは、道路網に沿った最短経路を見つけることを意味しますか?
ダイクストラ最短経路アルゴリズムが最もよく知られています。ウィキペディアには悪くない紹介文があります。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
ここに Java アプレットがあり、実際の動作を確認できます。 http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html Google を使えば、ほぼすべての言語のソース コードにアクセスできます。
運転ルートを生成するための実際の実装には、道路ネットワークの階層、平均速度、交差点の優先順位、信号機のリンク、禁止された曲がり角など、リンクやノードの通過に関連するコストを記述する道路ネットワーク上のかなりの量のデータが含まれます。
各マップ サービス プロバイダー (Gmaps、Ymaps API など) の API を学習する代わりに、学習することをお勧めします 地図抽出
「Mapstraction は、さまざまな JavaScript マッピング API に共通の API を提供するライブラリです」
URL にアクセスして、一般的な API を学習することをお勧めします。How-Toも充実しています。
ルーティングに関する適切なチュートリアルはまだ見つかりませんが、読むべきコードはたくさんあります。
Openstreetmap データを使用する GPL ルーティング アプリケーションがあります。 ゴスモア Windows (+ モバイル) と Linux で動作します。興味深い [同じデータを使用するアプリケーションが多数ありますが、gosmore にはいくつかの優れた用途があります] 例えばウェブサイトとのインターフェース.
ルーティングに関する最大の問題は不良データであり、十分なデータが得られないことです。したがって、それを試したい場合は、データをより適切に制御できるように、テストを非常にローカルに保ちます。
概念的な観点から、池に石を落として波紋を観察することを想像してください。ルートは、開始位置の池と石を表します。
もちろん、距離 n が増加するにつれて、アルゴリズムは n^2 のパスの一部を検索する必要があります。開始位置を取得し、その時点から利用可能なすべてのパスを確認します。次に、それらのパスの終点にあるポイントを再帰的に呼び出します。
パスを二重に戻さないこと、ルートが既にカバーされている場合はその時点でルートを再チェックしないこと、および時間がかかりすぎるパスを諦めることによって、パフォーマンスを向上させることができます。
別の方法は、アリのフェロモン アプローチを使用することです。このアプローチでは、アリが開始点からランダムに這い、匂いの跡を残します。匂いの痕跡は、指定された道を横切るアリの数が増えるほど蓄積されます。始点と終点の両方から（十分な）アリを送り込むと、最終的には最も強い香りの経路が最短になります。これは、アリが一定のペースで歩くと仮定すると、最短経路は一定期間内に何度も訪れることになるためです。
編集@スパイキー
池アルゴリズムの実装方法のさらなる説明として、必要となる潜在的なデータ構造が強調表示されます。
マップをネットワークとして保存する必要があります。これは単に次のセットです nodes そして edges それらの間の。一連の nodes を構成する route. 。エッジは 2 つのノード (おそらく両方が同じノード) を結合し、関連付けられた cost のような distance または time 端を横切る。エッジは双方向または単方向のいずれかになります。おそらく最も簡単なのは、一方向のものを用意し、ノード間の双方向の移動のために 2 倍にすることです (つまり、1 つのエッジは A から B へ、もう 1 つのエッジは B から A へ）。
例として、上向きの正三角形に配置された 3 つの鉄道駅を想像してください。さらに、それらの間にはそれぞれ 3 つの駅があります。エッジは隣接するすべてのステーションを結合し、最終的なダイアグラムでは、大きな三角形の内側に逆三角形が配置されます。
ノードに左下から始まり、左から右、上に A、B、C、D、E、F (F が上) とラベルを付けます。
エッジはどちらの方向にも横断できると仮定します。各エッジのコストは 1 km です。
さて、左下の A から上のステーション F までルートを設定したいと思います。考えられるルートは多数あり、その中には自分自身を倍増させるルートも含まれます。ABCEBDEF。
私たちはいつもこう言います。 NextNode, 、を受け入れる node そして cost そして、移動できるノードごとに自分自身を呼び出します。
明らかに、このルーチンを実行すると、長さが無限になる可能性のあるルート (例: ABABABAB など) を含むすべてのルートが最終的に検出されます。をチェックすることでこのような事態が起こらないようにする cost. 。以前に訪問したことのないノードを訪問するときは常に、そのノードに対してコストと訪問元のノードの両方を計算します。既存のコストと比較する前にノードが訪問されており、コストが安い場合は、ノードを更新して続行します (再帰的)。より高価な場合は、ノードをスキップします。すべてのノードがスキップされた場合、ルーチンを終了します。
ターゲットノードに到達したら、ルーチンも終了します。
このようにして、すべての実行可能なルートがチェックされますが、最も重要なのはコストが最も低いルートのみです。プロセスが終了するまでに、ターゲット ノードを含め、各ノードはそのノードに到達するためのコストが最小になります。
ルートを取得するには、ターゲット ノードから逆方向に作業します。元のノードをコストとともに保存したので、後は逆方向にホップしてルートを構築するだけです。この例では、次のような結果になります。
ノード A - (合計) コスト 0 - ノードからのコスト なし
ノード B - コスト 1 - ノード A から
ノード C - コスト 2 - ノード B から
ノード D - コスト 1 - ノード A から
ノード E - コスト 2 - ノード D から / コスト 2 - ノード B から (コストが等しいため、これは例外です)
ノード F - コスト 2 - ノード D から
したがって、最短ルートはADFです。
この分野で働いてきた私の経験から言えば、A* は仕事をとてもうまくやってくれます。これは (前述したように) ダイクストラのアルゴリズムよりも高速ですが、それでも通常の有能なプログラマーが実装して理解できるほど単純です。
ルート ネットワークの構築は最も難しい部分ですが、それは一連の簡単な手順に分解できます。すべての道を手に入れましょう。ポイントを順番に並べ替えます。異なる道路上の同一点のグループを交差点 (ノード) にします。ノードが接続する両方向に円弧を追加します (一方通行の場合は一方向のみ)。
A* アルゴリズム自体は ウィキペディアに詳しく記載されています. 。最適化の重要な点は、オープン リストから最適なノードを選択することです。このノードには、高性能の優先キューが必要です。C++ を使用している場合は、STL priority_queue アダプターを使用できます。
アルゴリズムをカスタマイズして、優先速度、距離、またはその他の基準に基づいてネットワークのさまざまな部分 (歩行者、自動車、公共交通機関など) をルーティングするのは非常に簡単です。これを行うには、ネットワークの構築時にどのルート セグメントが使用可能か、および各ルート セグメントにどの重みが割り当てられるかを制御するフィルターを作成します。
各走査のコストに関して別の考えが浮かびましたが、計算に必要な時間と処理能力が増加することになります。
例： GoogleMapsによると、（私が住んでいる場所で）A地点からB地点に行くには3つの方法があります。Garmin ユニットは、これら 3 つのパスのそれぞれを提供します。 Quickest ルート計算。これらの各ルートを何度も通過して平均した後 (時間帯やカフェインの量などによって誤差が生じるのは明らかです)、アルゴリズムは道路の曲がり角の数を考慮して高レベルの精度を実現できると感じています。 、 例えば 1マイルの直線道路は、急カーブのある1マイル道路よりも速いでしょう。実用的な提案ではありませんが、毎日の通勤の結果を改善するために私が使用しているものであることは確かです。
