約100個のノードと約200個のエッジを持つ無向グラフがあります。1つのノードには「start」というラベルが付けられ、もう1つは「end」というラベルが付けられ、「mustpass」というラベルが付けられたノードが約12個あります。
'start'で始まり、'end'で終わり、すべての' mustpass'ノードを（任意の順序で）通過する、このグラフの最短経路を見つける必要があります。
（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txtは問題のグラフであり、ペンシルバニア州ランカスターのトウモロコシの迷路を表しています）
これを巡回セールスマン問題と比較している人は、おそらくあなたの質問を注意深く読んでいないでしょう。TSP の目的は、すべての頂点を訪れる最短のサイクル(ハミルトン サイクル)を見つけることです。これは、すべてのノードに「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) は、本当に制限的な制約がない限り、実際にはピーナッツです。]
ダイクストラのアルゴリズムを実行して、すべての重要なノード（開始、終了、および通過する必要がある）間の最短経路を見つけます。次に、深さ優先探索により、すべてのノードの開始に接する結果のサブグラフを通る最短経路が示されます。 。mustpasses...end
これには 2 つの問題があります... Steven Lowe はこれを指摘しましたが、問題の後半については十分に考慮していませんでした。
最初に、すべての重要なノード (開始、終了、必須パス) 間の最短パスを検出する必要があります。これらのパスが検出されると、単純化されたグラフを作成できます。新しいグラフの各エッジは、元のグラフの 1 つの重要なノードから別のノードへのパスです。ここで最短経路を見つけるために使用できる多くの経路探索アルゴリズムがあります。
ただし、この新しいグラフを作成すると、まさに巡回セールスマンの問題が発生します (まあ、ほとんど... 出発点に戻る必要はありません)。上記のこれに関する投稿のいずれかが適用されます。
実際、あなたが投稿した問題は巡回セールスマンに似ていますが、単純な経路探索の問題に近いと思います。すべてのノードを訪問する必要はなく、可能な限り短い時間 (距離) で特定のノードのセットを訪問する必要があります。
この理由は、巡回セールスマン問題とは異なり、トウモロコシの迷路では、マップ上の任意のポイントから別のポイントに直接移動することができず、そこに到達するために他のノードを通過する必要がないためです。
実際、検討すべき手法として A* パスファインディングをお勧めします。これを設定するには、どのノードが他のどのノードに直接アクセスできるか、および特定のノードからの各ホップの「コスト」を決定します。この場合、ノードの間隔が比較的狭いように見えるため、各「ホップ」のコストは等しいように見えます。A* はこの情報を使用して、任意の 2 点間の最小コスト パスを見つけることができます。ポイント A からポイント B に移動し、その間に約 12 を訪問する必要があるため、パスファインディングを使用した力ずくのアプローチでもまったく問題はありません。
考慮すべき代替案です。それは確かに巡回セールスマン問題に非常によく似ており、それらは読むのに適した論文ですが、よく見ると過度に複雑なものだけであることがわかります。^_^ これは、以前にこのようなことを扱ったビデオ ゲーム プログラマーの考えから来ています。
これはTSP 問題ではなく、NP 困難でもありません。なぜなら、元の質問では、必須パス ノードを 1 回だけ訪問する必要がないからです。これにより、ダイクストラのアルゴリズムを介してすべてのパスする必要があるノード間の最短パスのリストをコンパイルした後、ブルートフォースだけでなく、答えがはるかに簡単になります。より良い方法があるかもしれませんが、簡単な方法は、単純にバイナリ ツリーを逆方向に処理することです。ノードのリスト [start,a,b,c,end] を想像してください。単純な距離の合計 [start->a->b->c->end] これがあなたの新しい目標距離です。[start->a->c->b->end] を試して、それがより良い場合は、それをターゲットとして設定します (ノードのパターンから来たことを思い出してください)。順列を逆方向に作業する：
そのうちの 1 つが最短になります。
(もしあれば、「複数回訪れた」ノードはどこにありますか? それらは、最短パスの初期化ステップで隠されているだけです。a と b の間の最短パスには、c または終点が含まれる場合があります。気にする必要はありません。 )
アンドリュー・トップは正しい考えを持っています：
1) Djikstra のアルゴリズム 2) いくつかの TSP ヒューリスティック。
Lin-Kernighan ヒューリスティックをお勧めします。これは、NP 完全問題で最もよく知られているものの 1 つです。他に覚えておくべき唯一のことは、ステップ 2 の後でグラフを再度展開した後、展開したパスにループが含まれている可能性があるため、それらを短絡する必要があるということです (パスに沿った頂点の次数を見てください)。
このソリューションが最適なソリューションと比較してどれだけ優れているかは、実際にはわかりません。おそらく、短絡に関係する病理学的なケースがいくつかあります。結局のところ、この問題は Steiner Tree によく似ています: http://en.wikipedia.org/wiki/Steiner_treeであり、たとえばグラフを縮小して Kruskal を実行するだけでは Steiner Tree を概算することはできません。
ノードとエッジの量が比較的限られていることを考慮すると、考えられるすべてのパスを計算して、最短のパスを選択できる可能性があります。
一般に、これは巡回セールスマン問題として知られており、使用するアルゴリズムに関係なく、非決定論的多項式ランタイムがあります。
どこにも言及されていないことの 1 つは、同じ頂点がパスで複数回アクセスされても問題ないかどうかです。ここでの回答のほとんどは、同じエッジに複数回アクセスしても問題ないことを前提としていますが、私の考えでは (パスは同じ頂点に複数回アクセスしてはいけません!) 、同じ頂点に 2 回アクセスすることは問題ありません。
したがって、ブルート フォース アプローチは引き続き適用されますが、パスの各サブセットを計算しようとすると、既に使用されている頂点を削除する必要があります。
ダースの「必見」ノードでブルートフォースを使用するのはどうですか。12 個のノードのすべての可能な組み合わせを十分に簡単にカバーできます。これにより、それらをカバーするために従うことができる最適な回路が得られます。
これで問題は単純化され、開始ノードからサーキットまでの最適なルートを見つけるというものになりました。次に、それらをカバーするまでたどり、そこから最後までのルートを見つけます。
最終パスは次のもので構成されます。
開始 -> 回路へのパス* -> ノードを訪問する必要がある回路 -> 終了へのパス* -> 終了
このように*でマークしたパスを見つけます
これらのそれぞれについて、開始ノードから回路上のすべてのポイントまで A* 検索を実行します。回路上の次および前のノードから最後まで A* 検索を実行します (どちらの方向にも回路をたどることができるため)。最終的には多くの検索パスがあり、コストが最も低いパスを選択できます。
検索をキャッシュすることによる最適化の余地はたくさんありますが、これは良い解決策を生み出すと思います。
ただし、最適な解決策を探すにはほど遠いものです。なぜなら、それには、必ず訪れなければならない回路を検索内に残すことが含まれる可能性があるからです。