算法設(shè)計與分析：NP完全問題

1第10章NP完全問題

210.1引言10.2P類10.3NP類10.4NP完全問題10.5co-NP類（略）10.6NPI類（略）10.7四種類之間的關(guān)系（略）31．引言在前面的各章中，我們對一些算法的設(shè)計和分析進行了討論，這些算法的運行時間可用低次多項式來表示（例二次）。在這一章，我們將注意力集中在這樣一類問題，這些問題至今沒有找到有效算法，而且今后也有可能證明得知：它們無有效算法。設(shè)П是任意問題，如果對問題存在一個算法，它的時間復(fù)雜性是O(nk)，其中n是輸入大小，k是非負(fù)整數(shù)，我們說問題П存在多項式時間算法?，F(xiàn)實世界的許多問題并不屬于這個范疇，因為求解這些問題需用指數(shù)（2n）或超指數(shù)（n!）來表示。4

本章將研究難解問題的一個子類，通常稱為NP完全問題（NPC問題）。這一類問題目前約有3000多個，其中還包括數(shù)百個著名問題。它們有一個共同特性，如果它們中的一個是多項式可解的話，那么所有其它問題也是多項式可解的。現(xiàn)存的求解這些問題算法的運行時間，對于中等大小的輸入也要用幾百或幾千年的時間。易求解問題： 存在多項式時間算法。難解問題： （到目前為止）不存在多項式時間算法。52．判定問題為了研究問題的復(fù)雜性，我們必須將問題抽象。為了簡化問題，我們只考慮一類簡單的問題，稱為“判定性問題”。也就是說提出一個問題，只需要回答Yes／No的問題。任何一般的最優(yōu)化問題都可以轉(zhuǎn)化為一系列判定性問題。例如求圖中從A到B的最短路徑，該問題可以轉(zhuǎn)化成如下形式： 從A到B是否有長度為1的最短路徑？ No

從A到B是否有長度為2的最短路徑？ No …………………？ No

從A到B是否有長度為k-1的最短路徑？ No

從A到B是否有長度為k的最短路徑？ Yes

如果問到了k的時候，回答了Yes，則停止發(fā)問。我們可以說：從A到B的最短路徑長度為k。63．確定性算法定義10.1（P176）設(shè)A是求解問題П的一個算法。如果在展示問題П的一個實例時，在整個執(zhí)行過程中每一步都只有一種選擇，則稱A是確定性算法。

所以對于同樣的輸入，實例一遍又一遍地執(zhí)行，它的輸出從不改變。在前面各章所討論的所有算法都是確定性的。例1：算法表達式的計算（5+3*8-9）

例2：選擇排序法問題：哈密頓回路給出一個無向圖G=(V,E)，它有哈密頓回路嗎？即在圖中是否存在一條恰好訪問每個頂點一次的回路?？梢杂酶F舉法來求解，一條回路一條回路檢查下去，最終便能得到結(jié)果。但是窮舉法的算法復(fù)雜性是指數(shù)級的，計算時間隨問題規(guī)模成指數(shù)型增長，很快就變得不可計算了，所以確定性算法對此類問題無效。74．P類定義10.2（P176）判定問題的P類由這樣的判定問題組成，它們的Yes／No解可以用確定性算法在多項式時間內(nèi)得到。例如在O(nk)內(nèi)得到，其中k是非負(fù)整數(shù)，n是輸入實例的大小。例1：給出一個有n個整數(shù)的表，它們是否按降序排列？答：只要檢查表中相鄰二個數(shù)即可，運行時間為O(n)。例2：給出二個整數(shù)集合，它們的交集是否為空？答：因集合中無重復(fù)元素，先將所有整數(shù)排序，然后檢查相鄰二數(shù)是否相等，顯然運行時間為O(nlog2n)。85．非確定性算法有些計算問題是確定性的，例如“加減乘除”，你只要按照公式推導(dǎo)，按部就班一步步進行，就可以得到結(jié)果。但是有些問題無法按部就班直接進行計算的，例如“找大質(zhì)數(shù)”的問題。已知目前最大質(zhì)數(shù)，那么下一個大質(zhì)數(shù)應(yīng)該是多少呢？有沒有一個公式可以一步步推算出來，顯然這樣的公式是沒有的。這種問題的答案，是無法直接計算得到的，只能通過“猜算”來得到結(jié)果，這也就是非確定性問題。這些問題通常有個算法，它不能直接告訴你答案是什么，但可以告訴你，某個可能的結(jié)果是正確的答案、還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，稱為非確定性算法。假如“猜算”可以在多項式時間內(nèi)得到，那么該問題稱作“多項式非確定性問題”。9非確定性算法定義（P177）對于輸入x，一個不確定算法由猜測和驗證二個階段組成。

⑴猜測階段在這個階段產(chǎn)生一個任意字符串y，它可能是對應(yīng)輸入實例x的一個解，也可能不是一個解，甚至不是解的合適形式，也可能在不確定算法的不同次運行中不同。在此階段，僅僅要求在多項式時間內(nèi)（O(ni)，n=|x|）產(chǎn)生串y。對于許多問題，這個階段可以在線性時間內(nèi)完成。

