Packing和Matching問題的參數(shù)化算法研究.pdf

1、作為求解NP難解問題的一種新途徑，參數(shù)計算方法受到了人們的廣泛關注，并被應用劍諸多領域難解問題的求解中。Packing和Matching問題是一類重要的NP難解問題，在調(diào)度、代碼優(yōu)化等領域有著重要的應用。其中，3D-Matching問題是六個基本NP完全問題之一。本文主要以3-Set Packing問題、加權3-Set Packing問題、加權3D-Matching問題、加權rD-Matching問題、加權r-Set Packing問題

2、、加權P2-Packing問題為例，討論了Packing和Matching問題的參數(shù)算法設計方法，主要的研究工作和創(chuàng)新點包括：
　　 本文以3-Set Packing問題為例，研究了問題解與問題特定實例的關系。通過對問題解空間結構的深入分析，得到了3-Set Packing問題的求解與問題兩個特殊實例的求解存在著密切的聯(lián)系?；趯μ厥鈱嵗那蠼?，提出了3-Set Packing問題時間復雜度為O*(3.533k)確定性算法，改進

3、了當時的最好結果O*(4.613k)。
　　 對于加權3-Set Packing問題，本文深入分析了問題實例與目標解的關系，將問題實例分成兩部分處理。基于對問題實例的分析，得到了特定的問題結構特性，提出了加權3-Set Packing問題時間復雜度為O*(10.63k)確定性算法。通過對問題實例結構的進一步劃分，提出了加權3-Set Packing問題時間復雜度為O*(7.563k)的確定性參數(shù)算法，改進了當時的最好結果O*(1

4、2.83k)。
　　 對于加權3D-Matching問題，通過對問題的結構特性的研究，得到了如下性質(zhì)：k-matching中存在兩列使得該兩列中至少有2k/3元素被包含在(k+1)-matching中所對應的兩列中?；诮o出的性質(zhì)，提出了時間復雜度為O*(4.823k)的確定性參數(shù)算法，改進了當時的最好結果O*(5.473k)。
　　 本文將劃分和排序技術應用到加權rD-Matching和加權r-SetPacking問題

5、的算法設計中，得到了相應問題的有效算法。對于加權rD-Matching問題的給定實例(S，k)，對S中的第一列的元素進行劃分，得到了如下性質(zhì)：通過枚舉n種可能的劃分，使得存在一種劃分使得最大加權k-Matching中的第一列元素中有k/2個元素被劃分到一部分中，而另外k/2個元素被劃分劍另一部分中?；谏鲜鲂再|(zhì)并對最大加權k-Matching中的另外(r-1)k個元素進行有效劃分，提出了時間復雜度為O*(4(r-1)k+o(k))的確定

6、性參數(shù)算法，改進了以前的最好結果O*(4rk+o(k))。本文提出的結果是當前求解加權rD-Matching問題的最好確定性算法。求解加權rD-Matching的算法可用于求解非加權3D-Matching問題，得到了時間復雜度為O*(16k+o(k))的確定性算法，改進了以前的最好結果O*(21.26k)，且本文得到的結果是當前求解非加權3D-Matching問題的最好結果。
　　 對于加權r-Set Packing問題，通過對

7、實例S中元素進行排序，得到了如下性質(zhì)：存在對權值最大的k-Packing的一個劃分，使得權值最大的k-Packing中有k/2個元素被劃分一個部分中?；谏鲜鲂再|(zhì)并對剩余的(2r-1)k/2個元素進行劃分，本文提出了時間復雜度為O*(2(2r-1)k+o(k))的確定性算法，改進了當前的最好結果O*(2(2r-1)k+o(k))。求解加權r-Set Packing問題的算法可用于求解非加權3-Set Packing問題，得到了時間復雜度

8、為O*(32k+o(k))的確定性算法，改進了以前的最好結果O*(3.533k)，且本文得到的結果是當前求解非加權3-SetPacking問題的最好結果。
　　 本文還研究了加權點不相交S-path理論的相關特性，得到了加權二分圖中加權點不相交S-path的相關性質(zhì)。利用加權點不相交S-path求解加權P2-Packing問題，提出了加權P2-Packing問題時間復雜度為O*(8k)的確定性參數(shù)算法。本文提出的求解加權P2-P

9、acking的算法同樣適用于求解非加權的P2-Packing問題，提出了時間復雜度為O*(8k)的確定性算法，改進了當前的最好結果O*(14.67k)。本文提出的算法足當前求解P2-Packing問題的最好結果。
　　 綜上所述，本文主要研究Packing和Matching問題的參數(shù)算法設計。通過對3-Set Packing、加權3-Set Packing、加權3D-Matching、加權rD-Matching、加權r-Set