各種算法集合講解章完全理論

算法設(shè)計與分析授課教師：王秋芬辦公地點：7307Email:第九章NP完全理論目錄易解問題和難解問題三種計算模型P類和NP類問題NP完全問題NP完全問題的近似算法教學(xué)目標理解易解問題和難解問題了解三種計算模型理解P類與NP類的概念（重點）理解NP完全問題的概念（重點）理解近似算法的近似比及相對誤差的概念通過實例掌握部分NP完全問題的近似算法（重點）9.1易解問題和難解問題易解問題：在多項式時間內(nèi)解決的問題排序（冒泡排序、合并排序、快速排序）會場安排問題單源最短路徑問題哈夫曼編碼最小生成樹二分查找矩陣連乘問題難解問題：在指數(shù)時間內(nèi)解決的問題不可判定問題（太難了，不存在任何算法求解）圖靈機停機問題（1936年被證明是不可判定問題）希爾伯特第十問題（整數(shù)多項式方程的可解性問題在1970年由蘇、美數(shù)學(xué)家證明Hilbert所期望的一般算法是不存在的，是不可判定問題）非決定的難處理問題旅行商問題漢諾塔為什么把多項式時間復(fù)雜性作為易解問題和難解問題的分界線？1．多項式時間與指數(shù)時間隨問題規(guī)模增長的增長率有本質(zhì)的差別2．計算機性能的提高對多項式時間算法和指數(shù)時間算法的影響不同3．多項式時間復(fù)雜性忽略了系數(shù)，但不影響易解問題和難解問題的劃分4．多項式時間復(fù)雜性的閉包性5．多項式時間復(fù)雜性的分析結(jié)果，對于常用的各種計算機形式模型具有不變性。補：三種計算模型（RAM,RASP,TM）隨機存取機RAM(RandomAccessMachine)的構(gòu)造累加器指令計數(shù)器程序存儲部件內(nèi)存儲器r0r1r2…只讀輸入帶……只寫輸出帶RAM定義了輸入帶到輸出帶的映射：（1）計算函數(shù)裝置（2）語言接受器RAM的復(fù)雜性標準標準一：均勻耗費標準在均勻耗費標準下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間。標準二：對數(shù)耗費標準對數(shù)耗費標準是執(zhí)行一條指令的耗費與以二進制表示的指令的操作數(shù)長度成比例。隨機存取機RAM隨機存取存儲程序機RASP隨機存取存儲程序機RASP(RandomAccessStoredProgramMachine)1、RASP的結(jié)構(gòu)RASP的整體結(jié)構(gòu)類似于RAM，所不同的是RASP的程序是存儲在寄存器中且能修改自身。每條RASP指令占據(jù)2個連續(xù)的寄存器。第一個寄存器存放操作碼的編碼，第二個寄存器存放地址。2、RASP程序的復(fù)雜性不管是在均勻耗費標準下，還是在對數(shù)耗費標準下，RAM程序和RASP程序的復(fù)雜性只差一個常數(shù)因子。即T(n)與KT(n)圖靈機(TuringMachine)圖靈機（TuringMachine）的構(gòu)造圖靈機原型……輸入帶有限狀態(tài)控制器磁頭1.改變有限狀態(tài)控制器的狀態(tài)2.清除讀寫頭下方的原有符號，并寫上新的符號3.讀寫頭向左或者向右移動一個方格，或不動TM的數(shù)學(xué)描述Q：有限狀態(tài)的集合；T：有限個帶符號的集合；IT：是輸入符號的集合；δ：Q×Tk→Q×(T×{L,R,S})k為轉(zhuǎn)移函數(shù)；B：唯一的空白符，b∈T–I；q0：初始狀態(tài)qf：終止狀態(tài)。M=(Q,T,I,δ,b,q0,qf)其中：圖靈機的語言圖靈機的解釋語言接受器：當(dāng)且僅當(dāng)從指定的初始狀態(tài)q0開始，經(jīng)過一系列計算步后，最終進入終止狀態(tài)qf時，稱圖靈機接受這個輸入符號串。圖靈機識別的一個語言：所有這臺圖靈機能接受的輸入符號串的集合計算函數(shù)的裝置：函數(shù)的自變量可編碼成一字符串輸入到一條輸入帶上，用一特殊符號＃隔開。若圖靈機經(jīng)過有限步后，在一條指定的帶上輸出整數(shù)y并停機，則可以說圖靈機計算出了f(x)=y。圖靈機的復(fù)雜性時間復(fù)雜性T(n)是輸入規(guī)模為n時所需的最大計算步數(shù)。如果圖靈機不停機，T(n)對這個n值無定義。空間復(fù)雜性S(n)是輸入規(guī)模為n時，在輸入帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)無定義圖靈機的變形多道圖靈機(輸入帶上有多個道)。雙向圖靈機(輸入帶被視為左右均是無窮的)。多帶圖靈機(具有多條輸入帶)。多頭圖靈機(具有多個磁頭)。多維圖靈機(輸入帶是多維的)。不確定的圖靈機(有限控制器是不確定的NDTM)。已經(jīng)證明各類變形圖靈機在可計算的能力上等價于原型圖靈機。但是在復(fù)雜性是有區(qū)別的。9.2P類和NP類問題判定問題是僅僅要求回答“yes”或“no”的問題判定問題的重要特性驗證比求解容易判定問題→語言的識別問題→計算模型許多問題以自然形式出現(xiàn)時并不是判定問題，但是可以轉(zhuǎn)化為判定問題圖的m可著色優(yōu)化問題旅行商問題0-1背包問題裝載問題單源最短路徑問題P類問題和NP類問題是針對語言識別問題基于圖靈機計算模型給出的。確定性算法與P類問題定義1設(shè)A是求解問題Π的一個算法，如果在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，則稱算法A是確定性（Determinism）算法。定義2如果對于某個判定問題Π，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個確定性算法，得到y(tǒng)es或no的答案，則該判定問題Π是一個P

