無向の重み付きエッジを持つ完全グラフがあり、グラフノードのサブセットを通じて最低のコストサイクルを見つける必要があります。巡回セールスマンとは異なり、どのノードにも複数回アクセスでき、すべてのノードにアクセスする必要はありません。コストによって、パスの通過エッジの重みの合計が最小になる必要があります。
たとえば、隣接行列形式のグラフは次のとおりです。
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
これに最適なアルゴリズム、または本当に優れたヒューリスティックアルゴリズムはありますか?