算法分析設(shè)計(jì)10-NP完全問題

算法設(shè)計(jì)與分析張怡婷Email:zyt@第10章NP完全問題

學(xué)習(xí)要點(diǎn)：確定算法和不確定算法判定問題和最優(yōu)化問題的關(guān)系可滿足性問題P類問題和NP類問題NP難度(NPhard)和NP完全(NPcomplete)問題Cook定理典型的NP完全（或NP難度）問題的證明章節(jié)內(nèi)容:

10.1基本概念

10.2.1Cook定理

10.3一些典型的NP完全問題10.1基本概念將能在多項(xiàng)式時(shí)間內(nèi)求解的問題視為易處理問題(tractableproblem)。至今尚未找到多項(xiàng)式時(shí)間算法求解的問題視為難處理問題(intractableproblem)。

——NP完全問題或NP難度(NPhard)問題

——如：指數(shù)時(shí)間算法 無論消耗多少計(jì)算機(jī)時(shí)間和空間也不能求解的稱為不可判定(undecidable)的。

——不存在任何算法求解如果任意一個(gè)NP難度問題存在一個(gè)多項(xiàng)式時(shí)間算法，那么所有NP完全問題都可以在多項(xiàng)式時(shí)間內(nèi)求解。一個(gè)NP完全問題可以在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)所有其他的NP完全問題都可以在多項(xiàng)式時(shí)間內(nèi)求解。10.1.1不確定算法和不確定機(jī)

不確定算法的抽象計(jì)算模型：算法在抽象機(jī)上運(yùn)行與計(jì)算機(jī)系統(tǒng)的性能無關(guān)；算法的執(zhí)行表現(xiàn)為執(zhí)行一個(gè)基本運(yùn)算序列；基本運(yùn)算的執(zhí)行時(shí)間是有限常量；Choice(S)：任意選擇集合S的一個(gè)元素。Failure()：發(fā)出不成功完成信號(hào)后算法終止。Success()：發(fā)出成功完成信號(hào)后算法終止。例10-1

在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中，則確定使a[j]==x的下標(biāo)j，否則輸出-1。不確定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1); //從{0,1,...,n-1}中任意選取一個(gè)值

if(a[j]==x){ cout<<j;

Success(); //不確定算法成功終止

}cout<<-1;

Failure(); //不確定算法失敗終止}執(zhí)行時(shí)間都為O(1)若算法執(zhí)行中需作出一系列的Choice函數(shù)選擇，當(dāng)且僅當(dāng)Choice的任何一組選擇都不會(huì)導(dǎo)致成功信號(hào)時(shí)，算法在O(1)時(shí)間不成功終止。如果一個(gè)判定問題實(shí)例的解為真，Choice函數(shù)每一次總能在O(1)時(shí)間內(nèi)做出導(dǎo)致成功的正確選擇。包含不確定選擇語句，并能按上述方式執(zhí)行一個(gè)算法的機(jī)器稱為不確定機(jī)（nondeterministicmachine)。在不確定機(jī)上執(zhí)行的算法稱為不確定算法(nondeterministicalgorithm)。不確定機(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ī)總能做出最佳選擇，以最短的程序步數(shù)完成計(jì)算，并成功終止。不確定機(jī)能及時(shí)判斷算法的某次執(zhí)行不存在任何導(dǎo)致成功完成的選擇，并使算法在一個(gè)單位時(shí)間內(nèi)輸出“不成功”信息后終止。顯然，這種機(jī)器是虛構(gòu)的，是一種概念性計(jì)算模型！不確定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);if(a[j]==x){ cout<<j;

Success();

}cout<<-1;

Failure(); }定義10-1

