算法設(shè)計與分析王紅梅NP完全理論PPT學(xué)習(xí)教案

1、會計學(xué)1算法設(shè)計與分析王紅梅算法設(shè)計與分析王紅梅NP完全理論完全理論2.1 下界下界 對于任何待求解的對于任何待求解的問題問題，如果能找到一個盡可，如果能找到一個盡可能能大大的函數(shù)的函數(shù)g(n)（n為問題規(guī)模），使得求解該問題為問題規(guī)模），使得求解該問題的所有算法都可以在的所有算法都可以在(g(n)的時間內(nèi)完成，則函數(shù)的時間內(nèi)完成，則函數(shù)g(n)稱為該問題計算復(fù)雜性的稱為該問題計算復(fù)雜性的下界下界（Lower Bound）。 如果已經(jīng)知道一個和下界的效率類型相同的算法如果已經(jīng)知道一個和下界的效率類型相同的算法，則稱該下界是，則稱該下界是緊密緊密（Close）的。）的。 意義：評價算法；改進(jìn)算法

2、。意義：評價算法；改進(jìn)算法。第1頁/共33頁 對問題的輸入中必須要對問題的輸入中必須要處理處理的元素進(jìn)行計的元素進(jìn)行計數(shù)，同時，對必須要數(shù)，同時，對必須要輸出輸出的元素進(jìn)行計數(shù)。這的元素進(jìn)行計數(shù)。這種計數(shù)方法產(chǎn)生的是一個種計數(shù)方法產(chǎn)生的是一個平凡下界平凡下界（Ordinary Lower Bound）.2.1.1 平凡下界平凡下界 例例 ：生成：生成 n 個元素的所有排列對象的算法屬于個元素的所有排列對象的算法屬于(n!) v 平凡下界往往過小而失去意義。平凡下界往往過小而失去意義。例：例：TSP問題的平凡下界是問題的平凡下界是(n2)第2頁/共33頁2.1.2 判定樹模型判定樹模型 判定樹判

3、定樹（Decision Trees）是這樣一棵）是這樣一棵二叉樹二叉樹：它的每：它的每一個內(nèi)部結(jié)點對應(yīng)一個形如一個內(nèi)部結(jié)點對應(yīng)一個形如xy的比較，如果關(guān)系成立，則的比較，如果關(guān)系成立，則控制轉(zhuǎn)移到該結(jié)點的左子樹，否則，控制轉(zhuǎn)移到該結(jié)點的控制轉(zhuǎn)移到該結(jié)點的左子樹，否則，控制轉(zhuǎn)移到該結(jié)點的右子樹，它的每一個葉子結(jié)點表示問題的一個結(jié)果。右子樹，它的每一個葉子結(jié)點表示問題的一個結(jié)果。v 在用判定樹模型建立問題的時間下界時，通常忽略求解在用判定樹模型建立問題的時間下界時，通常忽略求解問題的所有算術(shù)運算，只考慮分支執(zhí)行時的轉(zhuǎn)移次數(shù)。問題的所有算術(shù)運算，只考慮分支執(zhí)行時的轉(zhuǎn)移次數(shù)。 第3頁/共33頁a1a2

4、a1a2a3是是是是是是否否否否否否a1a3a2a3a2a1a3a2a3a3a2a1a2a3a1a1a3a3a1a2a1a3a2否否否否是是是是例：對三個數(shù)進(jìn)行排序的判定樹例：對三個數(shù)進(jìn)行排序的判定樹第4頁/共33頁2.1.3 最優(yōu)算法最優(yōu)算法 所謂所謂最優(yōu)算法最優(yōu)算法（Optimality Algorithm）是）是指在某一種度量標(biāo)準(zhǔn)下，優(yōu)于該問題的所有（指在某一種度量標(biāo)準(zhǔn)下，優(yōu)于該問題的所有（可能的）算法。可能的）算法。v 如果能夠證明求解問題如果能夠證明求解問題的任何算法的運行時的任何算法的運行時間下界是間下界是(g(n)，那么，對以時間，那么，對以時間O(g(n)來求解來求解問題問題的

5、任何算法，都認(rèn)為是最優(yōu)算法。的任何算法，都認(rèn)為是最優(yōu)算法。 第5頁/共33頁2.2 算法的極限算法的極限 2.2.1 易解問題與難解問題易解問題與難解問題 2.2.2 實際問題難以求解的原因?qū)嶋H問題難以求解的原因2.2.3 不可解問題不可解問題第6頁/共33頁2.2.1 易解問題與難解問易解問題與難解問題題 通常將存在多項式時間算法的問題看作是通常將存在多項式時間算法的問題看作是易解問易解問題題（Easy Problem），將需要指數(shù)時間算法解決的問），將需要指數(shù)時間算法解決的問題看作是題看作是難解問題難解問題（Hard Problem）。）。例：易解問題例：易解問題排序問題、查找問題、歐拉回

6、路排序問題、查找問題、歐拉回路 難解問題難解問題TSPTSP問題、問題、 HanioHanio問題、問題、HamiltonHamilton回路回路第7頁/共33頁 為什么把多項式時間復(fù)雜性作為易解問題和為什么把多項式時間復(fù)雜性作為易解問題和難解問題的分界線？難解問題的分界線？1多項式函數(shù)與指數(shù)函數(shù)的增長率有本質(zhì)的差別多項式函數(shù)與指數(shù)函數(shù)的增長率有本質(zhì)的差別2計算機性能的提高對多項式時間算法和指數(shù)時間計算機性能的提高對多項式時間算法和指數(shù)時間算法的影響不同算法的影響不同3多項式時間復(fù)雜性忽略了系數(shù)，但不影響易解問多項式時間復(fù)雜性忽略了系數(shù)，但不影響易解問題和難解問題的劃分題和難解問題的劃分4多項

7、式時間復(fù)雜性的閉包性多項式時間復(fù)雜性的閉包性5多項式時間復(fù)雜性的獨立性多項式時間復(fù)雜性的獨立性 第8頁/共33頁2.2.3 不可解問題不可解問題 不能用計算機求解（不能用計算機求解（不論耗費多少時間不論耗費多少時間）的問題）的問題稱為稱為不可解問題不可解問題（Unsoluble Problem）。）。 例：不可解問題例：不可解問題停機問題、病毒檢測停機問題、病毒檢測作業(yè)：證明停機問題是不可解問題。作業(yè)：證明停機問題是不可解問題。第9頁/共33頁2.3 P類問題和類問題和NP類問題類問題 2.3.1 判定問題判定問題 2.3.2 確定性算法與確定性算法與P類問題類問題2.3.3 非確定性算法與非

8、確定性算法與NP類問題類問題第10頁/共33頁2.3.1 判定問題判定問題 一個一個判定問題判定問題（Decision Problem）是僅）是僅僅要求回答僅要求回答“yes”或或“no”的問題。的問題。 判定問題的重要特性判定問題的重要特性證比求易證比求易 判定問題判定問題語言的識別問題語言的識別問題計算模型計算模型第11頁/共33頁2.3.2 確定性算法與確定性算法與P類問題類問題 定義定義2.1 設(shè)設(shè)A是求解問題是求解問題的一個算法，如果在算的一個算法，如果在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇法的整個執(zhí)行過程中，每一步只有一個確定的選擇，則稱算法，則稱算法A是是確定性確定性（

9、Determinism）算法。）算法。定義定義2.2 如果對于某個判定問題如果對于某個判定問題，存在一個非負(fù)，存在一個非負(fù)整數(shù)整數(shù)k，對于輸入規(guī)模為，對于輸入規(guī)模為n的實例，能夠以的實例，能夠以O(shè)(nk)的的時間運行一個確定性算法，得到時間運行一個確定性算法，得到y(tǒng)es或或no的答案，的答案，則該判定問題則該判定問題是一個是一個 P 類類（Polynomial）問題）問題。 v 所有易解問題都是所有易解問題都是P類問題類問題第12頁/共33頁2.3.3 非確定性算法與非確定性算法與NP類問類問題題 定義定義2.3 設(shè)設(shè)A是求解問題是求解問題的一個算法，如果算法的一個算法，如果算法A以如以如下下

10、猜測并驗證猜測并驗證的方式工作，就稱算法的方式工作，就稱算法A是是非確定性非確定性（Nondeterminism）算法：）算法： （1）猜測階段猜測階段：在這個階段，對問題的輸入實例產(chǎn)生一個：在這個階段，對問題的輸入實例產(chǎn)生一個任意字符串任意字符串y，在算法的每一次運行時，串，在算法的每一次運行時，串y的值可能不同，的值可能不同，因此，猜測以一種非確定的形式工作。因此，猜測以一種非確定的形式工作。 （2）驗證階段驗證階段：在這個階段，用一個確定性算法驗證：在這個階段，用一個確定性算法驗證： 檢查在猜測階段產(chǎn)生的串檢查在猜測階段產(chǎn)生的串y是否是合適的形式，如果不是否是合適的形式，如果不是，則算法

11、停下來并得到是，則算法停下來并得到no； 如果串如果串y是合適的形式，則驗證它是否是問題的解，如是合適的形式，則驗證它是否是問題的解，如果是，則算法停下來并得到果是，則算法停下來并得到y(tǒng)es，否則算法停下來并得到，否則算法停下來并得到no。 第13頁/共33頁 定義定義2.4 如果對于某個判定問題如果對于某個判定問題，存在一個，存在一個非負(fù)整數(shù)非負(fù)整數(shù)k，對于輸入規(guī)模為，對于輸入規(guī)模為n的實例，能夠以的實例，能夠以O(shè)(nk)的時間運行一個非確定性算法，得到的時間運行一個非確定性算法，得到y(tǒng)es或或no的答的答案，則該判定問題案，則該判定問題是一個是一個 NP 類類（Nondeterminist

12、ic Polynomial）問題。）問題。 v 關(guān)鍵關(guān)鍵存在一個存在一個確定性算法確定性算法，能夠以，能夠以多項式時間多項式時間來檢來檢查和查和驗證驗證猜測階段所產(chǎn)生的答案。猜測階段所產(chǎn)生的答案。例：例： NP類問題類問題HamiltonHamilton問題問題 漢諾塔問題不是漢諾塔問題不是NP類問題類問題第14頁/共33頁 P類問題和類問題和NP類問題的主要差別：類問題的主要差別： P類問題可以用類問題可以用多項式時間多項式時間的的確定性確定性算法算法來來進(jìn)行判定或求解；進(jìn)行判定或求解； NP類問題可以用類問題可以用多項式時間多項式時間的的非確定性非確定性算算法法來進(jìn)行判定或求解。來進(jìn)行判定

13、或求解。 第15頁/共33頁2.4 NP完全問題完全問題 2.4.1 問題變換與計算復(fù)雜性歸約問題變換與計算復(fù)雜性歸約 2.4.2 NP完全問題的定義完全問題的定義2.4.3 基本的基本的NP完全問題完全問題2.4.4 NP完全問題的計算機處理完全問題的計算機處理第16頁/共33頁2.4.1 問題變換與計算復(fù)雜性歸約問題變換與計算復(fù)雜性歸約 定義定義 2.5 假設(shè)問題假設(shè)問題存在一個算法存在一個算法A，對于問題，對于問題的輸入實例的輸入實例I，算法，算法A求解問題求解問題得到一個輸出得到一個輸出O，另外，另外一個問題一個問題的輸入實例是的輸入實例是I，對應(yīng)于輸入，對應(yīng)于輸入I，問題，問題有一個

14、有一個輸出輸出O，則問題，則問題變換變換到問題到問題是一個三步的過程：是一個三步的過程： 1. 輸入轉(zhuǎn)換：把問題輸入轉(zhuǎn)換：把問題的輸入的輸入I轉(zhuǎn)換為問題轉(zhuǎn)換為問題的適當(dāng)輸?shù)倪m當(dāng)輸入入I； 2. 問題求解：對問題問題求解：對問題應(yīng)用算法應(yīng)用算法A產(chǎn)生一個輸出產(chǎn)生一個輸出O ； 3. .輸出轉(zhuǎn)換：把問題輸出轉(zhuǎn)換：把問題的輸出的輸出O轉(zhuǎn)換為問題轉(zhuǎn)換為問題對應(yīng)對應(yīng)于輸入于輸入I的正確輸出。的正確輸出。 第17頁/共33頁 問題變換的一般過程問題變換的一般過程問題問題問題問題 算法算法AI 輸入轉(zhuǎn)換輸入轉(zhuǎn)換IOO 輸出轉(zhuǎn)換輸出轉(zhuǎn)換v問題變換的主要目的不是給出解決一個問題的問題變換的主要目的不是給出解決一

15、個問題的算法，而是給出通過另一個問題算法，而是給出通過另一個問題理解理解一個問題的一個問題的計算時間上下限計算時間上下限的一種方式。的一種方式。第18頁/共33頁排序問題排序問題輸入輸入I是一組整數(shù)是一組整數(shù)X=(x1, x2, , xn)，輸出輸出O是這組整數(shù)的一個排列是這組整數(shù)的一個排列xi1xi2xin。配對問題配對問題輸入輸入I是兩組整數(shù)是兩組整數(shù)X=(x1, x2, , xn)和和Y=(y1, y2, , yn)，輸出，輸出O是兩組整數(shù)的元素配對，是兩組整數(shù)的元素配對，即即X中的最小值與中的最小值與Y中的最小值配對，中的最小值配對，X中的次小中的次小值與值與Y中的次小值配對，依此類推

16、。中的次小值配對，依此類推。 例：配對問題到排序問題的變換例：配對問題到排序問題的變換第19頁/共33頁 v 配對問題到排序問題的變換有助于建立配對問題代價的配對問題到排序問題的變換有助于建立配對問題代價的一個上限，因為上述輸入和輸出轉(zhuǎn)換都是在多項式時間完成一個上限，因為上述輸入和輸出轉(zhuǎn)換都是在多項式時間完成，所以，如果排序問題有多項式時間算法，則配對問題也一，所以，如果排序問題有多項式時間算法，則配對問題也一定有多項式時間算法。定有多項式時間算法。 假設(shè)存在算法假設(shè)存在算法A解決排序問題，則解決排序問題，則配對問題可以變換到排序問題：配對問題可以變換到排序問題：1把配對問題的輸入把配對問題的

17、輸入I轉(zhuǎn)化為排序問題的兩個輸入轉(zhuǎn)化為排序問題的兩個輸入I1和和I2；2排序這兩組整數(shù)，即應(yīng)用算法排序這兩組整數(shù)，即應(yīng)用算法A對兩個輸入對兩個輸入I1和和I2分別排序得到分別排序得到兩個有序序列兩個有序序列O1 和和O2 ； 3把排序問題的輸出把排序問題的輸出O1和和O2轉(zhuǎn)化為配對問題的輸出轉(zhuǎn)化為配對問題的輸出O，這可以，這可以通過配對每組整數(shù)的第一個元素、第二個元素、通過配對每組整數(shù)的第一個元素、第二個元素、來得到。來得到。 配對問題到排序問題的變換過程配對問題到排序問題的變換過程第20頁/共33頁 定理（計算時間下限歸約）若已知問題定理（計算時間下限歸約）若已知問題的計算時間下的計算時間下限

18、是限是T(n)，且問題，且問題可可(n)變換到問題變換到問題，即，即(n)，則，則T(n)O(n)為問題為問題的一個計算時間下限。的一個計算時間下限。 定理（計算時間上限歸約）定理（計算時間上限歸約） 若已知問題若已知問題的計算時間上的計算時間上限是限是T(n)，且問題，且問題可可(n)變換到問題變換到問題，即，即(n)，則，則T(n)O(n)為問題為問題的一個計算時間上限。的一個計算時間上限。 計算時間下限歸約：計算時間下限歸約： T(n) (n) T(n)O(n)計算時間上限歸約：計算時間上限歸約：T(n)O(n) (n) T(n)問題問題 變換變換問題問題第21頁/共33頁 定理定理2.

19、5 設(shè)設(shè)、和和是三個判定問題，若是三個判定問題，若p且且p，則，則p。 v 多項式時間復(fù)雜性具有閉包性。多項式時間復(fù)雜性具有閉包性。第22頁/共33頁2.4.2 NP完全問題的定義完全問題的定義 定義定義2.6 令令是一個判定問題，如果問題是一個判定問題，如果問題屬于屬于NP類問題，并且對類問題，并且對NP類問題中的每一個問類問題中的每一個問題題，都有，都有p，則稱判定問題，則稱判定問題是一個是一個NP完全問題完全問題（NP Complete Problem），有時），有時把把NP完全問題記為完全問題記為NPC。 NP類問題NP完全問題第23頁/共33頁P PNPNP？ 廣義上說，廣義上說，P

20、類問題是可以用確定性算法在多項式時間內(nèi)類問題是可以用確定性算法在多項式時間內(nèi)求解的一類問題，求解的一類問題，NP類問題是可以用非確定性算法在多類問題是可以用非確定性算法在多項式時間猜測并驗證的一類問題，而且項式時間猜測并驗證的一類問題，而且P PNPNP。 目前人們猜測目前人們猜測PNP，則，則P類問題、類問題、NP類問題、類問題、NP完全問完全問題之間的關(guān)系如下：題之間的關(guān)系如下： NP類問題 P類問題 NPC問題第24頁/共33頁 定義定義2.7 令令是一個判定問題，如果對于是一個判定問題，如果對于NP類類問題中的每一個問題問題中的每一個問題，都有，都有p，則稱判定，則稱判定問題問題是一個

21、是一個NP難難問題。問題。 NP類問題NP難問題第25頁/共33頁 如果如果是是NP完全問題，完全問題，是是NP難問題，那么，難問題，那么，他們之間的差別在于他們之間的差別在于必定是必定是NP類問題，而類問題，而不一不一定在定在NP類問題中。類問題中。 v 一般而言，若判定問題屬于一般而言，若判定問題屬于NP完全問題，則相應(yīng)完全問題，則相應(yīng)的最優(yōu)化問題屬于的最優(yōu)化問題屬于NP難問題。難問題。 NP完全問題和完全問題和NP難問題的區(qū)別：難問題的區(qū)別：第26頁/共33頁2.4.3 基本的基本的NP完全問題完全問題 證明一個判定問題證明一個判定問題是是NP完全問題需要經(jīng)過兩步：完全問題需要經(jīng)過兩步：

22、 （1）證明問題）證明問題屬于屬于NP類問題，也就是說，可以在多類問題，也就是說，可以在多項式時間以確定性算法驗證一個任意生成的串，以確定它項式時間以確定性算法驗證一個任意生成的串，以確定它是不是問題的一個解；是不是問題的一個解； （2）證明）證明NP類問題中的每一個問題都能在多項式時間類問題中的每一個問題都能在多項式時間變換為問題變換為問題。由于多項式問題變換具有傳遞性，所以，。由于多項式問題變換具有傳遞性，所以，只需證明一個已知的只需證明一個已知的NP完全問題能夠在多項式時間變換完全問題能夠在多項式時間變換為問題為問題。 第27頁/共33頁NP完全問題的證明思想完全問題的證明思想NP類問題已知的NP完全問題要證明的NP完全問題第28頁/共33頁一些基本的一些基本的NP完全問題：完全問題：1SAT問題（問題（Boolean Satisfiability Problem） 2最大團(tuán)問題最大團(tuán)問題（Maximum Clique Problem） 3圖著色問題圖著色問題（Graph Coloring Problem） 4. 哈密頓回路問題哈密頓回路問題（Hamiltonian Cycle Problem）5TSP問題問題（Traveling Salsman P