1、算法設(shè)計(jì)與分析,張怡婷 Email:,第10章 NP完全問(wèn)題,學(xué)習(xí)要點(diǎn)： 確定算法和不確定算法 判定問(wèn)題和最優(yōu)化問(wèn)題的關(guān)系 可滿(mǎn)足性問(wèn)題 P類(lèi)問(wèn)題和NP類(lèi)問(wèn)題 NP難度(NP hard)和NP完全(NP complete)問(wèn)題 Cook定理 典型的NP完全（或NP難度）問(wèn)題的證明,章節(jié)內(nèi)容: 10.1 基本概念 10.2.1 Cook定理 10.3 一些典型的NP完全問(wèn)題,10.1 基本概念,將能在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題視為易處理問(wèn)題(tractable problem)。 至今尚未找到多項(xiàng)式時(shí)間算法求解的問(wèn)題視為難處理問(wèn)題(intractable problem)。 NP完全問(wèn)題或NP難度(

2、NP hard)問(wèn)題 如：指數(shù)時(shí)間算法 無(wú)論消耗多少計(jì)算機(jī)時(shí)間和空間也不能求解的稱(chēng)為不可判定(undecidable)的。 不存在任何算法求解,如果任意一個(gè)NP難度問(wèn)題存在一個(gè)多項(xiàng)式時(shí)間算法，那么所有NP完全問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)求解。 一個(gè)NP完全問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)所有其他的NP完全問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)求解。,10.1.1 不確定算法和不確定機(jī),不確定算法的抽象計(jì)算模型： 算法在抽象機(jī)上運(yùn)行與計(jì)算機(jī)系統(tǒng)的性能無(wú)關(guān)； 算法的執(zhí)行表現(xiàn)為執(zhí)行一個(gè)基本運(yùn)算序列； 基本運(yùn)算的執(zhí)行時(shí)間是有限常量；,Choice(S)：任意選擇集合S的一個(gè)元素。 Failure()：發(fā)出不成功完成

3、信號(hào)后算法終止。 Success()：發(fā)出成功完成信號(hào)后算法終止。,例10-1 在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中，則確定使aj=x的下標(biāo)j，否則輸出-1。,不確定搜索算法： void Search(int a,T x) int j=Choice(0,n-1);/從0,1,.,n-1中任意選取一個(gè)值 if(aj=x) coutj; Success();/不確定算法成功終止 cout-1; Failure();/不確定算法失敗終止 ,若算法執(zhí)行中需作出一系列的Choice函數(shù)選擇，當(dāng)且僅當(dāng)Choice的任何一組選擇都不會(huì)導(dǎo)致成功信號(hào)時(shí)，算法在O(1)時(shí)間不成功終止。,如果一個(gè)判定問(wèn)

4、題實(shí)例的解為真，Choice函數(shù)每一次總能在O(1)時(shí)間內(nèi)做出導(dǎo)致成功的正確選擇。,包含不確定選擇語(yǔ)句，并能按上述方式執(zhí)行一個(gè)算法的機(jī)器稱(chēng)為不確定機(jī)（non deterministic machine)。,在不確定機(jī)上執(zhí)行的算法稱(chēng)為不確定算法(non deterministic algorithm)。,不確定機(jī)的執(zhí)行方式，可理解為不受限制的并行計(jì)算： 不確定機(jī)執(zhí)行不確定算法時(shí)，每當(dāng)Choice函數(shù)進(jìn)行選擇時(shí)，就好像復(fù)制了多個(gè)程序副本，每一種可能的選擇產(chǎn)生一個(gè)副本，所有副本同時(shí)執(zhí)行。一旦一個(gè)副本成功完成，將立即終止所有其他副本的計(jì)算。 如果存在至少一種成功完成的選擇，一臺(tái)不確定機(jī)總能做出最佳選擇

5、，以最短的程序步數(shù)完成計(jì)算，并成功終止。 不確定機(jī)能及時(shí)判斷算法的某次執(zhí)行不存在任何導(dǎo)致成功完成的選擇，并使算法在一個(gè)單位時(shí)間內(nèi)輸出“不成功”信息后終止。,顯然，這種機(jī)器是虛構(gòu)的，是一種概念性計(jì)算模型！,不確定搜索算法： void Search(int a,T x) int j=Choice(0,n-1); if(aj=x) coutj; Success(); cout-1; Failure(); ,定義10-1 （不確定算法時(shí)間復(fù)雜度） 一個(gè)不確定算法所需的時(shí)間是指對(duì)任意一個(gè)輸入，當(dāng)存在一個(gè)選擇序列導(dǎo)致成功完成時(shí)，達(dá)到成功完成所需的最少程序步。在不可能成功完成的情況下，所需時(shí)間總是O(1)。