（不確定算法時(shí)間復(fù)雜度）一個(gè)不確定算法所需的時(shí)間是指對(duì)任意一個(gè)輸入，當(dāng)存在一個(gè)選擇序列導(dǎo)致成功完成時(shí)，達(dá)到成功完成所需的最少程序步。在不可能成功完成的情況下，所需時(shí)間總是O(1)。若元素x在數(shù)組中，Choice函數(shù)總能在O(1)時(shí)間內(nèi)選中該元素下標(biāo)，并成功終止。否則，算法在O(1)時(shí)間失敗終止。因此該不確定搜索算法的時(shí)間復(fù)雜度為O(1)。例10-2

將n個(gè)元素的序列排成有序序列。不確定排序算法：voidNSort(inta[],intn){intb[mSize],i,j;for(i=0;i<n;i++)b[i]=0; //將b初始化為0for(i=0;i<n;i++) //將每個(gè)a[i]存放在一個(gè)空閑的b[j]中

{ j=Choice(0,n-1); //任意選擇一個(gè)下標(biāo)

if(b[j])Failure; //若b[j]≠0，則算法失敗終止

b[j]=a[i]; //將a[i]付給b[j]}for(i=0;i<n-1;i++) //驗(yàn)證b中元素是否已經(jīng)有序

if(b[i]>b[i+1])Failure(); //若存在兩元素逆序，則失敗

Success(); //Choice函數(shù)的n次正確選擇，算法成功}必定存在對(duì)b中下標(biāo)的n次恰當(dāng)選擇，使得能將每個(gè)a[i]恰好保存在一個(gè)空閑的b[j]處，并且進(jìn)一步確保b中元素排成有序序列，從而能順利通過隨后的有序性驗(yàn)證，導(dǎo)致成功終止。因此該不確定搜索算法的時(shí)間復(fù)雜度為O(n)。判定問題和最優(yōu)化問題一個(gè)只要求產(chǎn)生“0”或“1”作為輸出的問題稱為判定問題（decisionproblem）。許多最優(yōu)化問題都可以得到與其相對(duì)應(yīng)的判定問題，且兩者往往存在計(jì)算上的相關(guān)性：一個(gè)判定問題能夠在多項(xiàng)式時(shí)間內(nèi)求解，當(dāng)且僅當(dāng)它相應(yīng)的最優(yōu)化問題可以在多項(xiàng)式時(shí)間內(nèi)求解。如果判定問題不能在多項(xiàng)式時(shí)間內(nèi)求解，那么它相應(yīng)的最優(yōu)化問題也不能在多項(xiàng)式時(shí)間內(nèi)求解。例10-3最大集團(tuán)及其判定問題無向圖G=（V,E）的一個(gè)完全子圖稱為該圖的一個(gè)集團(tuán)，集團(tuán)的規(guī)模用集團(tuán)的頂點(diǎn)數(shù)衡量。最大集團(tuán)問題：確定圖G的最大集團(tuán)規(guī)模的問題。最大集團(tuán)判定問題：判定圖G是否存在一個(gè)規(guī)模至少為k的集團(tuán)。（k為給定正整數(shù)）若最大集團(tuán)問題能在多項(xiàng)式時(shí)間O(g(n))內(nèi)求解。 當(dāng)且僅當(dāng)對(duì)應(yīng)的判定問題能在多項(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)問題的算法，求得最大集團(tuán)的規(guī)模為k’。若k’≥k，則最大集團(tuán)判定問題的解為“1”，否則為“0”。顯然有O(f(n))=O(g(n))。許多抽象問題并不是判定問題，而是最優(yōu)化問題，必須最大化或最小化某個(gè)量。然而，如我們看到的，將最優(yōu)化問題轉(zhuǎn)化為一個(gè)并不更難的判定問題通常是比較簡單的。10.1.2可滿足性問題數(shù)理邏輯中，一個(gè)變量和它的非都稱為文字。命題公式是由文字及邏輯運(yùn)算符“與(∧)”和“或(∨)”構(gòu)成的表達(dá)式。如果一個(gè)公式具有邏輯與形式：C1∧C2∧...∧Ck，其中每個(gè)子句Ci都是邏輯或形式li1∨li2∨...∨lip，每個(gè)lij是文字，則將這種形式的公式稱為合取范式(conjunctivenormalform，CNF)。如果一個(gè)公式具有邏輯或形式：C1∨C2∨...∨Ck，其中每個(gè)子句Ci都是邏輯與形式li1∧li2∧...∧liq，每個(gè)lij是文字，則將這種形式的公式稱為析取范式(disjunctivenormalform，DNF)。例10-4可滿足性問題（satisfiabilityproblem)是一個(gè)判定問題，確定對(duì)于一個(gè)給定的命題公式，是否存在布爾變量的一種賦值（也稱真值指派）使該公式為真。例如：公式是可滿足的。只需令x1=1，x2=0，x3=0。公式是不可滿足的。程序10-4可滿足性問題的不確定算法voidEval(CNFE,intn){intx[mSize];for(inti=1;i<=n;i++) //O(n) x[i]=Choice(0,1); //為變量x[i]賦0或1值

if(E(x,n))Success(); //O(e)，計(jì)算公式E(x,n)的值

//若為真，成功終止

elseFailure();}因?yàn)椋簩?duì)n個(gè)布爾變量賦值需要O(n)時(shí)間，計(jì)算公式E(x,n)的時(shí)間為O(e)，e是公式長度。所以，可滿足性問題的不確定算法時(shí)間為O(n+e)。10.1.3P類和NP類問題P類問題：可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問題。NP類問題：可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問題。（多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證問題的解。）確定算法是不確定算法當(dāng)Choice函數(shù)只有一種選擇時(shí)的特例，所以有：但至今無法斷定：是否P=NP或者P≠NP。定義10-3多項(xiàng)式約化令Q1和Q2是兩個(gè)問題，如果存在一個(gè)確定算法A求解Q1，而算法A以多項(xiàng)式時(shí)間調(diào)用另一個(gè)求解Q2的確定算法B。若不計(jì)B的工作量，算法A是多項(xiàng)式時(shí)間的，則稱Q1約化(reducedto)為Q2，記作Q1∝Q2。即：求解Q1的確定算法是通過調(diào)用求解Q2的確定算法完成的，對(duì)Q2算法實(shí)施的調(diào)用過程所需的時(shí)間是多項(xiàng)式時(shí)間的。那么：只要對(duì)問題Q2存在多項(xiàng)式時(shí)間求解算法，問題Q1就能在多項(xiàng)式時(shí)間內(nèi)得以求解。約化存在以下性質(zhì)：性質(zhì)10-1

