計(jì)算機(jī)算法設(shè)計(jì)與分析第十章NP-Hard和NP-CompleteVIP

10.1基本概念10.1.1不確定的算法10.1.2NP-Hard和NP-Complete類10.3NP-Hard問(wèn)題實(shí)例第十章NP-Hard和NP-Complete1預(yù)備知識(shí)算法時(shí)間復(fù)雜度的漸進(jìn)表示多項(xiàng)式時(shí)間算法與非多項(xiàng)式時(shí)間算法10.1基本概念2確定算法運(yùn)算結(jié)果是唯一確定的之前介紹的算法都是確定算法確定算法可以在確定型圖靈機(jī)上執(zhí)行不確定算法運(yùn)算結(jié)果不是唯一確定的不確定算法可以在非確定型圖靈機(jī)上執(zhí)行10.1.1不確定的算法3圖靈機(jī)1936年圖靈提出了一個(gè)抽象計(jì)算模型──

圖靈機(jī)，并用它來(lái)精確定義可計(jì)算函數(shù)。圖靈機(jī)的基本思想是模擬人用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程，這個(gè)運(yùn)算過(guò)程可分解為下面兩種簡(jiǎn)單的動(dòng)作：

1.在紙上寫(xiě)或擦除某個(gè)符號(hào)；

2.把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置。在每個(gè)階段將由執(zhí)行運(yùn)算的人決定下一步的動(dòng)作，而他的決定依賴于此人當(dāng)前所關(guān)注的是紙上哪個(gè)位置的符號(hào)，以及此人當(dāng)前思維的狀態(tài)。

4TuringMachine5DeterministicTuringMachine定義一臺(tái)圖靈機(jī)由一個(gè)八元組所組成TM=(Q,T,I,δ,b,q0,

qaccept,qreject)其中Q：一個(gè)有限狀態(tài)集；

T：一個(gè)有限符號(hào)集（字母表）；

I：輸入字符集，I

T；

b：空符，b∈T－I；

δ：Q×T的子集→Q×(T×{L,R,S})，即轉(zhuǎn)移函數(shù)或有限狀態(tài)控制函數(shù)，其中L,R表示讀寫(xiě)頭左移或右移，S表示讀寫(xiě)頭原地不動(dòng)；

q0：表示初始狀態(tài)；

qaccepr：表示終止（接受）狀態(tài)；

qreject：表示拒絕狀態(tài)。這里規(guī)定δ是單值映射，所以也稱為確定型圖靈機(jī)。6一個(gè)例子例：設(shè)TM=({0,1,10,11},{0,1,“”(空格)},{0,1},δ,0)，做一個(gè)以1的個(gè)數(shù)表示數(shù)值的整數(shù)加法運(yùn)算,在磁帶上的數(shù)據(jù)設(shè)為0000001110110000，就是3+2的意思。轉(zhuǎn)移函數(shù)δ定義如下：

0,0→0,0R

0,1→1,1R

1,0→10,1R

1,1→1,1R

10,0→11,0L

10,1→10,1R

11,0→

E

11,1→

S在

xx,y

→

aa,bb

中，xx是當(dāng)前狀態(tài)，y是當(dāng)前格子的值，aa是程序下一步的狀態(tài)，b是當(dāng)前格的修改值。例如第一行指令

0,0→0,0R，意思就是如果機(jī)器讀到格子的值是0，就將其仍變成0，狀態(tài)變?yōu)?，讀寫(xiě)頭向右移動(dòng)一格。最后兩行中的E代表錯(cuò)誤，S代表停機(jī)。

7圖靈機(jī)的格局序列

（粗體的字符表示讀寫(xiě)頭的當(dāng)前位置）

步數(shù)狀態(tài)磁帶步數(shù)狀態(tài)磁帶1000000011101100009100000011101100002000000011101100001010000001110110000300000001110110000111000000011111100004000000011101100001210000000111111000050000000111011000013100000001111110000600000001110110000141100000011111100007000000011101100001500000001111100000 (停機(jī))810000001110110000

8其他類型的圖靈機(jī)雙向無(wú)限帶圖靈機(jī)。其帶子向左向右都是無(wú)限長(zhǎng)的，與確定型圖靈機(jī)基本模型不同的是，它的帶子沒(méi)有左端、帶頭永遠(yuǎn)不會(huì)走出兩端。多帶多頭圖靈機(jī)。它具有一個(gè)有窮控制器，k個(gè)帶頭和k條帶子，每條帶子都是雙向無(wú)窮的，并且各帶頭在操作時(shí)相互獨(dú)立，除改寫(xiě)帶符、左右移動(dòng)外，還可以保持不動(dòng)。非確定型圖靈機(jī)。這種類型的圖靈機(jī)具有一個(gè)有限控制器和一條單向無(wú)限帶，對(duì)于一個(gè)給定的狀態(tài)，機(jī)器的下一動(dòng)作可以有窮多個(gè)選擇，每個(gè)選擇包括一個(gè)新?tīng)顟B(tài)，一個(gè)要打印的帶符號(hào)和一個(gè)帶頭移動(dòng)方向。9非確定型圖靈機(jī)定義:

一個(gè)非確定型圖靈機(jī)（NDTM）由下述八元組給出：

