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

算法分析設(shè)計(jì)完全問題第1頁，共30頁，2023年，2月20日，星期二第10章NP完全問題

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

10.1基本概念

10.2.1Cook定理

10.3一些典型的NP完全問題第3頁，共30頁，2023年，2月20日，星期二10.1基本概念將能在多項(xiàng)式時間內(nèi)求解的問題視為易處理問題(tractableproblem)。至今尚未找到多項(xiàng)式時間算法求解的問題視為難處理問題(intractableproblem)。

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

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

——不存在任何算法求解如果任意一個NP難度問題存在一個多項(xiàng)式時間算法，那么所有NP完全問題都可以在多項(xiàng)式時間內(nèi)求解。一個NP完全問題可以在多項(xiàng)式時間內(nèi)求解，當(dāng)且僅當(dāng)所有其他的NP完全問題都可以在多項(xiàng)式時間內(nèi)求解。第4頁，共30頁，2023年，2月20日，星期二10.1.1不確定算法和不確定機(jī)

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

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

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

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

}cout<<-1;

Failure(); //不確定算法失敗終止}執(zhí)行時間都為O(1)若算法執(zhí)行中需作出一系列的Choice函數(shù)選擇，當(dāng)且僅當(dāng)Choice的任何一組選擇都不會導(dǎo)致成功信號時，算法在O(1)時間不成功終止。如果一個判定問題實(shí)例的解為真，Choice函數(shù)每一次總能在O(1)時間內(nèi)做出導(dǎo)致成功的正確選擇。包含不確定選擇語句，并能按上述方式執(zhí)行一個算法的機(jī)器稱為不確定機(jī)（nondeterministicmachine)。在不確定機(jī)上執(zhí)行的算法稱為不確定算法(nondeterministicalgorithm)。第6頁，共30頁，2023年，2月20日，星期二不確定機(jī)的執(zhí)行方式，可理解為不受限制的并行計(jì)算：不確定機(jī)執(zhí)行不確定算法時，每當(dāng)Choice函數(shù)進(jìn)行選擇時，就好像復(fù)制了多個程序副本，每一種可能的選擇產(chǎn)生一個副本，所有副本同時執(zhí)行。一旦一個副本成功完成，將立即終止所有其他副本的計(jì)算。如果存在至少一種成功完成的選擇，一臺不確定機(jī)總能做出最佳選擇，以最短的程序步數(shù)完成計(jì)算，并成功終止。不確定機(jī)能及時判斷算法的某次執(zhí)行不存在任何導(dǎo)致成功完成的選擇，并使算法在一個單位時間內(nèi)輸出“不成功”信息后終止。顯然，這種機(jī)器是虛構(gòu)的，是一種概念性計(jì)算模型！第7頁，共30頁，2023年，2月20日，星期二不確定搜索算法：voidSearch(inta[],Tx){intj=Choice(0,n-1);if(a[j]==x){ cout<<j;

Success();

}cout<<-1;

Failure(); }定義10-1

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

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

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

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

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

——利用多項(xiàng)式約化（歸約）的方法（1）選擇一個已知其具有NP難度的問題Q1；（2）證明能夠從Q1的一個實(shí)例I1，在多項(xiàng)式時間內(nèi)構(gòu)造Q的一個實(shí)例I；（3）證明能夠在多項(xiàng)式時間內(nèi)從I的解確定I1的解。（4）從（2）和（3）可知，Q1∝Q；（5）從（1）和（4）及約化的傳遞性得出所有NP類問題均可約化到Q，所以Q是NP難度的。（6）*如果Q是NP類問題，則Q是NP完全的。第24頁，共30頁，2023年，2月20日，星期二10.3.1最大集團(tuán)最大集團(tuán)判定問題是NP類問題。“集團(tuán)”是無向圖中的完全子圖，任意一對頂點(diǎn)間有邊相連。P231程序10-3是求解該問題的多項(xiàng)式時間不確定算法?；颍簩o定的圖G=(V,E)，檢查頂點(diǎn)集V’V中每一對頂點(diǎn)u,v間是否存在邊(u,v)∈E，即可在多項(xiàng)式時間內(nèi)完成對V’是否是集團(tuán)的檢查。第25頁，共30頁，2023年，2月20日，星期二最大集團(tuán)判定問題是NP完全的。下面證明：證明思路：證明CNF可滿足性∝最大集團(tuán)判定問題，所以最大集團(tuán)判定問題是NP難度的。又因?yàn)樽畲蠹瘓F(tuán)判定問題是NP類問題（前面已證）所以最大集團(tuán)判定問題是NP完全的。第26頁，共30頁，2023年，2月20日，星期二定理10-3CNF可滿足性∝最大集團(tuán)判定問題證明：1、在多項(xiàng)式時間內(nèi)，以任意給定的CNF公式F為輸入，構(gòu)造一個相應(yīng)的無向圖G；2、證明F是可滿足的，當(dāng)且僅當(dāng)G有