完整圖上的最小成本週期

Question

我有一個complete graph帶有無向加權邊，需要通過圖節點的子集找到成本最低的cycle。不像在Travelling Salesman，任何節點可以訪問超過一次和不需要訪問所有節點更多，並通過成本我指的是路徑應具有遍歷邊權值和最小。

例如，這裏是在adjacency matrix形式的曲線圖：

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 

是否存在最佳的算法對於這一點，還是一個很好的啓發呢？

Answer 1

循環開始和結束在a和包括[b,d]只是意味着循環必須訪問節點a，b，d。 [a,b,d,a] = [b,d,a,b]（右轉）。你的問題被稱爲k-TSP。請參閱here。但是這很難實現，可能並不是你想要的。

所以我會給你一個更簡單的方法。首先構造通過這些節點的最短週期。然後用兩個節點之間的最小路徑替換每條邊。我認爲這是合理的，我忽略了最優性。這裏是步驟：

• V =節點E =邊緣和M =必須訪問節點。
• 通過在M上運行TSP（不使用其他節點）創建週期C，添加額外的邊緣以創建循環。
現在使用的所有節點五，對於在該 C每個邊緣 uv
• ，做到：
• 查找使用Dijsktra's algorithmu和v之間的最短路徑w（應該是在圖形沒有負循環）。
• 將uv替換爲w。