NDTM=(Q，T，I，δ，b，q0，qaccept，qreject)

其中Q,T,I,b,q0

和qr

的定義與確定型圖靈機(jī)的相同，唯一的區(qū)別在于狀態(tài)控制函數(shù)（轉(zhuǎn)移函數(shù)）δ。非確定型圖靈機(jī)的狀態(tài)控制函數(shù)δ給出的下一個(gè)動(dòng)作不是唯一確定的,即δ為多值映射,它的值域是一個(gè)有窮集合A。因此非確定型圖靈機(jī)在下一時(shí)刻的動(dòng)作可以有多種選擇。在處理問(wèn)題時(shí)，對(duì)于δ(q1,al,…,ak)的多個(gè)值，非確定型圖靈機(jī)對(duì)于其中任意一個(gè)值都存在一個(gè)格局序列可以推導(dǎo)下去，只要其中有一種可以到達(dá)終止?fàn)顟B(tài)qaccept，就說(shuō)該問(wèn)題是可以處理的（輸入字符串被接受或函數(shù)是可計(jì)算的）。10在SPARKS語(yǔ)言中增加：choice(S)failuresuccess例10.1不確定機(jī)上的檢索算法例10.2不確定機(jī)上的排序算法不確定算法的表示11非確定機(jī)在現(xiàn)實(shí)技術(shù)條件下是不存在的，是為了分析計(jì)算機(jī)復(fù)雜度難題而虛構(gòu)的理論模型?？梢栽O(shè)想非確定機(jī)在執(zhí)行choice(S)語(yǔ)句時(shí)，具有主動(dòng)選擇正確值（導(dǎo)致success）的能力，這是通過(guò)同時(shí)復(fù)制大量副本實(shí)現(xiàn)的。非確定算法的設(shè)計(jì)思路一般是，先隨機(jī)生成解，再檢查是否為答案。不確定算法的執(zhí)行12只關(guān)心唯一輸出的不確定算法不確定的判定算法只產(chǎn)生0/1輸出0:當(dāng)且僅當(dāng)沒(méi)有一種選擇可導(dǎo)致success1:當(dāng)且僅當(dāng)至少存在一種選擇導(dǎo)致success輸出隱含于success和failure，此外無(wú)輸出語(yǔ)句最優(yōu)化問(wèn)題和判定問(wèn)題是相互對(duì)應(yīng)的，很多問(wèn)題滿足：判定問(wèn)題在多項(xiàng)式時(shí)間內(nèi)求解當(dāng)且僅當(dāng)對(duì)應(yīng)的最優(yōu)化問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)求解，反之亦然不確定的判定算法13不確定算法的時(shí)間復(fù)雜度14可滿足性問(wèn)題[SAT]15可滿足性問(wèn)題時(shí)間復(fù)雜度O(n)1610.1.2NP-Hard和NP-Complete對(duì)于算法A，如果存在多項(xiàng)式P()，使得對(duì)A的每個(gè)大小為n的輸入，A的計(jì)算時(shí)間為O(P(n))，則稱A具有多項(xiàng)式時(shí)間復(fù)雜度。P是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題的集合。17cook定理【cook定理】可滿足性(SAT)在P內(nèi)，當(dāng)且僅當(dāng)P=NP。SAT問(wèn)題如果有多項(xiàng)式解，當(dāng)且僅當(dāng)P=NP18約化（多項(xiàng)式變換）理解：算法L1約化為算法L2當(dāng)且僅當(dāng)存在一個(gè)多項(xiàng)式時(shí)間的確定算法可將算法L1轉(zhuǎn)換為算法L2【算法L2的解決意味著L1的解決，反之不一定】【L2

可能比L1更復(fù)雜】19NP-Hard和NP-Complete如果可滿足性問(wèn)題可約化為一個(gè)問(wèn)題L，則L是NP-Hard

如果L是NP-Hard

且LNP，則L是NP-CompleteNP-CompleteNP-Hard有的問(wèn)題，判定問(wèn)題是NP完全，優(yōu)化問(wèn)題是NP難度但非NP完全。20NP-Hard非NP-Complete實(shí)例21

如何證明一個(gè)問(wèn)題是NP-難度的證明L是NP-難度，只需證明一個(gè)已知的NP-難度問(wèn)題可約化為L(zhǎng)證明L是NP-完全，需首先證明L是NP-難度，在找到一個(gè)解決它的多項(xiàng)式時(shí)間不確定算法22NP完全問(wèn)題第一個(gè)NP完全問(wèn)題（Cook定理1971）可滿足性問(wèn)題是NP完全問(wèn)題六個(gè)NP完全問(wèn)題（Karp1972)3SAT、團(tuán)集等更多的NP完全問(wèn)題1979年：300多個(gè)1998年：2000多個(gè)23最大集團(tuán)問(wèn)題(clique)G=(V,E)的最大完全子圖稱為一個(gè)集團(tuán)(Clique)。最大集團(tuán)問(wèn)題是確定G內(nèi)最大集團(tuán)的大小。對(duì)應(yīng)的判定問(wèn)題CDP是，是否存在大小至少為k的集團(tuán)。10.2NP-難度問(wèn)題實(shí)例24CDP屬于NP25定理10.2