NP完全性和近似算法

在理解NP完全性之前，筆者想引入關于科學與偽科學的定義。凡可接受實踐檢驗、可被證實和被否正的為科學，相反之為非科學，而偽科學是非科學之子集，與科學相對立，認定非科學為科學的即是偽科學。三者關系可簡化為：科學相反于非科學、對立于非科學子集偽科學。集合的運算關系見下面，科學定義為S、非科學定義為NS、偽科學定義為FS。

算法是用來解決問題的，一個問題能否在多項式時間內完成是衡量問題復雜度和算法有效性的標準。多項式時間就是指時間復雜度是個多項式。對于解決問題的算法，在其輸入規模為下，其最壞運行時間為，其中k為常數，則問題在多項式時間內可解。顯然，現實中很多問題是暫時無法找到多項式時間內的算法來解決，于是，以是否存在多項式時間內的算法來界定問題復雜度，存在則可解，反之則無解。NP集中在多項式復雜度的非確定性問題的研究上，屬于科學，可被證實和被否正。

再說明下判定問題和最優化問題。判定問題是指尋求有窮步驟內確定是否具有某一特定的性質的一種能行方法或程序或算法，該類問題的答案可用“是否”來回答；最優化問題是在滿足一定的約束條件和特定參數值輸入下取得最佳值的可行解。對最優化問題的值設定一個界，可轉化為相關判定問題。

特定狀態輸入下，如輸出唯一確定，則為確定性算法，如輸出多項可選，則為非確定性算法。非確定性算法將問題分解成猜測和驗證兩個階段，算法的猜測階段是非確定性的，算法的驗證階段是確定性的，它驗證猜測階段給出解的正確性。

P類問題（polynomialproblem）：多項式時間內可解的判定問題。

NP類問題（nondeterministic polynomial）：非確定性多項式時間可解的判定問題。

NPC類問題（NPcomplete）：屬于NP中的問題，其復雜性與整個類的復雜性一致，其中一個存在多項式時間的算法，該類所有問題均可在多項式時間可解的。

通俗地說，P類問題就是多項時間內一定可解，可以很快解決的問題組成；NP類問題就是多項式時間內非確定性可解，在約束性的輸入下，可以驗證出多項式時間內的解，可以很快驗證其解的問題組成；NPC類問題則是無法找尋一個多項式時間內的解的NP問題集合。顯然，P和NPC都是NP的子集，且P和NPC無交集，如下面集合關系。

NPC問題的定性更多傾向于解決問題的難度或算法復雜度無法在多項式時間內量化，于是這類問題的集合在邏輯高度上便形成一即一切、一切即一的思維，一個問題有解，所有問題便有解。對于NP問題的非確定性算法，存在很多可能性的猜測，但結果正確與否可驗證；可在多項式時間內驗證一個解是否正確的問題即為NP問題，易驗證問題類。

從NP類的問題中分出復雜性最高的一個子類，即NP完全類，其理論意義在于證明P=NP，只要二者有交集，就證明了NP類中的所有問題都是P類的，這對于解決NPC問題有現實意義。在算法設計和分析過程中,如證明某問題是NP完全的,即意味著面臨hard問題；因此對于NP完全問題，尋找最佳近似算法，或者界定具體要求尋找多項式時間算法。

實際上，P、NP、NPC三者的集合關系隨著各類難題的解決以及新出現的難題，證明P=NP一直未能有效成立。有解、未確定性有解、無解，就是問題的分類，有解的是P，如果能夠證明無解的NPC有解，那未確定性有解的NP就是確定性有解。何謂未確定有解，無法證明有解，但如果提出一個解可以很快驗證是否有效，其中找不到任何一個解的都歸類到NPC，而NPC中只要有一個問題存在解，那所有該類問題都有解，這就是歸約性的定義。

設A2是判定問題L2的多項式時間算法， F是計算規約函數f的多項式時間規約算法。