⑵驗證階段檢查產(chǎn)生串y是否是解的合適形式，若不是，則算法停下來回答No。若產(chǎn)生串y是解的合適形式，則繼續(xù)檢查y是否是問題實例x的解。若是，則算法停下來回答Yes；若不是，則算法停下來回答No。在此階段，也要求在多項式時間內(nèi)（O(nj)）完成。非確定性算法的運行時間是猜測階段和驗證階段所花費時間的和（O(nk)=O(ni)+O(nj)）。10實例：求大整數(shù)n的一個真因數(shù)（即1和大整數(shù)n本身以外的一個因數(shù)，并且該因數(shù)是素數(shù)）。這是一個至今未能找到有效算法的難解問題。對于難解問題，人們除了使用傳統(tǒng)型計算方法外，又想出了另一種類型的計算方法，該方法稱為非確定性計算。傳說從前有位年輕的國王，想在一天內(nèi)求出整數(shù)190334261410902619的一個真因素。他用2、3、5、7、11、13、……這些素數(shù)逐一去試，終于未能算出，于是他把這個問題交給了宰相。國王用的計算方法稱為“窮舉法”，是一種傳統(tǒng)的計算方法，窮舉法屬“確定性計算方法”。11

宰相猜想這個數(shù)可能是9位整數(shù)，于是宰相把全國成年百姓編成十個軍，每個軍有十個師，每個師有十個旅，每個旅有十個團，每個團有十個營，每個營有十個連，每個連有十個排，每個排有十個班，每個班有十個組，每個組有十個人，于是每個成年百姓都具有一個9位的番號。然后把題目發(fā)下去，讓每個成年百姓用自己的番號去除“190334261410902619”這個數(shù)，若除盡了就把番號報上去。于是很快就有二個人報上了結(jié)果，即“436273009”與“436273291”。經(jīng)國王驗證，這二個整數(shù)都是素數(shù)，并且這二整數(shù)的積就是題目所給的18位整數(shù)。12190334261410902619436273009 *436273291軍師旅團營連排組人軍師旅團營連排組人=這個故事說明算法分析中最基本問題：求大整數(shù)的真因數(shù)不能用多項式時間求解，但是驗證某數(shù)是否是大整數(shù)的真因數(shù)可以用多項式時間完成，所以求大整數(shù)的真因數(shù)要比驗證大整數(shù)的真因數(shù)要難得多。國王用得是確定性計算方法（窮舉法），所以計算很快變得無法進行下去；宰相用得是非確定性計算方法，首先猜想，然后驗證。136．定義10.3NP類（P177）判定問題的NP類由這樣的判定問題組成，對于它們存在多項式時間內(nèi)運行的不確定性算法。7．P類和NP類的區(qū)別（P177）P是一個判定問題類，這些問題可以用一個確定性算法在多項式時間內(nèi)判定或解出。NP是一個判定問題類，這些問題可以用一個確定性算法在多項式時間內(nèi)檢查或驗證它們的解。8．NP完全問題如果一個NP問題的所有可能答案，都可以在多項式時間內(nèi)進行正確與否驗證的話，那么該問題稱為“完全多項式非確定性問題”，簡稱NP完全問題（或NPC問題）。NP完全問題是NP類的一個子類。

14

前頁所述是對“NP完全問題”的一個比較通俗的解釋，它避免了很多抽象概念，對于初學(xué)者來說較易理解，而NP完全問題在算法分析中有嚴(yán)格定義。若要證明一個問題∏是NP完全的，僅需證明以下二個條件成立即可。問題∏是NP問題；已知問題∏'是一個NP完全問題，問題∏在多項式時間內(nèi)可歸約到問題∏'?！癗P完全問題”可以用窮舉法來求解，一個個檢驗下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度是指數(shù)級的，計算的時間隨問題的規(guī)模成指數(shù)型增長，很快便變得不可計算了。15哈密頓回路問題（重述）：給出一個無向圖G=(V,E)，它有哈密頓回路嗎？即在圖中存在一條恰好訪問每個頂點一次的回路。如果給出了哈密頓回路一個答案，我們可以在多項式時間內(nèi)判斷這個答案是否正確。即給出一個任意的回路，我們很容易判斷它是否是哈密頓回路，只要看是不是所有的結(jié)點都在回路中，并且出現(xiàn)一次就可以了。哈密頓回路問題就是一個NP完全問題。我們一般認(rèn)為NP完全問題是難解的問題，因為它們目前不存在一個多項式時間的算法，甚至將來也很難找到，即P≠NP。實際上對于某些頂點數(shù)不到100的無向圖，利用現(xiàn)有最好的計算機，也需要比較荒唐的時間（例如幾百年），才能確定其是否存在一條哈密頓回路。16cook在1971年找到了第一個NP完全問題，即可滿足性問題（邏輯運算問題），此后人們又陸續(xù)發(fā)現(xiàn)很多NP完全問題，例如類似哈密頓回路問題（旅行商問題）、圖3著色問題、多處理機調(diào)度問題等等。 人們發(fā)現(xiàn)，所有的NP完全問題都可以在多項式時間內(nèi)轉(zhuǎn)換到可滿足性問題。這樣如果它們中的一個存在多項式時間確定性算法的話，那么NP完全問題中的所有問題，都可用多項式時間確定性算法來求解。 人們于是就猜想，既然NP完全問題的所有可能答案，都可以在多項式時間內(nèi)驗證，對于此類問題是否存在一個確定性算法，可以在多項式時間內(nèi)直接算出或搜尋出正確的答案呢？這就是著名的NP=P？的猜想。這是21世紀(jì)計算機科學(xué)家向數(shù)學(xué)家提出的世界難題。17

解決NP=P？的猜想無非兩種可能。一種是找到一個這樣的算法，只要針對某個特定