《高級算法設(shè)計》課件 第3、4章 NP問題；近似算法

高級算法設(shè)計與分析NP問題主要內(nèi)容基本概念、歸約P問題的證明NPC問題的證明算法效率多項式時間算法O(nc)forsomeconstantc非多項式時間算法復(fù)雜度為O(n)的算法是高效率?復(fù)雜度為O(nlogn)?O(n2)?O(n10)?O(nlogn)?O(2n)?O(n!)?基本概念：P問題基本概念：NP問題基本概念：NPC問題基本概念：關(guān)系P問題，NP問題和NP完全問題的關(guān)系（認為，沒有得到證實）基本概念：NPC問題判斷是否NP問題也就是給出一個證書，可否在多項式時間內(nèi)判斷它是否是原問題的一個解最優(yōu)化問題需要轉(zhuǎn)化為判斷性問題基本概念：NPC問題旅行商問題轉(zhuǎn)化為：此圖中是否存在總權(quán)重為1的回路?此圖中是否存在總權(quán)重為2的回路?…此圖中是否存在總權(quán)重為n的回路?一個優(yōu)化問題可分解為多個判定性問題如果能夠證明一個判定性問題為NP難時，顯然原問題也是NP難的基本概念：歸約性通俗的講，一個問題(如Q1)可以規(guī)約為另外一個問題(如Q2)是指問題Q1可以轉(zhuǎn)換為問題Q2，之后可以通過求解Q2的方法來求解Q1如:求解一元一次方程(問題Q1)可歸為求解一元二次方程(問題Q2):一元二次方程的二次項系數(shù)為0即可，之后可以通過求解一元二次方程的方法來求解一元一次方程基本概念：歸約基本概念：歸約歸約具有傳遞性如果問題A可歸約為問題B，問題B可歸約為問題C，則問題A一定可歸約為問題C?；靖拍睿簹w約證明基本概念：歸約性主要內(nèi)容基本概念、歸約P問題的證明NPC問題的證明P問題的證明2合取范式(CNF)的可滿足性問題(SAT)P問題的證明2合取范式(CNF)到圖的轉(zhuǎn)換

P問題的證明2合取范式(CNF)到圖的轉(zhuǎn)換

P問題的證明2合取范式(CNF)到圖的轉(zhuǎn)換當(dāng)且僅當(dāng)2CNF中存在子句(x∨y)，圖G中存在邊?x→y

