特定のノードを訪問するグラフで最短経路を見つける

StackOverflow https://stackoverflow.com/questions/222413

  •  03-07-2019
  •  | 
  •  

質問

約100個のノードと約200個のエッジを持つ無向グラフがあります。 1つのノードには「開始」というラベルが付けられ、1つには「終了」というラベルが付けられ、「mustpass」というラベルが付けられたダースが約12個あります。

「start」で始まり「end」で終わり、すべての「mustpass」ノードを（任意の順序で）通過するこのグラフの最短経路を見つける必要があります。

（ http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txtは問題のグラフです-ペンシルバニア州ランカスターのトウモロコシの迷路を表しています）

役に立ちましたか？

解決

これを巡回セールスマン問題と比較している他の誰もが、あなたの質問を注意深く読んでいないのでしょう。 TSPの目的は、頂点を訪れる最短サイクル（ハミルトニアンサイクル）を見つけることです。これは、「mustpass」とラベル付けされた every ノードを持つことに相当します。

「mustpass」とラベル付けされたダースが約12個しかない場合、12個与えられます。かなり小さい（479001600）、「mustpass」ノードのみのすべての順列を試すことができ、「mustpass」ノードをその順序で訪れる「start」から「end」までの最短経路を見ることができます-それは単にそのリスト内の連続する2つのノード間の最短パスを連結します。

つまり、最初に、頂点の各ペア間の最短距離を見つけます（ダイクストラのアルゴリズムなどを使用できますが、それらの小さな数（100ノード）で、最も簡単なコード Floyd-Warshallアルゴリズムは時間内に実行されます）。次に、これをテーブルに入れたら、「mustpass」ノードのすべての順列とそれ以外の順列を試します。

次のようなもの：

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

（もちろんそれは実際のコードではありません。実際のパスが必要な場合は、どの順列が最短距離を与えるか、またすべてのペアの最短パスが何であるかを追跡する必要がありますが、アイデアは得られます。 ）

適切な言語であれば、せいぜい数秒で実行されます：
[n個のノードとk個の「mustpass」ノードがある場合、その実行時間は、Floyd-Warshall部分ではO（n 3 ）、すべての順列部分ではO（k！n）です。 100 ^ 3 +（12！）（100）は、非常に制限的な制約がない限り、実質的にピーナッツです。]

他のヒント

ジクストラのアルゴリズムを実行して、すべての重要なノード間の最短パス（開始、終了）を見つけます、およびmust-pass）、深さ優先のトラバーサルにより、すべてのノードstart ... mustpasses ... endに触れる結果のサブグラフを通る最短パスがわかります

実際に投稿した問題は巡回セールスマンに似ていますが、単純な経路探索の問題に近いと思います。ありとあらゆるノードにアクセスする必要はなく、可能な限り最短の時間（距離）で特定のノードセットにアクセスするだけです。

この理由は、巡回セールスマンの問題とは異なり、トウモロコシ迷路では他のノードを通過せずに地図上のある地点から他の地点に直接移動できないためです。

実際に検討する手法として、A *パスファインディングをお勧めします。これは、どのノードが他のどのノードに直接アクセスできるか、および「コスト」が何であるかを決定することにより設定します。特定のノードからの各ホップのこの場合、各「ホップ」はノードは比較的狭い間隔に見えるため、同じコストになる可能性があります。 A *はこの情報を使用して、任意の2点間の最低コストパスを見つけることができます。ポイントAからポイントBに行き、その間に約12を訪れる必要があるため、パスファインディングを使用したブルートフォースアプローチでもまったく問題はありません。

考慮すべき代替案。巡回セールスマンの問題のように非常に見えますが、これらは読み進めるのに適した論文ですが、よく見てみると、複雑すぎることがわかります。 ^ _ ^これは、以前にこの種のことを扱ったビデオゲームプログラマの心から来ています。

これは2つの問題です... Steven Loweはこれを指摘しましたが、問題の後半を十分に尊重していませんでした。

最初に、すべての重要なノード（開始、終了、mustpass）間の最短パスを発見する必要があります。これらのパスが検出されると、新しいグラフの各エッジが元のグラフの1つの重要なノードから別のノードへのパスである単純化されたグラフを作成できます。ここで最短経路を見つけるために使用できる多くの経路探索アルゴリズムがあります。

ただし、この新しいグラフを作成すると、巡回セールスマンの問題が発生します（ほとんど...出発点に戻る必要はありません）。これに関する上記の投稿はすべて適用されます。

