兩條邊相連的最小生成樹

Question

我想解決最小生成樹問題的一個較難的版本。

還有N頂點。還有2M邊編號爲1,2，..，2M。該圖連接，無向和加權。我想選擇一些邊緣來使圖形保持連接並使總成本儘可能小。有一個限制：編號爲2k的邊緣和編號爲2k-1的邊緣是並列爲，因此應該選擇兩者或者不應該選擇兩者。所以，如果我想選擇邊緣3，我也必須選擇邊緣4。

那麼，連接圖形的最低總成本是多少？

我的想法：

• 我們叫兩個邊2k和2k+1一個邊緣設置。
• 如果合併兩個不同的組件，我們稱它爲有效的。

• 如果兩條邊都是有效的，我們稱之爲邊集好。

  1. 首先準確地加上m邊緣集合，這些邊集合在成本的增加順序上是好的。然後以成本遞增的順序迭代所有邊集，並且如果至少一個邊有效，則添加集。應該從0到M迭代m。

  2. 運行一個克魯斯卡爾算法，其中有一些變化：邊緣e的成本各不相同。

     • 如果其中包含e邊集是良好，成本：（邊集的成本）/ 2。
     • 否則，費用是：（邊集的成本）。
     • 即使成本發生變化，我也無法證明kruskal算法是否正確。

對不起，我英文不好，但我想解決這個問題。是NP-hard還是某種東西，還是有很好的解決方案？ ：D感謝你提前！

Answer 1

正如我前面推測的那樣，這個問題是NP難的。我不確定不適應性;有一個非常簡單的2-approximation（將每一對分成兩半，保留兩半的全部成本，並運行您最喜愛的香草MST算法）。

給出這個問題的算法，我們可以解決如下的NP難哈密爾頓循環問題。設G =（V，E）爲Hamilton週期的實例。克隆所有其他頂點，用vi'表示vi的克隆。我們複製每一條邊e = {vi，vj}（製作一個多圖;我們可以用簡單的圖進行簡化，代價是清晰度），並且假設v0是任意原始頂點，我們將一個副本與{v0，vi '}，另一個與{v0，vj'}。

沒有MST可以使用少於n對，其中一個將每個克隆的頂點連接到v0。有趣的是，像這樣n對的候選對的另一半可以被解釋爲G的定向子圖，其中每個頂點具有超度1（使用克隆位中的索引作爲尾部）。這個圖連接了原始頂點，當且僅當它是一個漢密爾頓循環。

---

有多種方法可以應用整數編程。這是一個簡單的和更復雜的。首先我們爲每個i制定一個二進制變量x_i即1如果邊緣對2i-1, 2i被選中。問題模板看起來像

minimize sum_i w_i x_i (drop the w_i if the problem is unweighted) 
subject to 
<connectivity> 
for all i, x_i in {0, 1}. 

當然，我已經遺漏了有趣的約束:)。實施連接的一種方法是首先解決這個沒有限制的公式，然後檢查解決方案。如果它連接起來，那麼很好 - 我們完成了。否則，找到一組頂點S這樣有S和其補間無毛邊，並添加約束

sum_{i such that x_i connects S with its complement} x_i >= 1 

和重複。

另一種方法是在求解整數程序的線性鬆弛的求解程序中生成像這樣的約束。通常MIP庫有一個允許這個功能。分數問題具有分數連通性，但是，這意味着要查找最小分數來檢查可行性。我希望這種方法更快，但我必須道歉，因爲我沒有精力來描述它的細節。

Answer 2

我不知道這是否是最好的解決辦法，但我的第一個方法是搜索使用回溯：

1. 所有邊緣對中，紀念那些可以無需斷開圖中移除。
2. 刪除其中的一組並找出剩餘圖形的最佳解決方案。
3. 把這一對放回去，取而代之，找到最好的解決方案。

這個很有效，但是速度慢，不夠好。儘管可以通過一些調整來避免不必要的分支，但也許可以挽救這種做法。

首先，仍然可以去除的邊緣對是一個只有在深入時纔會收縮的集合。因此，在下一次遞歸中，您只需檢查上一組可能可移動的邊對中的那些。此外，由於刪除邊緣對的順序並不重要，因此您不應考慮之前已考慮過的任何邊緣對。

然後，檢查兩個節點是否連接是昂貴的。如果緩存邊緣的替代路由，則可以相對較快地檢查該路由是否仍然存在。如果沒有，則必須執行昂貴的支票，因爲即使這條路線不存在，也可能還有其他路線。

然後，修剪一些樹：可移動邊緣對的集合給出了最優解的權重的下限。此外，任何現有的解決方案都給出了最佳解決方案的上限。如果一組可移動的邊緣甚至沒有機會找到比以前最好的解決方案更好的解決方案，那麼您可以在此停止並回溯。

最後，要貪心。使用常規的貪婪算法不會給你一個最佳的解決方案，但它會迅速提高任何解決方案的標準，使修剪更有效。因此，試圖按照它們的重量損失的順序去除邊緣對。