6、,例10-2 將n個(gè)元素的序列排成有序序列。,不確定排序算法： void NSort(int a,int n) int bmSize,i,j; for (i=0;ibi+1) Failure();/若存在兩元素逆序，則失敗 Success();/Choice函數(shù)的n次正確選擇，算法成功 ,判定問(wèn)題和最優(yōu)化問(wèn)題,一個(gè)只要求產(chǎn)生“0”或“1”作為輸出的問(wèn)題稱(chēng)為判定問(wèn)題（decision problem）。,許多最優(yōu)化問(wèn)題都可以得到與其相對(duì)應(yīng)的判定問(wèn)題，且兩者往往存在計(jì)算上的相關(guān)性：,一個(gè)判定問(wèn)題能夠在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)它相應(yīng)的最優(yōu)化問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解。,如果判定問(wèn)題不能在多項(xiàng)式時(shí)間

7、內(nèi)求解，那么它相應(yīng)的最優(yōu)化問(wèn)題也不能在多項(xiàng)式時(shí)間內(nèi)求解。,例10-3 最大集團(tuán)及其判定問(wèn)題 無(wú)向圖G=（V,E）的一個(gè)完全子圖稱(chēng)為該圖的一個(gè)集團(tuán)，集團(tuán)的規(guī)模用集團(tuán)的頂點(diǎn)數(shù)衡量。,最大集團(tuán)問(wèn)題：確定圖G的最大集團(tuán)規(guī)模的問(wèn)題。,最大集團(tuán)判定問(wèn)題：判定圖G是否存在一個(gè)規(guī)模至少為k的集團(tuán)。（k為給定正整數(shù)）,若最大集團(tuán)問(wèn)題能在多項(xiàng)式時(shí)間O(g(n)內(nèi)求解。 當(dāng)且僅當(dāng) 對(duì)應(yīng)的判定問(wèn)題能在多項(xiàng)式時(shí)間O(f(n)內(nèi)求解。,一方面：只需以k=1,2,.,n，最多n次調(diào)用最大集團(tuán)判定算法，便可求得最大集團(tuán)的大小，因此O(g(n)=O(nf(n)； 另一方面：可使用求解最大集團(tuán)問(wèn)題的算法，求得最大集團(tuán)的規(guī)模為k。

8、若kk，則最大集團(tuán)判定問(wèn)題的解為“1”，否則為“0”。顯然有O(f(n)=O(g(n)。,許多抽象問(wèn)題并不是判定問(wèn)題，而是最優(yōu)化問(wèn)題，必須最大化或最小化某個(gè)量。然而，如我們看到的，將最優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)并不更難的判定問(wèn)題通常是比較簡(jiǎn)單的。,10.1.2 可滿(mǎn)足性問(wèn)題,數(shù)理邏輯中，一個(gè)變量 和它的非 都稱(chēng)為文字。 命題公式是由文字及邏輯運(yùn)算符“與()”和“或()”構(gòu)成的表達(dá)式。,如果一個(gè)公式具有邏輯與形式：C1C2.Ck，其中每個(gè)子句Ci都是邏輯或形式li1li2.lip，每個(gè)lij是文字，則將這種形式的公式稱(chēng)為合取范式(conjunctive normal form，CNF)。,如果一個(gè)公式具

9、有邏輯或形式：C1C2.Ck，其中每個(gè)子句Ci都是邏輯與形式li1li2 . liq，每個(gè)lij是文字，則將這種形式的公式稱(chēng)為析取范式(disjunctive normal form，DNF)。,例10-4 可滿(mǎn)足性問(wèn)題（satisfiability problem) 是一個(gè)判定問(wèn)題，確定對(duì)于一個(gè)給定的命題公式，是否存在布爾變量的一種賦值（也稱(chēng)真值指派）使該公式為真。,例如： 公式 是可滿(mǎn)足的。只需令x1=1，x2=0，x3=0。,公式 是不可滿(mǎn)足的。,程序10-4 可滿(mǎn)足性問(wèn)題的不確定算法,void Eval(CNF E, int n) int xmSize; for (int i=1;i=

10、n;i+) /O(n) xi=Choice(0,1);/為變量xi賦0或1值 if (E(x,n) Success();/O(e)，計(jì)算公式E(x,n)的值 /若為真，成功終止 else Failure(); ,因?yàn)椋簩?duì)n個(gè)布爾變量賦值需要O(n)時(shí)間，計(jì)算公式E(x,n)的時(shí)間為O(e)，e是公式長(zhǎng)度。 所以，可滿(mǎn)足性問(wèn)題的不確定算法時(shí)間為O(n+e)。,10.1.3 P類(lèi)和NP類(lèi)問(wèn)題,P類(lèi)問(wèn)題：可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題。 NP類(lèi)問(wèn)題：可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題。（多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證問(wèn)題的解。）,確定算法是不確定算法當(dāng)Choice函數(shù)只有一種選擇時(shí)的特例，所以

11、有： 但至今無(wú)法斷定：是否P=NP或者PNP。,定義10-3 多項(xiàng)式約化 令Q1和Q2是兩個(gè)問(wèn)題，如果存在一個(gè)確定算法A求解Q1，而算法A以多項(xiàng)式時(shí)間調(diào)用另一個(gè)求解Q2的確定算法B。若不計(jì)B的工作量，算法A是多項(xiàng)式時(shí)間的，則稱(chēng)Q1約化(reduced to)為Q2，記作Q1Q2。,約化存在以下性質(zhì)：,性質(zhì)10-1 若Q1P，Q2Q1，則有Q2 P。,性質(zhì)10-2 （傳遞性） 若Q1Q2，Q2Q3，則Q1Q3。,10.1.4 NP難度和NP完全問(wèn)題,性質(zhì)10-4 NP難度（NP hard） 對(duì)任意問(wèn)題Q1NP都有Q1Q，則稱(chēng)問(wèn)題Q是NP難度（NP hard）的。,只要對(duì)任何一個(gè)NP難度問(wèn)題Q找到

12、了它的多項(xiàng)式時(shí)間算法，那么，可以斷定所有NP類(lèi)問(wèn)題都能在多項(xiàng)式時(shí)間內(nèi)求解，因?yàn)樗蠳P類(lèi)問(wèn)題都能約化到問(wèn)題Q。 （然而目前尚無(wú)任何一個(gè)NP難度問(wèn)題具有多項(xiàng)式時(shí)間算法。）,性質(zhì)10-5 NP完全（NP complete） 對(duì)于問(wèn)題QNP且Q是NP難度的，則稱(chēng)Q是NP完全（NP complete，NPC）的。,所有NP完全問(wèn)題都是NP難度的，反之不然，NP難度問(wèn)題不一定是NP完全的（若不是NP類(lèi)問(wèn)題，則不是NP完全的）。,現(xiàn)實(shí)意義： 若一個(gè)問(wèn)題被證明是NP難度（NP hard）的，則很難找到一個(gè)多項(xiàng)式時(shí)間的有效算法。若問(wèn)題的實(shí)例規(guī)模較大，則應(yīng)選擇采用啟發(fā)式算法、隨機(jī)算法或近似算法等其他算法策略求解

13、。,如何確定某個(gè)問(wèn)題是否是NP難度的？,證明某個(gè)問(wèn)題Q是NP難度（NP hard）的證明策略： (1)選擇一個(gè)已經(jīng)證明是NP難度問(wèn)題Q1; (2)求證Q1Q。 則問(wèn)題Q是NP難度的。,由于Q1是NP難度的，因此所有NP類(lèi)問(wèn)題都可約化到Q1。 根據(jù)約化的傳遞性，任何NP類(lèi)問(wèn)題都可約化到Q。 所以，Q是NP難度的。,在此基礎(chǔ)上，若進(jìn)一步表明Q本身是NP類(lèi)的，則問(wèn)題Q是NP完全的。,10.2 Cook定理和證明,10.2.1 Cook定理,斯蒂芬?guī)炜耍⊿teven Cook）于1971年證明了第一個(gè)NP完全問(wèn)題，稱(chēng)為Cook定理，表明可滿(mǎn)足性問(wèn)題是NP完全的。 至今至少已有300多個(gè)問(wèn)題被證明是NP

14、難度問(wèn)題，但尚未證明其中任何一個(gè)是屬于P的。,10.3 一些典型的NP完全問(wèn)題,證明(一個(gè)猜想可能是NP難度的)問(wèn)題Q確實(shí)是NP難度(或NP完全)問(wèn)題的具體步驟： 利用多項(xiàng)式約化（歸約）的方法 （1）選擇一個(gè)已知其具有NP難度的問(wèn)題Q1； （2）證明能夠從Q1的一個(gè)實(shí)例I1，在多項(xiàng)式時(shí)間內(nèi)構(gòu)造Q的一個(gè)實(shí)例I； （3）證明能夠在多項(xiàng)式時(shí)間內(nèi)從I的解確定I1的解。 （4）從（2）和（3）可知，Q1Q； （5）從（1）和（4）及約化的傳遞性得出所有NP類(lèi)問(wèn)題均可約化到Q，所以Q是NP難度的。 （6）*如果Q是NP類(lèi)問(wèn)題，則Q是NP完全的。,10.3.1 最大集團(tuán),最大集團(tuán)判定問(wèn)題是NP類(lèi)問(wèn)題。,“集

15、團(tuán)”是無(wú)向圖中的完全子圖，任意一對(duì)頂點(diǎn)間有邊相連。,P231 程序10-3是求解該問(wèn)題的多項(xiàng)式時(shí)間不確定算法。 或： 對(duì)給定的圖G=(V,E)，檢查頂點(diǎn)集V V中每一對(duì)頂點(diǎn)u,v間是否存在邊(u,v) E，即可在多項(xiàng)式時(shí)間內(nèi)完成對(duì)V是否是集團(tuán)的檢查。,最大集團(tuán)判定問(wèn)題是NP完全的。,下面證明：,證明思路： 證明CNF可滿(mǎn)足性最大集團(tuán)判定問(wèn)題，所以最大集團(tuán)判定問(wèn)題是NP難度的。 又因?yàn)樽畲蠹瘓F(tuán)判定問(wèn)題是NP類(lèi)問(wèn)題（前面已證） 所以最大集團(tuán)判定問(wèn)題是NP完全的。,定理10-3 CNF可滿(mǎn)足性最大集團(tuán)判定問(wèn)題,證明： 1、在多項(xiàng)式時(shí)間內(nèi)，以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖G； 2、

