

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、覆蓋問(wèn)題是計(jì)算幾何和組合優(yōu)化領(lǐng)域中的一類重要的難解問(wèn)題,對(duì)此類問(wèn)題的研究不但具有重大的理論意義,而且在生物計(jì)算、電路設(shè)計(jì)、網(wǎng)絡(luò)選址、工藝流程分析等應(yīng)用領(lǐng)域具有許多重要的實(shí)際意義。人們從實(shí)際應(yīng)用中抽象出了許多的覆蓋問(wèn)題,如頂點(diǎn)覆蓋問(wèn)題、樹(shù)覆蓋問(wèn)題、超平面覆蓋問(wèn)題、集合覆蓋問(wèn)題等。本文主要對(duì)超平面覆蓋問(wèn)題和基于保證值的完美匹配圖中頂點(diǎn)覆蓋問(wèn)題進(jìn)行了深入的研究。
對(duì)于超平面覆蓋問(wèn)題,本文首先通過(guò)深入分析直線覆蓋問(wèn)題(超平面覆蓋問(wèn)
2、題的一個(gè)特例)的結(jié)構(gòu)特征,提出了一個(gè)時(shí)間復(fù)雜度為O*((0.736κ)κ)的確定性的參數(shù)算法,較大地改進(jìn)了以前最好的時(shí)間復(fù)雜度為O*((κ/2.2)2κ)的算法。更一般地,我們還提出了關(guān)于超平面覆蓋問(wèn)題的確定性的參數(shù)算法,其時(shí)間復(fù)雜度為O*((dκ)!/((d!)κκ!)),較之前的時(shí)間復(fù)雜度為O*(κd(κ+1))的算法亦有較大改進(jìn)。
對(duì)于完美匹配圖中基于保證值的項(xiàng)點(diǎn)覆蓋問(wèn)題,已有相關(guān)文獻(xiàn)提出了一個(gè)時(shí)間復(fù)雜度為O*(15
3、κ)的固定參數(shù)算法。本文對(duì)此算法作了進(jìn)一步的改進(jìn),其整體思路是首先采用迭代壓縮技術(shù)將原問(wèn)題轉(zhuǎn)化為求一個(gè)特殊的具有完美匹配的K(o)nig圖上的最小頂點(diǎn)覆蓋問(wèn)題,然后將后者進(jìn)一步轉(zhuǎn)化為參數(shù)化2-ASLASAT問(wèn)題的一個(gè)變種問(wèn)題(KPM-2-AASAT問(wèn)題),最后,通過(guò)深入分析問(wèn)題的結(jié)構(gòu)特征,我們采用分枝搜索技術(shù)和隱含參數(shù)技術(shù)求解KPM-2-AASAT問(wèn)題。整個(gè)算法的時(shí)間復(fù)雜度為O*(9κ),較之前最好結(jié)果有較大改進(jìn)。
本文最
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 頂點(diǎn)覆蓋問(wèn)題的確定參數(shù)可解算法研究.pdf
- 參數(shù)化點(diǎn)覆蓋及最小點(diǎn)覆蓋問(wèn)題研究.pdf
- 集合覆蓋問(wèn)題的算法研究及其應(yīng)用.pdf
- 最小頂點(diǎn)覆蓋問(wèn)題的幾種DNA算法研究.pdf
- s-路徑頂點(diǎn)覆蓋問(wèn)題的算法研究.pdf
- 粗集覆蓋算法及其相關(guān)問(wèn)題的研究.pdf
- Matching和packing問(wèn)題的參數(shù)算法研究.pdf
- Packing和Matching問(wèn)題的參數(shù)化算法研究.pdf
- 加權(quán)邊支配集問(wèn)題的參數(shù)算法研究.pdf
- 若干NP難解問(wèn)題的參數(shù)化算法研究.pdf
- m臺(tái)同類機(jī)覆蓋問(wèn)題的LPT算法.pdf
- 傳感器網(wǎng)絡(luò)柵欄覆蓋問(wèn)題的調(diào)度算法研究.pdf
- WSN中基于帆布協(xié)議的覆蓋問(wèn)題與路由算法研究.pdf
- 覆蓋算法的增量學(xué)習(xí)研究.pdf
- 文本聚類算法的參數(shù)設(shè)置問(wèn)題研究.pdf
- 基于覆蓋的聚類算法研究.pdf
- 基于樹(shù)分解的難解問(wèn)題的參數(shù)算法研究.pdf
- 基于蟻群算法的集合覆蓋問(wèn)題求解及其應(yīng)用研究.pdf
- 基于黃蜂群算法的群機(jī)器人區(qū)域覆蓋問(wèn)題研究.pdf
- 無(wú)線傳感器網(wǎng)絡(luò)觀測(cè)覆蓋問(wèn)題及其優(yōu)化算法的研究.pdf
評(píng)論
0/150
提交評(píng)論