5

私は自分のアプリでわずかに変更されたダイクストラアルゴリズムを使用していますが、それは非常に遅く、もっと良いアプローチが必要であることを知っています。私の入力データは、相互に指定された移動時間のバス停です（〜400ノードと〜800パス、最大結果深度= 4（最大4バス変更またはなし）。

入力データ（バス路線）：

bus_id | location-from | location-to | travel-time | calendar_switch_for_today
XX | A | B | 12 | 1
XX | B | C | 25 | 1
YY | C | D | 5  | 1
ZZ | A | D | 15 | 0

dijkstraResolve(A,D, '2012-10-10') -> (XX,A,B,12),(XX,B,C,25),(YY,C,D,5) 
=> one bus change, 3 bus stops to final destination
* A->D cant be used as calendar switch is OFF

ご想像のとおり、たとえば主要都市（ノード）がさまざまな都市に170の接続を持っている、より複雑なグラフでは、ダイクストラが遅くなります（5秒以上）。他の方法で目的地に到達する...

うまく適合する他のアルゴリズムを教えていただけますか？

私が探していた：

持っていると素晴らしいでしょう（オプションのものだけ）：-バスの変更回数または時間を最小限にするオプション-代替方法を探すオプション（移動時間が類似している場合）

ヒントをありがとう

4

3 に答える 3

6

多分A*アルゴリズム？参照： http： //en.wikipedia.org/wiki/A-star_algorithm

多分収縮階層？http://en.wikipedia.org/wiki/Contraction_hierarchiesを参照してください。

収縮階層は、非常に優れた、非常に高速なオープンソースルーティングマシン（OSRM）によって実装されます。

http://project-osrm.org/

およびOpenTripPlannerによる：

http://opentripplanner.com/

A *は、多くのルーティングシステムによって実装されています。Googleで検索するだけです。

OpenTripPlannerはマルチモーダルルーティングシステムであり、私が見る限り、プロジェクトと非常によく似ているはずです。

于 2012-09-30T21:50:50.920 に答える
5

A*を探しているようですね。これは、ヒューリスティックを使用して検索を高速化するDjikstraのバリアントです。特定の合理的な仮定の下では、A*が最速の最適アルゴリズムです。常にエンドポイントとの関係を断ち切るようにしてください。

はるかに短い時間でほぼ最適なパスを提供できるA*のバリアントもあります。たとえば、こことここを参照してください。

ベルマンフォード法 （あなたの質問で示唆されているように）は、ダイクストラ法またはA *法よりも遅い傾向があります。これは主に、ここにはない負のエッジウェイトがある場合に使用されます。

于 2012-09-30T21:51:21.507 に答える
0

A*アルゴリズムはこれに最適です。ヒューリスティックを使用することで、パフォーマンスが向上します。

これがあなたが始めるための簡単なチュートリアルです：http ：//www.policyalmanac.org/games/aStarTutorial.htm

于 2012-09-30T21:50:46.543 に答える