算法設(shè)計(jì)與分析王紅梅NP完全理論P(yáng)PT學(xué)習(xí)教案

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

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

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

4、a1a2a3是是是是是是否否否否否否a1a3a2a3a2a1a3a2a3a3a2a1a2a3a1a1a3a3a1a2a1a3a2否否否否是是是是例：對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹例：對(duì)三個(gè)數(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)于該問題的所有（可能的）算法?？赡艿模┧惴ā 如果能夠證明求解問題如果能夠證明求解問題的任何算法的運(yùn)行時(shí)的任何算法的運(yùn)行時(shí)間下界是間下界是(g(n)，那么，對(duì)以時(shí)間，那么，對(duì)以時(shí)間O(g(n)來求解來求解問題問題的

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

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

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

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

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

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

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

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

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

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

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

16、。中的次小值配對(duì)，依此類推。 例：配對(duì)問題到排序問題的變換例：配對(duì)問題到排序問題的變換第19頁/共33頁 v 配對(duì)問題到排序問題的變換有助于建立配對(duì)問題代價(jià)的配對(duì)問題到排序問題的變換有助于建立配對(duì)問題代價(jià)的一個(gè)上限，因?yàn)樯鲜鲚斎牒洼敵鲛D(zhuǎn)換都是在多項(xiàng)式時(shí)間完成一個(gè)上限，因?yàn)樯鲜鲚斎牒洼敵鲛D(zhuǎn)換都是在多項(xiàng)式時(shí)間完成，所以，如果排序問題有多項(xiàng)式時(shí)間算法，則配對(duì)問題也一，所以，如果排序問題有多項(xiàng)式時(shí)間算法，則配對(duì)問題也一定有多項(xiàng)式時(shí)間算法。定有多項(xiàng)式時(shí)間算法。 假設(shè)存在算法假設(shè)存在算法A解決排序問題，則解決排序問題，則配對(duì)問題可以變換到排序問題：配對(duì)問題可以變換到排序問題：1把配對(duì)問題的輸入把配對(duì)問題的

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

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

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

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

21、是一個(gè)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完全問題完全問題 證明一個(gè)判定問題證明一個(gè)判定問題是是NP完全問題需要經(jīng)過兩步：完全問題需要經(jīng)過兩步：

22、 （1）證明問題）證明問題屬于屬于NP類問題，也就是說，可以在多類問題，也就是說，可以在多項(xiàng)式時(shí)間以確定性算法驗(yàn)證一個(gè)任意生成的串，以確定它項(xiàng)式時(shí)間以確定性算法驗(yàn)證一個(gè)任意生成的串，以確定它是不是問題的一個(gè)解；是不是問題的一個(gè)解； （2）證明）證明NP類問題中的每一個(gè)問題都能在多項(xiàng)式時(shí)間類問題中的每一個(gè)問題都能在多項(xiàng)式時(shí)間變換為問題變換為問題。由于多項(xiàng)式問題變換具有傳遞性，所以，。由于多項(xiàng)式問題變換具有傳遞性，所以，只需證明一個(gè)已知的只需證明一個(gè)已知的NP完全問題能夠在多項(xiàng)式時(shí)間變換完全問題能夠在多項(xiàng)式時(shí)間變換為問題為問題。 第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