《算法設計與分析》第10章.ppt

第10章NP完全問題,10.1基本概念10.2Cook定理和證明10.3一些典型的NP完全問題,10.1基本概念,將能在多項式時間求解的問題看作易處理問題(tractableproblem)，而將至今尚未找到多項式時間算法求解的問題視為難處理問題(intractableproblem)。,10.1.1不確定算法和不確定機,為便于研究，先假定一種運行不確定算法的抽象計算模型，該抽象機除了包含第2.1.3節(jié)的抽象機模型的基本運算外，最根本的區(qū)別在于它新增了下面一個新函數(shù)和兩個新語句：（1）Choice(S)：任意選擇集合S的一個元素；（2）Failure：發(fā)出不成功完成信號后算法終止；（3）Success：發(fā)出成功完成信號后算法終止。,例101在n個元素的數(shù)組a中查找給定元素x，如果x在其中，則確定使aj=x的下標j，否則輸出-1?！境绦?01】不確定搜索算法voidSearch(inta,Tx)intj=Choice(0,n-1);if(aj=x)cout<<j;Success();cout<<-1;Failure();,包含Choice函數(shù)的算法能按如下既定方式執(zhí)行：當算法執(zhí)行中需作出一系列的Choice函數(shù)選擇時，當且僅當對于Choice的任何一組選擇都不會導致成功信號時，此算法在O(1)時間不成功終止；否則，只要存在一組選擇能夠導致成功時，算法總能采取該組選擇使得算法成功終止。包含不確定選擇語句，并能按上述方式執(zhí)行一個算法的機器稱為不確定機（nondeterministicmachine）。在不確定機上執(zhí)行的算法稱為不確定算法（nondeterministicalgorithm）。,例10-2將n個元素的序列排成有序序列?！境绦?0-2】不確定排序算法voidNSort(inta,intn)intbmSize,i,j;for(i=0;i<n;i+)bi=0;for(i=0;i<n;i+)j=Choice(0,n-1);if(bj)Failure();bj=ai;,for(i=0;ibi+1)Failure();for(i=0;i<n;i+)cout<<bi<<cout<<endl;Success();,定義10-1（不確定算法時間復雜度）一個不確定算法所需的時間是指對任意一個輸入，當存在一個選擇序列導致成功完成時，達到成功完成所需的最少程序步。在不可能成功完成的情況下，所需時間總是O(1)。,例10-3（最大集團及其判定問題）無向圖G=(V,E)的一個完全子圖稱為該圖的一個集團（clique）。集團的規(guī)模用集團的頂點數(shù)衡量。最大集團問題是確定圖G的最大集團規(guī)模的問題。最大集團判定問題（G,k）是對給定正整數(shù)k，判定圖G是否存在一個規(guī)模至少為k的集團。,【程序10-3】最大集團判定問題不確定算法voidClique（intgmSize,intn,intk）S=;for(inti=0;i<k;i+)intt=Choice(0,n-1);if(tS)Failure();S=St;for(對所有(i,j)，iS，jS且ij)if(i,j)E)Failure();Success();,10.1.2可滿足性問題,例10-4可滿足性問題（satisfiabilityproblem）是一個判定問題，它確定對于一個給定的命題公式，是否存在布爾變量的一種賦值（也稱真值指派）使該公式為真。CNF可滿足性是指判定一個CNF公式的可滿足性。,【程序10-4】可滿足性問題的不確定算法voidEval(CNFE,intn)intxmSize;for(inti=1;i<=n;i+)xi=Choice(0,1);if(E(x,n)Success();elseFailure();,10.1.3P類和NP類問題,定義10-2（P類和NP類）P是所有可在多項式時間內用確定算法求解的判定問題的集合。NP是所有可在多項式時間內用不確定算法求解的判定問題的集合。定義10-3（多項式約化）令Q1和Q2是兩個問題，如果存在一個確定算法A求解Q1，而算法A以多項式時間調用另一個求解Q2的確定算法B。若不計B的工作量，算法A是多項式時間的，則稱Q1約化（reducedto）為Q2，記做Q1Q2。,性質10-1若Q1P，Q2Q1，則有Q2P。性質10-2若Q1Q2，Q2Q3，則Q1Q3。,10.1.4NP難度和NP完全問題,定義10-4（NP難度）對于問題Q以及任意問題Q1NP，都有Q1Q，則稱Q是NP難度（NPhard）的。定義10-5（NP完全）對于問題QNP，Q是NP難度的，則稱Q是NP完全（NPcomplete）的。,如何確定某個問題Q是否是NP難度的？一般的證明策略由以下兩步組成：（1）選擇一個已經證明是NP難度問題Q1；（2）求證Q1Q。由于Q1是NP難度的，因此所有NP類問題都可約化到Q1，根據約化的傳遞性，任何NP類問題都可約化到Q，所以Q是NP難度的。如果進一步表明Q本身是NP類的，則問題Q是NP完全的。,10.2Cook定理和證明,10.2.1Cook定理,斯蒂芬?guī)炜耍⊿tevenCook）于1971年證明了第一個NP完全問題，稱為Cook定理。Cook定理表明可滿足性問題是NP完全的。CNF可滿足性問題也被證明是NP完全的。自從Cook證明了可滿足性問題是NP完全的之后，迄今為止至少有300多個問題被證明是NP難度問題，但尚未證明其中任何一個是屬于P的。定理10-1（Cook定理）可滿足性問題在P中，當且僅當P=NP。定理10-2CNF可滿足性問題是NP完全的。,10.3一些典型的NP完全問題,證明一個問題Q是NP難度（或NP完全）問題的具體步驟如下：（1）選擇一個已知其具有NP難度的問題Q1；（2）證明能夠從Q1的一個實例I1，在多項式時間內構造Q的一個實例I；（3）證明能夠在多項式時間內從I的解確定I1的解。（4）從（2）和（3）可知，Q1Q；（5）由（1）和（4）及約化的傳遞性得出所有NP類問題均可約化到Q，所以Q是NP難度的；（6）如果Q是NP類問題，則Q是NP完全的。,10.3.1最大集團,定理10-3CNF可滿足性最大集團判定問題。證明分兩步證明這一定理：首先尋找一種方法，它能在多項式時間內，從任意給定的CNF公式F構造一個無向圖G=(V,E)；然后證明，F(xiàn)是可滿足的，當且僅當G有一個規(guī)模至少為k的集團。,第一步：以任意給定的CNF公式F為輸入，構造一個相應的無向圖G，并且這種構造能夠在多項式時間內完成。令是一個CNF形式的命題公式，xi，1in，是F中的變量。由F生成一個無向圖G=(V,E)的方法為：V=|是子句Ci的一個文字，E=(,)|ij且。,第二步：如果能夠證明F可滿足，當且僅當G有一個規(guī)模至少為k的集團，那么，便證明了CNF可滿足性問題可以約化到最大集團判定問題。分兩方面證明此結論:一方面，若F是可滿足的，則必定存在對n個布爾變量的一種賦值，使得每個子句Ci中至少有一個文字為真。另一方面，若G有一個規(guī)模至少為k的集團G（S，E），設S=,是集團的頂點集合，則必有i，ij，若不然，則頂點和之間沒有邊，S不是集團。,例10-5設有命題公式F，,圖G(V.E)有大小為2的集團，F(xiàn)是可滿足的（可令x1true，x2false）,10.3.2頂點覆蓋,例106（頂點覆蓋判定問題）對于無向圖G(V,E)，集合SV，如果E中所有邊都至少有一個頂點在S中，則稱S是圖G的一個頂點覆蓋。覆蓋的規(guī)模是S中頂點的數(shù)目|S|。頂點覆蓋（vertexcover）問題是指求圖G的最小規(guī)模的頂點覆蓋，而頂點覆蓋判定問題是確定圖G是否存在規(guī)模至多為k的頂點覆蓋。,對于圖中所示的無向圖G，S1=1，3和S2=0，2，4分別是圖G的頂點覆蓋，S1是最小覆蓋，其規(guī)模為2。,定理104最大集團判定問題頂點覆蓋判定問題。證明：分兩步證明這一結論。第一步：以最大集團判定問題的任一實例(G，k)，G=(V，E)，k為正整數(shù)，來構造一個頂點覆蓋判定問題的實例(G，n-k)，G=(V，)，n=|V|，=(u,v)|uV,vV且（u,v）E。,第二步：分兩方面證明“圖G有一個規(guī)模至少為k的集團，當且僅當圖G有一個規(guī)模至多為nk的結點覆蓋?！币环矫?，先證明：若圖G有一個規(guī)模至少為k的集團S，則圖G有一個規(guī)模至多為nk的結點覆蓋S，SVS。反證法：若G不能被S中的頂點所覆蓋，則必定存在邊(u,v)，頂點u和v均不在S中，而在S中。這與S是圖G的一個集團相矛盾。所以，S必定是圖G的頂點覆蓋。并且若|S|k，則|S|nk。,另一方面，需證明：若G有一個規(guī)模至多為nk的結點覆蓋S，則G有一個規(guī)模至少為k的集團S，S=VS。反證法：若S不是完全圖，則S中至少有一對頂點uS，vS之間缺少邊，該邊（u,v）應屬于，即S未覆蓋此邊。這與S是G的頂點覆蓋相矛盾。因此，S必為完全圖。若|S|nk，則|S|k。,10.3.33元CNF可滿足性,例107（3SAT）3元CNF可滿足性問題是指一個CNF公式F中，每個子句包含恰好3個文字時的可滿足性問題。,可滿足性的若干結果是可滿足的，當且僅當公式f=(y1y2)(y2)(y1)()是可滿足的。其中，是公式，y1和y2是變量。由于y1，y2，y1y2，y2,y1和不同時為真。所以，是可滿足的，當且僅當公式f是可滿足的。,12是可滿足的，當且僅當公式f=(12y)(12)是可滿足的。由于y，兩者之一為假。所以，12是可滿足的，當且僅當公式f是可滿足的。,f1f2是可滿足的，當且僅當公式f=(f1y)(f2)是可滿足的，f1和f2是公式，y是變量，并且不出現(xiàn)在f1和f2中。若f1f2是可滿足的，則必有f1或f2為真。若f1為真，可令y為假，則f可滿足；否則，若f2為真，可令y為真，則f可滿足。若f是可滿足的，因為y，若y為真，則必有f2為真，若y為假，則必有f1為真。即無論y為何值，只有f1f2為真時，f才為真。,定理105CNF可滿足性3元CNF可滿足性。證明：使用上述結論，可將任意一個CNF公式在多項式時間內轉換成一個3元CNF公式，且這種轉換能夠維持可滿足性不變。因此，CNF可滿足性3元CNF可滿足性，故3元CNF可滿足性問題是NP完全的。,10.3.4圖的著色數(shù),例108（圖著色數(shù)判定問題）對給定的無向圖G著色，是指對圖中任何兩個相鄰頂點都分配不同顏色。圖的著色問題是求對給定無向圖著色所必需的最少顏色種類，而圖著色判定問題是確定能否使用k種顏色對一個給定的無向圖著色的問題。,定理1063元CNF可滿足性著色數(shù)判定問題。證明：仍然分兩步證明這一結論。第一步：以3元CNF可滿足性問題的任意一個實例公式F為輸入，構造一個著色數(shù)判定問題的實例(G，k)，其中G=(V,E)為無向圖，k為正整數(shù)。第二步：從兩方面證明“3元CNF公式F是可滿足的，當且僅當圖G是n+1可著色的?！?總共3n+k個頂點,證明：3元CNF公式F是可滿足的，當且僅當圖G是n+1可著色的。若F是可滿足的，則圖G是n+1可著色的若圖G是n+1可著色的，則F是可滿足的,綜上所述，可在多項式時間內從3元CNF可滿足性問題的任意一個實例公式F，構造一個圖著色數(shù)問題的實例無向圖G=(V,E)，并且3元CNF公式F是可滿足的，當且僅當圖G是n+1可著色的，所以，3元CNF可滿足性著色數(shù)判定問題，著色數(shù)判定問題是NP完全的。,