24

私は常にマップルーティングに興味を持ってきましたが、優れた入門（または上級）レベルのチュートリアルは見つかりませんでした。誰かがポインタやヒントなどを持っていますか？

更新：私は主に、マップシステムの実装方法（データ構造、アルゴリズムなど）に関するポインターを探しています。

4

9 に答える 9

15

オープンストリートマッププロジェクトを見て、ユーザーが提供しライセンスを取得したデータのみを使用して、真に無料のソフトウェアプロジェクトでこの種の問題にどのように取り組んでいるかを確認し、興味深いと思われるものを含むwikiを作成してください。

数年前、関係者はとても簡単に行って、私が持っていた多くの質問に答えたので、彼らがまだ良い束ではない理由はわかりません。

于 2008-08-05T20:27:36.633 に答える
5

A* は、実際にはプロダクション マッピング アルゴリズムにはるかに近いものです。Dijikstra の元のアルゴリズムと比較して、必要な調査はかなり少なくて済みます。

于 2008-09-24T23:19:48.583 に答える
5

マップ ルーティングとは、道路網に沿って最短経路を見つけるという意味ですか?

ダイクストラ最短パス アルゴリズムが最もよく知られています。ウィキペディアのイントロは悪くありません: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

ここに Java アプレットがあり、実際の動作を確認できます。言語。

走行ルートを生成するための実際の実装には、道路網の階層、平均速度、交差点の優先順位、交通信号のリンク、禁止されたターンなど、横断リンクとノードに関連するコストを説明する道路網に関するかなりの量のデータが含まれます。

于 2008-08-15T04:31:27.390 に答える
4

Google マップのルート検索機能のエンジニアの 1 人である Barry Brumitt は、このトピックに関する興味深い投稿を書いています。

より良い経路探索への道 11/06/2007 03:47:00 PM

于 2008-09-17T08:44:28.847 に答える
2

各マップ サービス プロバイダー (Gmaps、Ymaps api など) への API を学習する代わりに、Mapstraction を学習すると良い

「Mapstraction は、さまざまな JavaScript マッピング API に共通の API を提供するライブラリです」

URL にアクセスして、一般的な API を学習することをお勧めします。ハウツーも充実しています。

于 2008-08-06T13:35:08.930 に答える
2

ルーティングに関する優れたチュートリアルをまだ見つけていませんが、読むべきコードがたくさんあります。