Andrew Topには正しい考えがあります：

1）ジクストラのアルゴリズム 2）いくつかのTSPヒューリスティック。

Lin-Kernighanヒューリスティックをお勧めします。これは、NP Complete問題で最もよく知られているものの1つです。覚えておくべき他の唯一のことは、ステップ2の後でグラフを再度展開した後、展開したパスにループがある可能性があるため、それらを短絡させる必要があります（パスに沿った頂点の度合いを見てください）。

実際、このソリューションが最適と比較してどれだけ良いかはわかりません。おそらく短絡に関係するいくつかの病理学的なケースがあります。結局のところ、この問題はSteiner TreeのようなLOTに見えます： http://en.wikipedia.org/wiki/Steiner_tree グラフを縮小してクラスカルを実行するだけでは、シュタイナーツリーを正確に近似することはできません。

これはTSPの問題ではなく、NPハードではありません。元の質問では、パスを通過する必要があるノードは1回だけアクセスする必要がないためです。これにより、すべてのパスパスノード間の最短パスのリストをダイクストラのアルゴリズムを介してコンパイルした後、ブルートフォースに比べて答えがはるかに簡単になります。より良い方法があるかもしれませんが、単純な方法は単純にバイナリツリーを逆方向に処理することです。ノードのリストを想像してください[start、a、b、c、end]。単純な距離を合計する[start-＆gt; a-＆gt; b-＆gt; c-＆gt; end]これは、ビートの新しい目標距離です。 [start-＆gt; a-＆gt; c-＆gt; b-＆gt; end]を試してみて、それがターゲットとして設定した方がよい場合（そして、それがノードのパターンから来たことを思い出してください）。順列を逆にたどります：

  • [start-＆gt; a-＆gt; b-＆gt; c-＆gt; end]
  • [start-＆gt; a-＆gt; c-＆gt; b-＆gt; end]
  • [start-＆gt; b-＆gt; a-＆gt; c-＆gt; end]
  • [start-＆gt; b-＆gt; c-＆gt; a-＆gt; end]
  • [start-＆gt; c-＆gt; a-＆gt; b-＆gt; end]
  • [start-＆gt; c-＆gt; b-＆gt; a-＆gt; end]

そのうちの1つが最短になります。

（「複数回訪問した」ノードがある場合、それらは最短パスの初期化ステップで非表示になります。aとbの間の最短パスにはcまたはエンドポイントが含まれる場合があります。気にする必要があります）

ノードとエッジの量は比較的有限であると考えられるため、おそらくすべての可能なパスを計算し、最短のパスを取ることができます。

一般にこれは巡回セールスマン問題として知られ、使用するアルゴリズムに関係なく、非決定的な多項式ランタイムを持ちます。

http://en.wikipedia.org/wiki/Traveling_salesman_problem

ダースの「必見」ノードでブルートフォースを使用するのはどうですか。 12のノードのすべての可能な組み合わせを十分に簡単にカバーできます。これにより、それらをカバーするために従うことができる最適な回路が残ります。

問題は、開始ノードから回路までの最適なルートを見つけることで簡単になり、それらをカバーするまで辿り、そこから最後までのルートを見つけます。

最終パスは次で構成されます：

開始-＆gt;サーキットへのパス*-＆gt;巡回しなければならないノードの回路-＆gt;終了パス*-＆gt;終了

このように*でマークしたパスが見つかります

開始ノードから回線上のすべてのポイントまでA *検索を実行します これらのそれぞれについて、回線上の次および前のノードから最後までA *検索を実行します（どちらの方向にも巡回できるため） 最終的には多くの検索パスが得られるため、最もコストの低いものを選択できます。

検索をキャッシュすることで最適化の余地はたくさんありますが、これは良い解決策を生み出すと思います。

ただし、最適な解決策を探すことには近づきません。これは、検索内の必見の回路を離れる必要があるためです。

どこにも言及されていないことの1つは、パス内で同じ頂点に複数回アクセスしても問題ないかどうかです。ここでの回答のほとんどは、同じエッジに複数回アクセスしても問題ないと想定していますが、私の質問では、パスは同じ頂点に複数回アクセスしてはいけません！ not ok同じ頂点を2回訪問します。

したがって、ブルートフォースのアプローチが適用されますが、パスの各サブセットを計算しようとするときに、既に使用されている頂点を削除する必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top