若干NP難解問(wèn)題的參數(shù)化算法研究.pdf

1、NP難解問(wèn)題是理論計(jì)算機(jī)科學(xué)的主要研究對(duì)象,對(duì)NP難解問(wèn)題提出實(shí)際有效的固定參數(shù)可解算法是理論計(jì)算機(jī)科學(xué)中的一個(gè)新的研究方向。
　　 本文以Matching、Packing、Maximum Cut和MultiCut等經(jīng)典的NP難解問(wèn)題為研究對(duì)象,在深入挖掘問(wèn)題結(jié)構(gòu)中新特點(diǎn)、新性質(zhì)的基礎(chǔ)上,運(yùn)用多種參數(shù)計(jì)算技術(shù)對(duì)它們提出了一系列的固定參數(shù)可解算法。其主要研究工作包括:
　　 帶權(quán)的m-Set Packing、m-D Mat

2、ching問(wèn)題以前一直是用近似算法求解的,本文運(yùn)用參數(shù)計(jì)算理論對(duì)該類問(wèn)題進(jìn)行了研究,首次證明了該類問(wèn)題是固定參數(shù)可解的。本文首先運(yùn)用最新的著色技術(shù)和動(dòng)態(tài)規(guī)劃技術(shù)對(duì)帶權(quán)的m-Set Packing問(wèn)題提出了一個(gè)時(shí)間復(fù)雜度為O(12.2mknO(1)的固定參數(shù)可解算法,接著在此基礎(chǔ)上利用問(wèn)題本身的結(jié)構(gòu)特點(diǎn)對(duì)帶權(quán)的m-D Matching問(wèn)題提出了一個(gè)時(shí)間復(fù)雜度為O(12.2(m-1)knO(1)的固定參數(shù)可解算法,然后對(duì)帶權(quán)的3-D Mat

3、ching問(wèn)題提出了一個(gè)時(shí)間復(fù)雜度為D(5.483k2z)的固定參數(shù)枚舉算法,其中z表示需要枚舉的權(quán)值最優(yōu)解的個(gè)數(shù)。
　　 針對(duì)3-D Matching參數(shù)化計(jì)數(shù)問(wèn)題目前還不存在固定參數(shù)可解的精確算法,本文提出了一個(gè)基于Monte-Carlo自適應(yīng)覆蓋算法的固定參數(shù)可解隨機(jī)近似算法。即對(duì)于一個(gè)含有n個(gè)三元組的集合S,給定一個(gè)整數(shù)k和兩個(gè)正實(shí)數(shù)ε和δ,該算法能在時(shí)間O(5.483kn21n(2/δ)/ε2)內(nèi)返回一個(gè)數(shù)N,使得Pr

4、ob[(1-ε)No≤(1+ε)N0]≥1-δ,其中N0表示S中大小為k的matching的精確個(gè)數(shù)。在設(shè)計(jì)該隨機(jī)近似算法時(shí),本文的關(guān)鍵發(fā)現(xiàn)是3-D Matching參數(shù)化計(jì)數(shù)問(wèn)題通過(guò)著色技術(shù)可以轉(zhuǎn)化為標(biāo)準(zhǔn)的集合并集計(jì)數(shù)問(wèn)題。
　　 Maximum Cut問(wèn)題通常是用近似算法來(lái)求解的,本文運(yùn)用參數(shù)計(jì)算理論對(duì)該問(wèn)題進(jìn)行了研究。首先對(duì)該問(wèn)題及其相關(guān)概念進(jìn)行了參數(shù)化定義,然后對(duì)參數(shù)化Maximum Cut問(wèn)題提出了一種基于隨機(jī)劃分技術(shù)

5、的隨機(jī)算法。該隨機(jī)算法依次將實(shí)例圖的頂點(diǎn)進(jìn)行[1n(1/ε)]×2k(0<ε＜1)次隨機(jī)劃分,并選擇其中權(quán)值最大的k-劃分作為輸出解,因而能在時(shí)間O*(1n(1/ε)2k)內(nèi)以至少1-ε的概率找到目標(biāo)解。接著在此基礎(chǔ)上運(yùn)用最新改進(jìn)的(n,k)-全集劃分技術(shù)對(duì)參數(shù)化Maximum Cut問(wèn)題提出了一個(gè)時(shí)間復(fù)雜度為O*(22k+12log2(2k)的確定性算法,表明了Maximum Cut問(wèn)題是固定參數(shù)可解的。
　　 本文進(jìn)一步研究

6、了基于保證值參數(shù)化MaxCut問(wèn)題的核和算法,并得到了相關(guān)改進(jìn)結(jié)果。對(duì)關(guān)于頂點(diǎn)的核提出了一個(gè)√8k的下界,將關(guān)于邊的核由16k2-18k+6減少至8k2+10k+2,并且在此基礎(chǔ)上將求解該問(wèn)題當(dāng)前最好算法的時(shí)間復(fù)雜度由O*(16k)改進(jìn)至O*(8.999k)。
　　 本文還進(jìn)一步研究了MultiCut問(wèn)題,并對(duì)它提出了一個(gè)新的參數(shù)化算法。在深入分析問(wèn)題結(jié)構(gòu)特點(diǎn)的基礎(chǔ)上,本文運(yùn)用集合劃分策略和相關(guān)問(wèn)題的最新研究結(jié)果對(duì)MultiCu