場所の住所から抽出する座標のセットがあります。今、私の仕事はこれらのポイントに最適なパスを生成することです。このタスクをどのように達成できますか？2点のルートを生成する例を見てきました。しかし、カバーする目的地が複数ある場合、それを大規模に想像することはできません。私はこの機能をAndroidアプリケーションに使用しています。
2 に答える
0
これは「パスファインディング」または「ルーティング」の問題です。
http://en.wikipedia.org/wiki/Pathfinding
また、Dijikstra のアルゴリズムに直面することがよくあります。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
または、「A* アルゴリズム」として知られる一般化を使用します。
http://en.wikipedia.org/wiki/A-star_algorithm
近年、このようなものは「収縮階層」アルゴリズムに進化しました。
http://en.wikipedia.org/wiki/Contraction_hierarchies
これははるかに高速で効率的です。
そこにはいくつかの経路探索/ルーティングエンジンがあります。最良のものは、間違いなく Open Source Routing Machine です。
他にもいくつかのエンジンを見つけることができます。「マップルーティング」または「パスファインディング」については、Googleで検索してください。
通常、エンジンは、Java/Android プロジェクトに埋め込むことができるライブラリではなく、ネット経由でアクセスする必要がある (RESTful) Web サービスです。
于 2012-11-27T16:59:15.600 に答える
0
特定の順序でそれらを訪問する必要がある場合、問題は 2 つのポイントのパスを解決することに減らすことができます。隣接する座標のペアを使用して同じ方法で問題を解決し、始点と終点を接続するパスをつなぎ合わせるだけです。
それらを任意の順序で訪問し、移動距離を最適化する必要がある場合、実際には NP-Hard である巡回セールスマンの問題を解決していることになります。唯一の正確な解決策は、すべての順列を試すことです。実際には、前のケースと似ていますが、ポイントの大きなセットを練習するには時間がかかりすぎます。まず、メモリを節約するために距離のみを保持して、ポイントのすべてのペアの最短パスを解決します。これには n(n-1)/2 操作が必要です。次に、一連の座標のすべての順列を生成し、以前に計算されたデータを使用して、それらに関連付けられたパスを計算します。最小距離の順列 (およびそれに関連付けられたパス) が最適なシーケンスになります。最初の段落で説明した方法を使用して、パスを再度生成します。
アルゴリズムの最初のステップは時間がかかるように見えるかもしれませんが、実際には非多項式の 2 番目のステップです。より高速に実行される不正確なソリューションもありますが、信頼性は異なります。アプリケーションに適しているかどうかを判断するには、試行錯誤を行う必要があります。
于 2012-11-27T12:13:22.443 に答える