

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、作為求解NP難解問題的一種新途徑,參數(shù)計算方法受到了人們的廣泛關(guān)注,并被應(yīng)用劍諸多領(lǐng)域難解問題的求解中。Packing和Matching問題是一類重要的NP難解問題,在調(diào)度、代碼優(yōu)化等領(lǐng)域有著重要的應(yīng)用。其中,3D-Matching問題是六個基本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è)計方法,主要的研究工作和創(chuàng)新點包括:
本文以3-Set Packing問題為例,研究了問題解與問題特定實例的關(guān)系。通過對問題解空間結(jié)構(gòu)的深入分析,得到了3-Set Packing問題的求解與問題兩個特殊實例的求解存在著密切的聯(lián)系。基于對特殊實例的求解,提出了3-Set Packing問題時間復(fù)雜度為O*(3.533k)確定性算法,改進
3、了當(dāng)時的最好結(jié)果O*(4.613k)。
對于加權(quán)3-Set Packing問題,本文深入分析了問題實例與目標(biāo)解的關(guān)系,將問題實例分成兩部分處理?;趯栴}實例的分析,得到了特定的問題結(jié)構(gòu)特性,提出了加權(quán)3-Set Packing問題時間復(fù)雜度為O*(10.63k)確定性算法。通過對問題實例結(jié)構(gòu)的進一步劃分,提出了加權(quán)3-Set Packing問題時間復(fù)雜度為O*(7.563k)的確定性參數(shù)算法,改進了當(dāng)時的最好結(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ì),提出了時間復(fù)雜度為O*(4.823k)的確定性參數(shù)算法,改進了當(dāng)時的最好結(jié)果O*(5.473k)。
本文將劃分和排序技術(shù)應(yīng)用到加權(quán)rD-Matching和加權(quán)r-SetPacking問題
5、的算法設(shè)計中,得到了相應(yīng)問題的有效算法。對于加權(quán)rD-Matching問題的給定實例(S,k),對S中的第一列的元素進行劃分,得到了如下性質(zhì):通過枚舉n種可能的劃分,使得存在一種劃分使得最大加權(quán)k-Matching中的第一列元素中有k/2個元素被劃分到一部分中,而另外k/2個元素被劃分劍另一部分中?;谏鲜鲂再|(zhì)并對最大加權(quán)k-Matching中的另外(r-1)k個元素進行有效劃分,提出了時間復(fù)雜度為O*(4(r-1)k+o(k))的確定
6、性參數(shù)算法,改進了以前的最好結(jié)果O*(4rk+o(k))。本文提出的結(jié)果是當(dāng)前求解加權(quán)rD-Matching問題的最好確定性算法。求解加權(quán)rD-Matching的算法可用于求解非加權(quán)3D-Matching問題,得到了時間復(fù)雜度為O*(16k+o(k))的確定性算法,改進了以前的最好結(jié)果O*(21.26k),且本文得到的結(jié)果是當(dāng)前求解非加權(quán)3D-Matching問題的最好結(jié)果。
對于加權(quán)r-Set Packing問題,通過對
7、實例S中元素進行排序,得到了如下性質(zhì):存在對權(quán)值最大的k-Packing的一個劃分,使得權(quán)值最大的k-Packing中有k/2個元素被劃分一個部分中?;谏鲜鲂再|(zhì)并對剩余的(2r-1)k/2個元素進行劃分,本文提出了時間復(fù)雜度為O*(2(2r-1)k+o(k))的確定性算法,改進了當(dāng)前的最好結(jié)果O*(2(2r-1)k+o(k))。求解加權(quán)r-Set Packing問題的算法可用于求解非加權(quán)3-Set Packing問題,得到了時間復(fù)雜度
8、為O*(32k+o(k))的確定性算法,改進了以前的最好結(jié)果O*(3.533k),且本文得到的結(jié)果是當(dāng)前求解非加權(quán)3-SetPacking問題的最好結(jié)果。
本文還研究了加權(quán)點不相交S-path理論的相關(guān)特性,得到了加權(quán)二分圖中加權(quán)點不相交S-path的相關(guān)性質(zhì)。利用加權(quán)點不相交S-path求解加權(quán)P2-Packing問題,提出了加權(quán)P2-Packing問題時間復(fù)雜度為O*(8k)的確定性參數(shù)算法。本文提出的求解加權(quán)P2-P
9、acking的算法同樣適用于求解非加權(quán)的P2-Packing問題,提出了時間復(fù)雜度為O*(8k)的確定性算法,改進了當(dāng)前的最好結(jié)果O*(14.67k)。本文提出的算法足當(dāng)前求解P2-Packing問題的最好結(jié)果。
綜上所述,本文主要研究Packing和Matching問題的參數(shù)算法設(shè)計。通過對3-Set Packing、加權(quán)3-Set Packing、加權(quán)3D-Matching、加權(quán)rD-Matching、加權(quán)r-Set
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- Matching和packing問題的參數(shù)算法研究.pdf
- 求解不等球和不等圓Packing問題的高性能算法研究.pdf
- 帶平衡約束的圓形Packing問題的算法研究.pdf
- 求解矩形packing問題的純粹擬人算法.pdf
- 求解等圓Packing問題的快速優(yōu)化算法研究.pdf
- 帶平衡約束的圓和矩形正交Packing問題的擬物擬人算法研究.pdf
- 若干NP難解問題的參數(shù)化算法研究.pdf
- 求解等圓packing問題的擬物擬人算法.pdf
- 求解等圓packing問題的高性能近似算法.pdf
- 基于知識的約束圓和矩形正交Packing問題的智能搜索算法研究.pdf
- 求解等圓Packing問題的完全擬物算法.pdf
- 圖切割問題的核心化及參數(shù)算法研究.pdf
- 求解等圓packing問題的擬物擬人算法改進策略研究.pdf
- 若干圖修改問題的參數(shù)算法及核心化研究.pdf
- 求解二維矩形packing問題的高效算法設(shè)計.pdf
- 求解長方體Packing問題的最大穴度算法.pdf
- 求解等圓Packing問題的遺傳擬物混合算法.pdf
- 參數(shù)算法中核心化和彩色編碼技術(shù)的研究.pdf
- d-Hitting Set問題的固定參數(shù)化算法.pdf
- 二維矩形Packing問題和大規(guī)模集成電路布圖規(guī)劃問題的算法研究.pdf
評論
0/150
提交評論