覆蓋問(wèn)題的參數(shù)算法研究.pdf

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)。
　　 本文最