類（Polynomial）問題。所有易解問題的判定問題都是P類問題如最短路徑的判定問題屬于P類問題非確定性算法與NP類問題定義3設(shè)A是求解問題Π的一個算法，如果算法A以如下猜測并驗證的方式工作，就稱算法A非確定性算法：（1）猜測階段：在這個階段，對問題的輸入實例產(chǎn)生一個任意字符串y，在算法的每一次運行時，串y的值可能不同，因此，猜測以一種非確定的形式工作。（2）驗證階段：在這個階段，用一個確定性算法驗證：①檢查在猜測階段產(chǎn)生的串y是否是合適的形式，如果不是，則算法停下來并得到no；②如果串y是合適的形式，則驗證它是否是問題的解，如果是，則算法停下來并得到y(tǒng)es，否則算法停下來并得到no。如旅行商問題，最大團問題，圖的m可著色判定問題。非確定性算法與NP類問題★定義4如果對于某個判定問題，存在一個非負整數(shù)k，對于輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個不確定算法，得到是或否的答案，則該判定問題是一個NP類問題。NP類問題是一類能夠用不確定算法在多項式時間內(nèi)求解的判定問題。對于NP類判定問題，它必須存在一個確定算法，能夠以多項式時間來檢查和驗證在猜測階段所產(chǎn)生的答案。思考：哈密頓回路判定問題是不是NP類問題？漢諾塔問題是不是NP類問題？P類問題和NP類問題的關(guān)系（1）P類問題可以用多項式時間的確定性算法來進行判定或求解。（2）NP類問題可以用多項式時間的不確定性算法來進行判定或求解，關(guān)鍵是存在一個確定算法，能夠以多項式的時間來驗證在猜測階段所產(chǎn)生的答案。顯然，因為DTMNDTM(是一個特例)，所以PNP。是否有P=NP？問題求解難于問題驗證，故大多數(shù)研究者相信NP類是比P類要大得多的集合，故P≠NP但是，時至今日，還沒有任何人能證明：在NP類中有哪個問題不屬于P類目前也沒有任何人能為NP類中的眾多難題里面的哪怕是一個難題，找到一個多項式時間算法。P=NP？這至今仍然是一個懸而未決的問題

9.3NP完全問題（NPC）

NP完全問題是NP類問題的一個子類，是更為復(fù)雜的問題。奇特的性質(zhì)如果一個NP完全問題能在多項式時間內(nèi)得到解決，那么NP類中的每個問題都可以在多項式時間內(nèi)得到解決，即P=NP成立！。思考：為什么一個NP完全問題能在多項式時間內(nèi)解決，NP類中的每一個問題都可以在多項式時間內(nèi)解決？多項式變換技術(shù)（問題的變換）

若問題Q1的求解能夠變換成問題Q2的求解且變換的時間為O(τ(n))，則稱Q1是τ(n)時間變換為Q2，簡記為Q1∝τ(n)Q2，其中n為問題Q1的規(guī)模。若Q1∝τ(n)Q2

，當(dāng)τ(n)為多項式時，稱Q1可多項式變換為問題Q2