(和邊?y→x)P問題的證明P問題的證明P問題的證明P問題的證明P問題的證明主要內(nèi)容基本概念、歸約P問題的證明NPC問題的證明NPC問題的證明第一個NPC問題電路可滿足性問題問題：給定一個邏輯電路，問是否存在一種輸入使輸出為True其它的NPC問題都是由這個問題歸約而來的。因此，邏輯電路問題是NPC類問題的“鼻祖”。有了第一個NPC問題后，一大堆NPC問題就出現(xiàn)了，因為再證明一個新的NPC問題只需要將一個已知的NPC問題歸約到它就行了公式可滿足性問題公式可滿足性問題:公式可滿足性問題公式可滿足性證明這是一個NP問題公式可滿足性問題公式可滿足性證明歸約證明：電路可滿足性歸約到公式可滿足性顯而易見，每個電路都可寫成一個布爾公式也就是存在f，使得任何一個實例x屬于電路，當(dāng)且僅當(dāng)f(x)屬于公式但，直接寫的話，因每個電路門輸出線扇出為2或者2以上導(dǎo)致布爾公式的規(guī)模出現(xiàn)指數(shù)增長公式可滿足性問題公式可滿足性證明我們的目的不是將電路轉(zhuǎn)換為布爾公式，而是證明可滿足性，如果電路有可滿足指派，則電路每個門輸出都由其輸入決定，寫成表達式如右x7公式可滿足性問題公式可滿足性證明以上轉(zhuǎn)換為多項式時間如果電路有可滿足性實例，則電路輸出為1，而公式輸出也為1如果公式輸出為1，則顯然電路輸出也為1公式可滿足性為NPC問題3-CNF可滿足性問題每個子句有3個文字3-CNF可滿足性問題公式可滿足性證明這是一個NP問題公式可滿足性可以歸約到3-CNF將布爾公式轉(zhuǎn)換為子句的合取式將子句轉(zhuǎn)換為合取范式將子句轉(zhuǎn)為3個文字的合取取式3-CNF可滿足性問題1.將布爾公式轉(zhuǎn)換為子句的合取式建立布爾公式的語法樹3-CNF可滿足性問題1.將布爾公式轉(zhuǎn)換為子句的合取式建立布爾公式的語法樹將語法分析樹看成電路，得出歸約的布爾公式此布爾公式為合取式3-CNF可滿足性問題2.將子句轉(zhuǎn)換為合取范式構(gòu)造每個子句的真值表3-CNF可滿足性問題2.將子句轉(zhuǎn)換為合取范式構(gòu)造每個子句的真值表根據(jù)真值表中值為0的項，得出析取范式此析取范式等價于子句的否3-CNF可滿足性問題2.將子句轉(zhuǎn)換為合取范式構(gòu)造每個子句的真值表根據(jù)真值表中值為0的項，得出析取范式此析取范式等價于子句的否運用德摩根定律，得出合取子句（將析取范式再取否）3-CNF可滿足性問題3.將子句轉(zhuǎn)為3個文字的合取取式3-CNF可滿足性問題以上映射為多項式時間將布爾公式轉(zhuǎn)換為子句的合取式同布爾電路轉(zhuǎn)換為布爾公式將子句轉(zhuǎn)換為合取范式每個子句至多變?yōu)?個子句（至多3個變量）將子句轉(zhuǎn)為3個文字的合取取式至多引入4個子句由以上步驟可知：3-CNF是可滿足的當(dāng)且僅當(dāng)以上三個步驟的每一步都是可滿足的=》以上轉(zhuǎn)換為歸約團問題團問題團問題證明這是一個NP問題團問題3合取范式可以歸約為團問題構(gòu)造圖一個子句對應(yīng)一組頂點對于任意兩個在不同組的頂點，如果滿足“這兩個頂點不是‘否’的關(guān)系”這一條件，就用一條邊連接團問題是一組可滿足賦值，其對應(yīng)圖中的灰色團團問題團問題還有一個疑問：歸約為一個特殊的圖，能說明一般圖的團問題也是NP完全的嗎？頂點覆蓋問題頂點覆蓋問題頂點覆蓋問題證明這是一個NP問題頂點覆蓋問題頂點覆蓋問題頂點覆蓋問題頂點覆蓋問題哈密頓回路哈密頓回路哈密頓回路證明哈密頓回路哈密頓回路哈密頓回路可以這樣定義附件圖嗎？哈密頓回路用附件圖替換哈密頓回路用附件圖替換哈密頓回路多項式轉(zhuǎn)換哈密頓回路以上過程是一種歸約哈密頓回路以上過程是一種歸約高級算法設(shè)計與分析近似算法目錄概述旅行商問題子集和問題集合覆蓋-整數(shù)規(guī)劃斯坦納最小樹概述NPC問題該如何求解?如果規(guī)模很小，用指數(shù)運行時間算法對一些特殊的情況，如果有多項式時間可以解決，則設(shè)計多項式算法對用一般情況，則通過多項式時間的近似解法概述近似解的精確度C：某一算法解的代價C*：最優(yōu)解的代價如果一個解達到此因子，則稱算法C為ρ(n)近似算法概述近似模式：對于一個輸入為n的實例，通常近似算法的因子為（1+ε）算法時間除了和n相關(guān)，和ε也相關(guān)如果對于任意一個ε>0，該算法都可以在輸入規(guī)模為n的多項式時間內(nèi)完成，稱此模式為多項式時間近似模式顯然此種模式下，當(dāng)ε趨近于0時，算法逼近最優(yōu)值，但可能算法的復(fù)雜度急劇增加，如時間復(fù)雜度為多項式時間近似模式中一種更好的模式稱為完全多項式時間近似模式，其復(fù)雜度為：這種模式當(dāng)ε減少時，運行時間不會指數(shù)增長，而是多項式增長旅行商問題旅行商問題為NPC問題定義：對于完全無向圖G=（V，E），設(shè)c(A)為子集A的總代價三角不等式：旅行商問題滿足三角不等式的旅行商問題生成最小生成樹按對樹進行先序的順序訪問節(jié)點上述算法中，生成最下生成樹可以用Kruskal算法或者Prim算法，復(fù)雜度都為O(mlogn)。先序遍歷的復(fù)雜度為O(n)，所以旅行商問題的近似算法復(fù)雜度為O(mlogn)