判定問題L1的多項式時間算法A1。x屬于L1問題，將x通過F歸約到f(x)，f(x)屬于L2問題，如果f(x)能夠通過多項式時間內的算法A2得解，則判定問題x可通過多項式時間算法A1得解。

反過來，歸約性也用來證明一個問題在一個多項式時間因子內與其他問題一樣難。通過歸約性得出定理：如果任何NPC的問題是多項式時間內可求解的，則P=NP。等價地，如果NP中的任何問題不是多項式時間可求解的，則所有NPC問題都不是多項式內可求解的。目前理論研究的進展，傾向P不等于NP，三者的集合關系如下圖。

既然NPC問題的存在，使P=NP不成立，那么研究NPC問題的解決便成為復雜類問題的關鍵。一般解決策略有：只對問題的特殊實例求解、用動態規劃法或分支限界法求解、用概率算法求解、只求近似解、用啟發式方法求解。關于近似算法定義如下：

如果對規模為n的任何輸入，由近似算法產生的解的代價C與最優解的代價C*只差一個因子ρ(n)（近似比，approximation ratio），則該算法為ρ(n)近似算法。

若對問題的輸入規模n，有一函數ε(n)使得，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間顯然有如下關系：。

對理解NPC和近似算法還需要就具體問題的算法求解進行研究，如旅行商問題、集合覆蓋問題等。考驗邏輯的圖靈停機問題卻想理解下。

圖靈停機問題的描述：不存在一個程序（或算法），它能夠計算任何程序在給定輸入上是否會結束（停機）。用反證法來證明：

1）假設存在萬能程序God_algo，可以判定任何一段程序及其給定的輸入是否會結束。

boolGod_algo(char* program, char* input){

??? if(<program> halts on <input>)

??????? return true;

??? return false;

}

顯然這個程序可以知道任何程序能否結束的結果，如果可以結束就返回true，不能結束就返回false。

2）現在我們增加一個程序Satan_algo來調用萬能程序God_algo：

boolSatan_algo(char* program){

if(God_algo(program, input) ) {

?????? while(1);??????? // loop forever!

?????? return false;?? // can never get here!

}else returntrue;

}

該程序根據God_algo返回結果輸出。假設輸入程序A，God_algo判定A程序及其給定輸入input可停機，則進入循環無法退出，如果不停機則返回true。

3）Satan_algo調用自身：

Satan_algo（Satan_algo）執行結果顯然是左右矛盾。

假設Satan_algo能夠停機，God_algo返回ture，進入while循環，無法停機；

假設Satan_algo不能停機，God_algo返回false，返回true，可以停機。

4）結論：

Satan_algo能夠停機=>Satan_algo(Satan_algo)它不能停機

Satan_algo不能停機=>Satan_algo(Satan_algo)它能夠停機

推導出不存在這樣的一個萬能程序，可判定任何程序在給定輸入下是否能停機。

科學的偉大就在于不斷證明和反證明，科學家的偉大在于在不斷的探索中肯定和否定，而思考和邏輯顯然在這中間扮演著無窮魅力的角色。沒有思考不存在邏輯，而沒有邏輯的思考不存在思考的意義，沉浸在理論科學的汪洋大海中，忘記技術工程的瑣細，是一種享受，而尋找理論的應用卻是一種自我升華和證明的過程。現代信息科學大廈的基礎無疑是數學，但計算機科學也豐富了數學的理論，無法忘記歸納、推理在程序中所體現的閃光點，圖靈機開創的時代，至今令人心驚動搖，如今智能和量子時代的來臨，圖靈理論基礎還是適用。要繼續進步，也許只有理論再次創新，出現二次圖靈機理論，每次理論的創新都有著漫長理論應用的經驗探索，而后量變出現質變，我相信這個理論革命不遠了。超越圖靈機、突破馮諾依曼體系，是賦予現如今計算機科學理論研究者的使命，而作為前沿技術工程者，無疑是期待著能參與，可惜理論所需要的數學基礎非專攻不能。

總結

以上是生活随笔為你收集整理的算法导论之NP完全性和近似算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。