1

無向の重み付きエッジを持つ完全グラフがあり、グラフノードのサブセットを通じて最低のコストサイクルを見つける必要があります。巡回セールスマンとは異なり、どのノードにも複数回アクセスでき、すべてのノードにアクセスする必要はありません。コストによって、パスの通過エッジの重みの合計が最小になる必要があります。

たとえば、隣接行列形式のグラフは次のとおりです。

  a b c d
a 0 3 4 5
b 3 0 2 4
c 4 2 0 1
d 5 4 1 0

ここで、各エッジの重みは各要素に使用されます。で開始および終了するサイクルはa、次[b,d]のようになります。

[a,b,d,a] -> 3+4+5 = 12
[a,b,d,b,a] -> 3+4+4+3 = 14
[a,b,c,d,c,a] -> 3+2+1+1+4 = 11

これに最適なアルゴリズム、または本当に優れたヒューリスティックアルゴリズムはありますか？

4

1 に答える 1

3

で開始および終了するサイクルはa、[b,d]単にサイクルがノード a、b、d を訪問しなければならないことを意味します。[a,b,d,a] = [b,d,a,b]（右に循環）。あなたの問題はk-TSPと呼ばれます。ここを参照してください。しかし、これを実装するのは非常に難しく、探しているものではないかもしれません。

なので、もっと簡単な方法を教えます。最初に、これらのノードのみを通過する最短サイクルを構築します。次に、各エッジを 2 つのノード間の最小パスに置き換えます。合理的だと思います。最適性は除外します。手順は次のとおりです。

  • V=nodes E=edges および M=must-visit ノード。
  • M でTSPCを実行して (他のノードを使用せずに)サイクルを作成し、エッジを追加してサイクルを作成します。
  • ここで、すべてのノード V を使用します。 の各エッジに対してuv、次の操作Cを行います。
  • Dijsktra のアルゴリズムを使用してとのw間の最短経路を見つけます(グラフに負のサイクルがないはずです)。uv
  • に置き換えuvますw。
于 2013-03-02T12:42:38.797 に答える