[解決済み] グラフの中で特定のノードを訪れる最短経路を求めよ

質問

約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」とラベル付けされています。

あなたの場合、'mustpass' というラベルが付いたノードが約 12 個しかなく、12! がかなり小さい (479001600) ことを考えると、単純に 'mustpass' ノードのすべての順列を試して、'start' から 'end' までこの順序で 'mustpass' ノードを訪れる最短パスを見ることができます -- それは単に、そのリスト内のすべての連続した 2 つのノード間の最短パスの連結になるでしょう。

言い換えれば、まず各頂点のペアの間の最短距離を求めます (Dijkstra のアルゴリズムなどを使用できますが、これらの小さな数 (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」ノードがある場合、その実行時間はO(n ³ であり、100^3+(12!)(100)はよっぽどの制約がない限り、実質的に大したことはない。