若Q1∈P，Q2∝Q1，則有Q2∈P。性質(zhì)10-2（傳遞性）若Q1∝Q2，Q2∝Q3，則Q1∝Q3。10.1.4NP難度和NP完全問題性質(zhì)10-4NP難度（NPhard）對(duì)任意問題Q1∈NP都有Q1∝Q，則稱問題Q是NP難度（NPhard）的。只要對(duì)任何一個(gè)NP難度問題Q找到了它的多項(xiàng)式時(shí)間算法，那么，可以斷定所有NP類問題都能在多項(xiàng)式時(shí)間內(nèi)求解，因?yàn)樗蠳P類問題都能約化到問題Q。（然而目前尚無任何一個(gè)NP難度問題具有多項(xiàng)式時(shí)間算法。）性質(zhì)10-5NP完全（NPcomplete）對(duì)于問題Q∈NP且Q是NP難度的，則稱Q是NP完全（NPcomplete，NPC）的。所有NP完全問題都是NP難度的，反之不然，NP難度問題不一定是NP完全的（若不是NP類問題，則不是NP完全的）?，F(xiàn)實(shí)意義：若一個(gè)問題被證明是NP難度（NPhard）的，則很難找到一個(gè)多項(xiàng)式時(shí)間的有效算法。若問題的實(shí)例規(guī)模較大，則應(yīng)選擇采用啟發(fā)式算法、隨機(jī)算法或近似算法等其他算法策略求解。如何確定某個(gè)問題是否是NP難度的？證明某個(gè)問題Q是NP難度（NPhard）的證明策略：(1)選擇一個(gè)已經(jīng)證明是NP難度問題Q1;(2)求證Q1∝Q。則問題Q是NP難度的。由于Q1是NP難度的，因此所有NP類問題都可約化到Q1。根據(jù)約化的傳遞性，任何NP類問題都可約化到Q。所以，Q是NP難度的。在此基礎(chǔ)上，若進(jìn)一步表明Q本身是NP類的，則問題Q是NP完全的。10.2Cook定理和證明10.2.1Cook定理斯蒂芬?庫克（StevenCook）于1971年證明了第一個(gè)NP完全問題，稱為Cook定理，表明可滿足性問題是NP完全的。至今至少已有300多個(gè)問題被證明是NP難度問題，但尚未證明其中任何一個(gè)是屬于P的。10.3一些典型的NP完全問題

