FPT-算法在CBVC問題中的運用.pdf

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

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

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