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

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

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

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