證明(一個(gè)猜想可能是NP難度的)問題Q確實(shí)是NP難度(或NP完全)問題的具體步驟：

——利用多項(xiàng)式約化（歸約）的方法（1）選擇一個(gè)已知其具有NP難度的問題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）可知，Q1∝Q；（5）從（1）和（4）及約化的傳遞性得出所有NP類問題均可約化到Q，所以Q是NP難度的。（6）*如果Q是NP類問題，則Q是NP完全的。10.3.1最大集團(tuán)最大集團(tuán)判定問題是NP類問題。“集團(tuán)”是無向圖中的完全子圖，任意一對(duì)頂點(diǎn)間有邊相連。P231程序10-3是求解該問題的多項(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)判定問題是NP完全的。下面證明：證明思路：證明CNF可滿足性∝最大集團(tuán)判定問題，所以最大集團(tuán)判定問題是NP難度的。又因?yàn)樽畲蠹瘓F(tuán)判定問題是NP類問題（前面已證）所以最大集團(tuán)判定問題是NP完全的。定理10-3CNF可滿足性∝最大集團(tuán)判定問題證明：1、在多項(xiàng)式時(shí)間內(nèi)，以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無向圖G；2、證明F是可滿足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。定理10-3CNF可滿足性∝最大集團(tuán)判定問題證明：1、在多項(xiàng)式時(shí)間內(nèi)，以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無向圖G；令F=C1∧C2∧...∧Ck是一個(gè)具有k個(gè)子句的CNF形式的布爾公式。由公式F構(gòu)造無向圖G的方法為：V={<σ,i>|σ是子句Ci的一個(gè)文字}E={(<σ,i>,<δ,j>)|i≠j

且σ≠}屬于哪個(gè)子句σ和δ處于不同的分句中σ和δ相應(yīng)的文字是一致的如：則G就是下圖：定理10-3CNF可滿足性∝最大集團(tuán)判定問題證明：2、證明F是可滿足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。（一方面，如果F可滿足，那么圖G中必定存在規(guī)模為k的集團(tuán)。）若F是可滿足的，則必定存在布爾變量的一個(gè)賦值，使F的每個(gè)子句Ci中至少有一個(gè)文字為真。若σi是子句Ci中為真的文字，則S={<σ1,1>,<σ2,2>,...,<σk,k>}是圖G中相應(yīng)頂點(diǎn)集合。根據(jù)圖的構(gòu)造方法，集合S中任意一對(duì)頂點(diǎn)<σi,i>和<σj,j>，由于σi和σj都為真且i≠j，因此它們之間應(yīng)該有邊相連，從而形成完全圖。S就是圖G的規(guī)模為k的集團(tuán)。定理10-3CNF可滿足性∝最大集團(tuán)判定問題證明：2、證明F是可滿足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。（另一方面，若圖G有一個(gè)規(guī)模至少為k的集團(tuán)，則必定存在一種布爾變量賦值，使命