，記為Q1∝pQ2問題Q1問題Q2

算法AI

輸入轉(zhuǎn)換I'O'O

輸出轉(zhuǎn)換問題變換的一般過程多項式變換的兩個性質(zhì)：(1)A∝pB且B∈P，則A∈P。(2)若A∝pB且B∝pC，則A∝pC例：配對問題到排序問題的變換排序問題——輸入I'是一組整數(shù)X=(x1,x2,…,xn)，輸出O'是這組整數(shù)的一個排列xi1≤xi2≤…≤xin。配對問題——輸入I是兩組整數(shù)X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)，輸出O是兩組整數(shù)的元素配對，即X中的最小值與Y中的最小值配對，X中的次小值與Y中的次小值配對，依此類推。

NPC與NP困難定義5令Q是一個判定問題，如果：（1）Q∈NP，即問題Q屬于NP類問題（2）對NP中的所有問題Q’，都有Q’∝pQ則稱判定問題Q是一個NP完全問題（NPcompleteproblem），簡記為NPC。定義6：對于問題Q，如果任意問題Q’∈NP，都有Q’∝pQ，則稱問題Q是NP困難的。P、NP、NPC、NP困難之間的關(guān)系如果P≠NP，則P、NP、NPC之間的關(guān)系或許如下圖所示。NPPNPC若判定問題屬于NP完全問題，則相應(yīng)的最優(yōu)化問題屬于NP難問題。NP難問題若干NP完全的問題Cook在1971年證明了第一個NP完全的問題。Cook定理：布爾表達式的可滿足性SAT是NP完全的?；谠搯栴}，逐漸生成了一棵以它為根的NP完全問題樹。1979年只證明了300多個NP完全問題目前，已證明的NP完全問題有幾千個，且在繼續(xù)增加。這一事實，增強了人們對P≠NP的猜測。但遺憾的是，這個猜測迄今仍然還只是個猜測。部分NP完全問題樹9.4NP完全問題的近似算法近似算法所適應(yīng)的問題是最優(yōu)化問題。對于一個規(guī)模為n的問題，近似算法應(yīng)該滿足下面兩個基本的要求：（1）算法的時間復(fù)雜性：要求算法能在n的多項式時間內(nèi)完成。（2）解的近似程度：算法的近似解應(yīng)滿足一定的精度。衡量精度的標準近似比相對誤差NP完全問題的近似解法（1）近似比若一個最優(yōu)化問題的最優(yōu)值為C，求解該問題的一個近似算法求得的近似最優(yōu)解相應(yīng)的目標函數(shù)值為c，則將該近似算法的近似比定義為在通常情況下，該近似比是問題輸入規(guī)模n的一個函數(shù)ρ(n)，即（2）相對誤差該近似算法的相對誤差定義為若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得則稱ε(n)為該近似算法的相對誤差界。近似算法的近似比ρ(n)與相對誤差界ε(n)之間顯然有如下關(guān)系：

ε(n)≥ρ(n)-1。1.頂點覆蓋問題問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V’，使得若(u,v)是G的一條邊，則v∈V’或u∈V’。頂點覆蓋V’的大小是它所包含的頂點個數(shù)|V’|。算法描述VertexSetapproxVertexCover(Graphg){cset=

；e1=g.e；while(e1!=

){從e1中任取一條邊(u,v)；cset=cset∪{u,v}；從e1中刪去與u和v相關(guān)聯(lián)的所有邊；}returnc}頂點覆蓋問題的近似算法的性能比為2。圖(a)～(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。2.裝箱問題問題描述：設(shè)有n個物品w1,w2,…,wn和若干個體積均為C的箱子b1,b2,…,bk,…。n個物品的體積分別為s1,s2,…,sn且有si≤C(1≤i≤n)。要求把所有物品分別裝入箱子且物品不能分割，使得占用箱子數(shù)最少的裝箱方案。近似算法：首次適宜法、最適宜法、首次適宜降序法和最適應(yīng)降序法3.旅行商問題問題描述：給定一個無向帶權(quán)圖G=(V，E)，對每一個邊(u，v)E，都有一個非負的常數(shù)費用c(u，v)>0，求G中費用最小的哈密爾頓回路。兩種類型旅行商問題歐幾里德旅行商問題（對于圖中的任意3個頂點u、v、w，其費用函數(shù)具有三角不等式性質(zhì)：c(u，v)≤c(u，w)+c(w，v)一般的旅行商問題歐幾里德旅行商問題的近似算法算法的設(shè)計思想：在圖中任選一個頂點u，用Prim