問題の最短経路または最適/最適な解決策を見つけることについて話している多くのアルゴリズムとアプローチを見つけました。しかし、私がやりたいのは、ある点から別の点への最初の K 最短経路を見つけるアルゴリズムです。私が直面している問題は、ツリーを検索するようなものです。各ステップで、それぞれに重みのある複数のオプションがある場合です。この種の問題に直面するために、どのような種類のアルゴリズムが使用されていますか?
質問する
408 次
3 に答える
1
Jose Santosによる2006 年の論文で、3 つの異なる K 最短経路検索アルゴリズムを比較しています。
于 2010-11-18T16:51:21.123 に答える
0
編集:どうやらリンクをクリックしたようです。新しい質問に答えていると思ったからです。この質問があなたにとってもはや重要ではない場合は、これを無視してください。
あなたが扱っている問題の制限されたバージョンを考えると、これは実装がはるかに簡単になります。注目すべき最も重要なことは、ツリーでは最短パスが 2 つのノード間の唯一のパスであるということです。したがって、BFS トラバーサルをO(n²)実行してツリー内にあるすべてのペアの最短パスを解決し、最小値を取得します。これはおそらく何らかの方法で最適化できますが、それを行うための素朴なアプローチは、距離を時間的にソートし、最小値を取ることです。帳簿をつけると、時間の複雑さのオーバーヘッドなしで、どの距離がどのパスに対応するかを追跡できます。これにより、可能性のある st-pairに KSPA アルゴリズムを使用するよりも複雑さが増します。nkO(n²)O(n² log n)kO(n²)
あなたが実際にソースを修正し、kそのソースからの距離が最小のノードを取得することを意味している場合、1 つの BFS で十分です。ソースとターゲットの両方を修正する場合は、1 つの BFS で十分です。
ツリーの構造について詳しく知らなければ、ノードから下のレベルのノードに向かうすべてのエッジが同じ重みを持つという事実をどのように使用できるかわかりません。
于 2013-08-02T14:52:07.890 に答える
0
円のアルゴリズムの実装: http://code.google.com/p/k-shortest-paths/
より簡単なアルゴリズムと議論: 無向グラフでの KSPA の提案
于 2011-06-03T19:39:21.800 に答える