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

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

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

3、了當(dāng)時(shí)的最好結(jié)果O*(4.613k)。
　　 對于加權(quán)3-Set Packing問題，本文深入分析了問題實(shí)例與目標(biāo)解的關(guān)系，將問題實(shí)例分成兩部分處理?；趯栴}實(shí)例的分析，得到了特定的問題結(jié)構(gòu)特性，提出了加權(quán)3-Set Packing問題時(shí)間復(fù)雜度為O*(10.63k)確定性算法。通過對問題實(shí)例結(jié)構(gòu)的進(jìn)一步劃分，提出了加權(quán)3-Set Packing問題時(shí)間復(fù)雜度為O*(7.563k)的確定性參數(shù)算法，改進(jìn)了當(dāng)時(shí)的最好結(jié)果O*(1

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

5、的算法設(shè)計(jì)中，得到了相應(yīng)問題的有效算法。對于加權(quán)rD-Matching問題的給定實(shí)例(S，k)，對S中的第一列的元素進(jìn)行劃分，得到了如下性質(zhì)：通過枚舉n種可能的劃分，使得存在一種劃分使得最大加權(quán)k-Matching中的第一列元素中有k/2個(gè)元素被劃分到一部分中，而另外k/2個(gè)元素被劃分劍另一部分中。基于上述性質(zhì)并對最大加權(quán)k-Matching中的另外(r-1)k個(gè)元素進(jìn)行有效劃分，提出了時(shí)間復(fù)雜度為O*(4(r-1)k+o(k))的確定

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

7、實(shí)例S中元素進(jìn)行排序，得到了如下性質(zhì)：存在對權(quán)值最大的k-Packing的一個(gè)劃分，使得權(quán)值最大的k-Packing中有k/2個(gè)元素被劃分一個(gè)部分中。基于上述性質(zhì)并對剩余的(2r-1)k/2個(gè)元素進(jìn)行劃分，本文提出了時(shí)間復(fù)雜度為O*(2(2r-1)k+o(k))的確定性算法，改進(jìn)了當(dāng)前的最好結(jié)果O*(2(2r-1)k+o(k))。求解加權(quán)r-Set Packing問題的算法可用于求解非加權(quán)3-Set Packing問題，得到了時(shí)間復(fù)雜度

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

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