16、證明F是可滿(mǎn)足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。,定理10-3 CNF可滿(mǎn)足性最大集團(tuán)判定問(wèn)題,證明： 1、在多項(xiàng)式時(shí)間內(nèi)，以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖G； 令F=C1C2 . Ck是一個(gè)具有k個(gè)子句的CNF形式的布爾公式。 由公式F構(gòu)造無(wú)向圖G的方法為： V=|是子句Ci的一個(gè)文字 E=(,)| ij 且 ,和處于 不同的分句中,和相應(yīng)的文字是一致的,如： 則G就是下圖：,定理10-3 CNF可滿(mǎn)足性最大集團(tuán)判定問(wèn)題,證明： 2、證明F是可滿(mǎn)足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。 （一方面，如果F可滿(mǎn)足， 那么圖G中必定存在規(guī)模為k的集團(tuán)。） 若F是可滿(mǎn)足的

17、，則必定存在布爾變量的一個(gè)賦值，使F的每個(gè)子句Ci中至少有一個(gè)文字為真。若i是子句Ci中為真的文字，則S=,.,是圖G中相應(yīng)頂點(diǎn)集合。根據(jù)圖的構(gòu)造方法，集合S中任意一對(duì)頂點(diǎn)和，由于i和j都為真且ij，因此它們之間應(yīng)該有邊相連，從而形成完全圖。S就是圖G的規(guī)模為k的集團(tuán)。,定理10-3 CNF可滿(mǎn)足性最大集團(tuán)判定問(wèn)題,證明： 2、證明F是可滿(mǎn)足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。 （另一方面，若圖G有一個(gè)規(guī)模至少為k的集團(tuán)， 則必定存在一種布爾變量賦值，使命題公式F為真，即F是可滿(mǎn)足的。） 若圖G中存在一個(gè)規(guī)模至少為k的集團(tuán)，S=,.,是集團(tuán)的頂點(diǎn)集合，則必有i和j值相同且ij（否則頂點(diǎn)和之間沒(méi)有邊）。 于是，對(duì)S中所有的文字賦真值，對(duì)不屬于S的變量取任意值，則使得F的每個(gè)子句Ci中至少有一個(gè)文字為真，從而F為真。,雖然當(dāng)前只是將CNF公式規(guī)約成了帶某種特定結(jié)構(gòu)的集團(tuán)實(shí)例，僅證明了在這種受限的情況下，最大集團(tuán)判定問(wèn)題是NP難度（NP完全）的。但是，這一證明足以證明在一般的圖中，最大集團(tuán)判定問(wèn)題也是NP難度的。 因?yàn)椋喝绻覀冇幸粋€(gè)多項(xiàng)式時(shí)間的算法，它能在一