組合最優問題解決方法

A. 組合優化問題的實例

在研究組合優化問題時，關鍵在於問題的歸類和轉化。例如，最小公約問題的演算法可以應用在解決多個問題上，如問題a和問題b，而通過將問題b規約為問題b'，問題b的解決也可以藉助於最小公約問題的演算法。一個問題能否通過m-極限演算法解決，本質上是看它是否能歸入m的大方向或細分領域。

以下是幾個實例來說明這些概念：

• 最大獨立集：尋找無相鄰頂點的最大集合，其對立面是最大匹配，通過最大匹配的解來計算最小頂點覆蓋。


• 最小頂點覆蓋：選擇最少的點覆蓋所有邊，等於所有節點減去最大獨立集的節點。


• 最大匹配：在二分圖中找到不交匯的邊的最大集合，其對偶問題涉及邊的分配和權重優化。


• 最短環路問題（TSP）：尋找經過每個點一次的最短環路，去除重復路徑。


• 最大割問題（MaxCUT）：在圖中找到最大邊權和的劃分，使得一側的邊權和最大化。

固定負擔網路流涉及節點需求平衡和弧的容量與成本，而3D-Bin Packing則是關於物品如何最有效地填充三維空間。TSP的簡化版本（Dantzig版本）則是針對給定距離的點，尋找最短的完整環路。

值得注意的是，線性規劃問題的規約有時可能會產生冗餘約束或凸包問題，這需要在處理時特別注意。組合優化問題通常通過對象和關系節點構建的二部圖形式展現，其中二部圖最長圈問題就是一個典型實例。