FPT-算法在CBVC問(wèn)題中的運(yùn)用.pdf

1、FPT-算法(Fixed-Parameter-TractableAlgorithms)被認(rèn)為是當(dāng)前比較流行的運(yùn)用于解決許多NP完全問(wèn)題的較為有效的算法，許多FPT-算法是通過(guò)兩個(gè)步驟來(lái)對(duì)問(wèn)題進(jìn)行求解：首先，把實(shí)例轉(zhuǎn)化為一個(gè)較小的等價(jià)體，具體來(lái)說(shuō)，其大小由只依賴(lài)于參數(shù)的一個(gè)函數(shù)所限制。這一步稱(chēng)為化簡(jiǎn)問(wèn)題核心。其次，通過(guò)用一些更小的參數(shù)解決一些導(dǎo)出子例，把簡(jiǎn)化了的問(wèn)題用遞歸的方式來(lái)解決。因?yàn)樵谶f歸調(diào)用中的那些參數(shù)更小，所以遞歸最終能完成(要

2、么找到一個(gè)解，要么了解到由于k≤0而沒(méi)有解存在)。這一步稱(chēng)為限定搜索樹(shù)。 頂點(diǎn)覆蓋問(wèn)題是一個(gè)公認(rèn)的NP完全問(wèn)題，對(duì)它的解決將具有十分廣闊的應(yīng)用前景，特別是對(duì)于受二分圖約束的頂點(diǎn)覆蓋(CBVC)問(wèn)題在超大規(guī)模集成電路芯片的修復(fù)上的運(yùn)用已相當(dāng)成熟。但隨著芯片集成度的提高，對(duì)頂點(diǎn)覆蓋的算法無(wú)論在精確度上還是運(yùn)行時(shí)間上都提出更高的要求。而把固定參數(shù)算法與受約束的二分圖頂點(diǎn)覆蓋問(wèn)題相結(jié)合起來(lái)的算法能適應(yīng)這種要求。 本文通過(guò)用把匹配

3、理論的經(jīng)典理論運(yùn)用到參數(shù)理論與二分圖頂點(diǎn)覆蓋問(wèn)題的結(jié)合中，得到時(shí)間復(fù)雜度只需要D(1.26k+nk)的優(yōu)良結(jié)果的算法的一個(gè)實(shí)例來(lái)證明參數(shù)理論在解決NP-完全問(wèn)題時(shí)的有效性，并得出一個(gè)結(jié)論：參數(shù)復(fù)雜性算法雖然好用，但也不是放之四海而皆準(zhǔn)的算法，只有把FPT-算法充分與具體實(shí)際問(wèn)題相結(jié)合才能產(chǎn)生出更為優(yōu)越的結(jié)果，這是立足于對(duì)具體問(wèn)題的深入理解和掌握的基礎(chǔ)上的，對(duì)具體問(wèn)題理解越透徹，得到的結(jié)果也會(huì)更優(yōu)異。此外，通過(guò)對(duì)這一實(shí)例的具體分析，也希望