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

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

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

9.3NP完全問(wèn)題（NPC）

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

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

，當(dāng)τ(n)為多項(xiàng)式時(shí)，稱Q1可多項(xiàng)式變換為問(wèn)題Q2

，記為Q1∝pQ2問(wèn)題Q1問(wèn)題Q2

算法AI

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

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

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

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