旅行商問題旅行商問題最優(yōu)旅行線路（H*）的總代價的下限為最小生成樹（T）邊的總代價對T進行按先序往返（返回時會再次遍歷節(jié)點）遍歷（W），W剛好對所有的邊遍歷兩次旅行商問題一般旅行商問題三角不等式不成立的條件下，ρ近似的旅行商問題是一個NPC問題，則定理自然成立旅行商問題如果圖G存在一條哈密頓回路H，則G′必然存在一條代價為n的旅行商回路TSP(同H),此回路為ρ近似旅行商回路如果圖G′存在一條ρ近似的旅行商回路TSPρ，則圖G必然存在一條哈密頓回路H

子集和問題準確算法（指數(shù)時間復(fù)雜度）:得出集合S的所有子集，并計算所有子集的和優(yōu)化在第i-1輪迭代中，計算(e1,e2,…,ei-1)所有的子集和在第i輪迭代中，計算(e1,

e2,…,ei)在相加的過程中，一旦子集和超過t，舍棄子集和問題子集和問題去除相近的元素：x可以被y代替例子子集和問題子集和問題子集和問題子集和問題子集和問題按這兩種不同的情況討論子集和問題子集和問題子集和問題所以：子集和問題子集和問題Ln必然包含0元素，可能包含1元素集合覆蓋問題簡單集合覆蓋

集合覆蓋問題：例子集合覆蓋問題貪心算法集合覆蓋問題算法第i次選擇了子集Si加入到頂點覆蓋集R，則其總代價+1在選取第i個子集Si時，假設(shè)ni個元素被Si首次覆蓋，其中每個元素分配到的代價為：集合覆蓋問題集合覆蓋問題當(dāng)近似算法選擇了i個子集后，子集S中未被覆蓋的元素的個數(shù)集合覆蓋問題集合覆蓋問題集合覆蓋問題集合覆蓋-整數(shù)規(guī)劃帶權(quán)重的集合覆蓋：覆蓋所有的元素，其權(quán)重總和最小設(shè)E={1,2,3,4,5,6,7,8}子集有:S1={1,2,3}w1=1S2={2,7,8}w2=2S3={4,5,6,7}w3=3S4={4,5,6,8}w4=4解:C={S1,S2,S3},C={S1,S2,S4}最優(yōu)解：C={S1,S2,S3}集合覆蓋-整數(shù)規(guī)劃松弛集合覆蓋-整數(shù)規(guī)劃算法元素的最大頻率f：設(shè)g表示包含某一元素的子集個數(shù)，則最大的g即元素的最大頻率f在所有的LP最優(yōu)解的子集中，選取xi（每個子集通過LP求解得出的值）的值大于1/f的子集作為IP的解集合覆蓋-整數(shù)規(guī)劃證明1：以上選取的子集包含了E中所有的元素集合覆蓋-整數(shù)規(guī)劃集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法集合覆蓋-原始-對偶算法斯坦納最小樹斯坦納最小樹用最小生成樹來近似斯坦納樹？斯坦納最小樹斯坦納最小樹：例子GRTMTGMTTST斯坦納最小樹：例子算法基于原圖G，生成R的一個完全圖GR，其中任意一條邊的權(quán)重為原圖G中的最短路徑基于GR，生成最小生成樹TMT

將TMT

中的邊替換成原來的最短路徑，得到圖GMT