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

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

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

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

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

集合覆蓋問題：例子集合覆蓋問題貪心算法集合覆蓋問題算法第i次選擇了子集Si加入到頂點(diǎn)覆蓋集R，則其總代價(jià)+1在選取第i個(gè)子集Si時(shí)，假設(shè)ni個(gè)元素被Si首次覆蓋，其中每個(gè)元素分配到的代價(jià)為：集合覆蓋問題集合覆蓋問題當(dāng)近似算法選擇了i個(gè)子集后，子集S中未被覆蓋的元素的個(gè)數(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表示包含某一元素的子集個(gè)數(shù)，則最大的g即元素的最大頻率f在所有的LP最優(yōu)解的子集中，選取xi（每個(gè)子集通過LP求解得出的值）的值大于1/f的子集作為IP的解集合覆蓋-整數(shù)規(guī)劃證明1：以上選取的子集包含了E中所有的元素集合覆蓋-整數(shù)規(guī)劃集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法集合覆蓋-原始-對(duì)偶算法斯坦納最小樹斯坦納最小樹用最小生成樹來近似斯坦納樹？斯坦納最小樹斯坦納最小樹：例子GRTMTGMTTST斯坦納最小樹：例子算法基于原圖G，生成R的一個(gè)完全圖GR，其中任意一條邊的權(quán)重為原圖G中的最短路徑基于GR，生成最小生成樹TMT

將TMT

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