Openstreetmap データを使用する GPL ルーティング アプリケーションがあります。たとえば、Windows (+ モバイル) および Linux で動作するGosmoreです。[同じデータを使用する興味深いアプリケーションが多数ありますが、gosmore にはWeb サイトとのインターフェースなどの優れた用途があります。

ルーティングの最大の問題はデータの質が悪く、十分なデータが得られないことです。したがって、試してみたい場合は、テストを非常にローカルに保ち、データをより適切に制御できるようにします。

于 2008-09-17T08:34:24.207 に答える
2

概念的な観点から、石を池に落として波紋を見ることを想像してください。ルートは、池と石が開始位置を表します。

もちろん、アルゴリズムは、距離 n が増加するにつれて、n^2 パスの一部を検索する必要があります。開始位置に移動し、その時点から利用可能なすべてのパスを確認します。次に、これらのパスの最後にあるポイントなどを再帰的に呼び出します。

パスをダブルバックしないこと、ポイントでルートが既にカバーされている場合はそのルートを再チェックしないこと、および時間がかかりすぎるパスを放棄することによって、パフォーマンスを向上させることができます。

別の方法として、アリ フェロモン アプローチを使用する方法があります。この方法では、アリが開始点からランダムにクロールし、香りの跡を残します。これにより、特定のパスを横切るアリの数が増えます。始点と終点の両方から (十分な数の) アリを送ると、最終的に最も香りの強い経路が最短になります。これは、アリが一定のペースで歩くとすると、最短経路は一定時間内に何度も訪れているためです。

編集 @ スパイキー

池のアルゴリズムを実装する方法の詳細な説明として、必要な潜在的なデータ構造が強調されています。

マップをネットワークとして保存する必要があります。これは単にそれらの間のセットnodesですedges。のセットをnodes構成しrouteます。エッジは 2 つのノード (両方とも同じノードである可能性があります) を結合し、エッジを横断するやcostなどの関連付けられています。エッジは、双方向または単方向のいずれかです。おそらく最も単純なのは、単方向のものだけを持ち、ノード間の双方向の移動を 2 倍にすることです (つまり、A から B への 1 つのエッジと、B から A への別のエッジ)。distancetime

例として、上向きの正三角形に配置された 3 つの鉄道駅を想像してください。また、それぞれの中間にさらに 3 つの駅があります。エッジは隣接するすべてのステーションを結合します。最終的な図では、大きな三角形の内側に逆三角形が配置されます。

左下から始まり、左から右、上に向かって、ノードに A、B、C、D、E、F (上部の F) のラベルを付けます。

エッジはどちらの方向にもトラバースできると仮定します。各エッジのコストは 1 km です。

わかりました。では、左下の A 駅から一番上の駅 F までルートを設定したいと思います。ABCEBDEF のように、それ自体で 2 倍になるルートを含め、多くのルートが考えられます。

aと aNextNodeを受け取り、移動できる各ノードに対して自分自身を呼び出すルーチン say があります。nodecost

明らかに、このルーチンを実行すると、潜在的に無限の長さのルート (ABABABAB など) を含むすべてのルートが最終的に検出されます。に対してチェックすることで、これが起こらないようにしcostます。以前に訪問したことのないノードを訪問するときはいつでも、そのノードに対してコストと元のノードの両方を置きます。既存のコストを確認する前にノードにアクセスしたことがあり、コストが安い場合は、ノードを更新して続行します (再帰)。より高価な場合は、ノードをスキップします。すべてのノードがスキップされた場合、ルーチンを終了します。

ターゲット ノードにヒットすると、ルーチンも終了します。

このようにして、すべての実行可能なルートがチェックされますが、決定的に最もコストが低いルートのみがチェックされます。プロセスの終わりまでに、各ノードは、ターゲット ノードを含め、そのノードに到達するためのコストが最も低くなります。

ルートを取得するには、ターゲット ノードから逆方向に作業します。コストとともに元のノードを保存したので、ルートを構築するために逆方向にホップするだけです。この例では、次のようになります。

ノード A - (合計) コスト 0 - ノードから なし
ノード B - コスト 1 - ノード A から
ノード C - コスト 2 - ノード B から
ノード D - コスト 1 - ノード A から
ノード E - コスト 2 - ノード D から / コスト2 - ノード B から (コストが等しいため、これは例外です)
ノード F - コスト 2 - ノード D から

したがって、最短ルートはADFです。

于 2008-09-26T14:05:18.623 に答える
1

この分野での私の経験から、A* は非常にうまく機能します。これは (前述のように) Dijkstra のアルゴリズムよりも高速ですが、通常の有能なプログラマーが実装して理解するには十分に単純です。

ルート ネットワークの構築は最も難しい部分ですが、一連の簡単な手順に分けることができます。すべての道路を取得します。ポイントを順番に並べ替えます。異なる道路上の同一ポイントのグループを交差点 (ノード) にします。ノードが接続する両方向にアークを追加します (または、一方通行の場合は一方向のみ)。

A* アルゴリズム自体はWikipedia で詳しく説明されています。最適化する重要な場所は、オープン リストから最適なノードを選択することです。これには、高性能の優先キューが必要です。C++ を使用している場合は、STL priority_queue アダプターを使用できます。

ネットワークのさまざまな部分 (歩行者、車、公共交通機関など) を優先する速度、距離、またはその他の基準でルーティングするようにアルゴリズムをカスタマイズするのは非常に簡単です。これを行うには、フィルターを作成して、ネットワークを構築するときに使用可能なルート セグメントを制御し、それぞれにどの重みを割り当てるかを制御します。

于 2012-07-15T21:13:02.097 に答える
1

各トラバーサルのコストに関して別の考えが浮かびますが、計算に必要な時間と処理能力が増加します。

例: Google マップによると、私が (住んでいる場所で) A 地点から B 地点に行くには 3 つの方法があります。Garmin ユニットは、Quickestルート計算でこれら 3 つのパスのそれぞれを提供します。これらの各ルートを何度も横断して平均化した後 (時間帯やカフェインの量などによって誤差が生じることは明らかです)、アルゴリズムは道路の曲がり角の数を考慮して高レベルの精度を得ることができると思います。たとえば 、1 マイルの直線道路は、急カーブのある 1 マイルの道路よりも速くなります。実用的な提案ではありませんが、毎日の通勤の結果セットを改善するために私が使用していることは確かです.

于 2011-09-18T21:34:27.853 に答える