中科大算法第二章近似算法--黃劉生(調(diào)整后適合打印版)

1、近似算法近似算法 黃劉生黃劉生目錄目錄Part1 NP-Part1 NP-完全性理論完全性理論P(yáng)art2 Part2 近似算法近似算法3 | Presentation Title | Month 2010NP-NP-完全性理論完全性理論14 計(jì)算機(jī)科學(xué)的局限性計(jì)算機(jī)科學(xué)的局限性n 可解性可解性：?jiǎn)栴}及其可解性可用函數(shù)和可計(jì)算性來(lái)代替n 可計(jì)算性理論可計(jì)算性理論：研究計(jì)算的一般性質(zhì)的數(shù)學(xué)理論，它通過(guò)建立計(jì)算的數(shù)學(xué)模型（例如抽象計(jì)算機(jī)），精確區(qū)分哪些是可計(jì)算的，哪些是不可計(jì)算的。n 可計(jì)算函數(shù)可計(jì)算函數(shù)：能夠在抽象計(jì)算機(jī)上編出程序計(jì)算其值的函數(shù)。這樣就可以討論哪些函數(shù)是可計(jì)算的，哪些函數(shù)是不可計(jì)算

2、的。n Church-TuringChurch-Turing論題論題：若一函數(shù)在某個(gè)合理的計(jì)算模型上可計(jì)算，則它在圖靈機(jī)上也是可計(jì)算的。n 不可計(jì)算性不可計(jì)算性：很多問(wèn)題和函數(shù)是無(wú)法用具有有窮描述的過(guò)程完成計(jì)算5 停機(jī)問(wèn)題停機(jī)問(wèn)題n 停機(jī)問(wèn)題停機(jī)問(wèn)題：能否寫(xiě)一個(gè)程序正確判定輸入給它的任何一個(gè)程序是否會(huì)停機(jī)？ 設(shè)程序halts(P,X)總是正確地判定程序P在其輸入X上是否停機(jī):若停機(jī)，則返回yes；否則死循環(huán)，返回no。設(shè)另有一程序: diagonal(Y) a: if halts(Y,Y) then goto a; else halt; diagonal（diagonal）是否停機(jī)？ 不可判定

3、 它停機(jī)當(dāng)且僅當(dāng)halts(diagonal,diagonal)返回否，也就是： diagonal停機(jī)當(dāng)且僅當(dāng)它自己不停機(jī)，矛盾！ 即：halts(P,X)并不存在，停機(jī)問(wèn)題是不可解的！ 功能：若halts斷定當(dāng)程序Y用其自身Y作為輸入時(shí)Y停機(jī),則diagonal(Y)死循環(huán)；否則它停機(jī)6 圖靈機(jī)圖靈機(jī) 依據(jù)控制器的狀態(tài)和讀寫(xiě)頭所讀字符，決定執(zhí)行以下3個(gè)操作之一、之二或全部： 1）改變有限狀態(tài)控制器中的狀態(tài)； 2）讀寫(xiě)頭在相應(yīng)的方格中寫(xiě)一符號(hào)； 3）讀寫(xiě)頭左、右移一格或不動(dòng)。n 確定型圖靈機(jī)確定型圖靈機(jī)DTMDTM：若對(duì)任一個(gè)狀態(tài)和符號(hào)，要執(zhí)行的動(dòng)作都是唯一的n 非確定型圖靈機(jī)非確定型圖靈機(jī)N

4、TMNTM：若執(zhí)行的動(dòng)作是有窮多個(gè)可供選擇 有單帶、多帶等變有單帶、多帶等變種，計(jì)算能力等價(jià)種，計(jì)算能力等價(jià) 有限狀態(tài)控制器有限狀態(tài)控制器輸入帶輸入帶 無(wú)限長(zhǎng)無(wú)限長(zhǎng) 讀寫(xiě)頭讀寫(xiě)頭7 P、NP及NPC類(lèi)問(wèn)題n P類(lèi)問(wèn)題：類(lèi)問(wèn)題：一類(lèi)問(wèn)題的集合，對(duì)其中的任一問(wèn)題，都存在一個(gè)確定確定型圖靈機(jī)M和一個(gè)多項(xiàng)式p，對(duì)于該問(wèn)題的任何（編碼）長(zhǎng)度為n的實(shí)例，M都能在p(n)步內(nèi)，給出對(duì)該實(shí)例的回答。即：多項(xiàng)式時(shí)間內(nèi)可解的問(wèn)題n NP類(lèi)問(wèn)題：類(lèi)問(wèn)題：一類(lèi)問(wèn)題的集合，對(duì)其中的任一問(wèn)題，都存在一個(gè)非確定非確定型圖靈機(jī)M和一個(gè)多項(xiàng)式p，對(duì)于該問(wèn)題的任何（編碼）長(zhǎng)度為n的實(shí)例，M都能在p(n)步內(nèi)，給出對(duì)該實(shí)例的回答。

5、 若NTM在每一步都恰有2步可供選擇，則回答實(shí)例需考察2p(n)種不同的可能性。 存在多項(xiàng)式時(shí)間的算法嗎？ 多項(xiàng)式時(shí)間內(nèi)可驗(yàn)證問(wèn)題（指驗(yàn)證其解的正確性）8 P、NP及及NPC類(lèi)問(wèn)題類(lèi)問(wèn)題n 多一歸約多一歸約 假設(shè)L1和L2是兩個(gè)判定問(wèn)題，f將L1的每個(gè)實(shí)例I變換成L2的實(shí)例f(I)。若對(duì)L1的每個(gè)實(shí)例I，I的答案為“是”當(dāng)且僅當(dāng)f(I)是L2的答案為“是”的實(shí)例，則稱(chēng)f是從L1到L2的多一歸約，記作： L1mL2（傳遞關(guān)系）（傳遞關(guān)系） 直觀意義：將求解L1的問(wèn)題轉(zhuǎn)換為求解L2的問(wèn)題，而問(wèn)題L1不會(huì)難于L2n 多項(xiàng)式時(shí)間多一歸約多項(xiàng)式時(shí)間多一歸約：若f是多項(xiàng)式時(shí)間可計(jì)算，則上述歸約稱(chēng)為多項(xiàng)式時(shí)

6、間多一歸約，也稱(chēng)多項(xiàng)式時(shí)間變換。記作： pLLm129 P、NP及及NPC類(lèi)問(wèn)題類(lèi)問(wèn)題n NPC問(wèn)題：?jiǎn)栴}：對(duì)于一個(gè)(判定性)問(wèn)題q，若 (1)qNP (2)NP中任一問(wèn)題均可多項(xiàng)式時(shí)間多一歸約到q 則稱(chēng)問(wèn)題q為NP-完全的(NP-complete，NPC)n NP-hard問(wèn)題問(wèn)題：若問(wèn)題q僅滿足條件(2)而不一定滿足條件(1)，則問(wèn)題q稱(chēng)為NP-難的(NP-hard，NPH)。顯然：NPCNP-hardn NPC和和NP-hard關(guān)系關(guān)系 NP-hard問(wèn)題至少跟NPC問(wèn)題一樣難。 NPC問(wèn)題肯定是NP-hard的，但反之不一定 例：停機(jī)問(wèn)題是NP-hard而非NPC的。 該問(wèn)題不可判定，

7、即無(wú)任何算法(無(wú)論何復(fù)雜度)求解該問(wèn)題 該問(wèn)題 NP。但是 可滿足問(wèn)題SATp停機(jī)問(wèn)題10 P、NP及及NPC類(lèi)問(wèn)題類(lèi)問(wèn)題n NP=？P 確定型圖靈機(jī)是非確定型圖靈機(jī)的特例，PNP 是否有NPP？即是否NP=P？ 美國(guó)麻省的Clay數(shù)學(xué)研究所于2000年5月24日在巴黎法蘭西學(xué)院宣布：對(duì)七個(gè)“千年數(shù)學(xué)難題千年數(shù)學(xué)難題”中的每一個(gè)均懸賞100萬(wàn)美元，而問(wèn)題NP=？P位列其首:1.P問(wèn)題對(duì)問(wèn)題對(duì)NP問(wèn)題問(wèn)題 2.霍奇猜想3.龐加萊猜想(2002.11-2003.7，俄羅斯數(shù)學(xué)家佩雷爾曼在3篇論文預(yù)印本中證明了幾何化猜想，2006被授予菲爾茲獎(jiǎng))4.黎曼假設(shè)5.楊米爾斯存在性和質(zhì)量缺口6.納維葉斯托

8、克斯方程的存在性與光滑性7.貝赫和斯維訥通戴爾猜想11 P、NP及及NPC類(lèi)問(wèn)題類(lèi)問(wèn)題n P、NP、NPC和和NP-hard之關(guān)系之關(guān)系 NPC是NP中最難的問(wèn)題，但是NP-hard至少與NPC一樣難 n 如何證明問(wèn)題如何證明問(wèn)題q是是NP-hard或是或是NPC的？的？ 若已知q NPC或q NPH，且qpq，則q NPH；若進(jìn)一步有q NP，則q NPC。 即：要證q是NPH的，只要找到1個(gè)已知的NPC或NPH問(wèn)題q，然后將q多項(xiàng)式歸約到q即可。若還能驗(yàn)證q NP，則q是NPC的。 NP中任意問(wèn)題均可多項(xiàng)式歸約到q，由于p有傳遞性 他們也都能多項(xiàng)式歸約到q，由定義可知q是NPH的12 NP

9、-NP-完全性理論完全性理論n Cook的貢獻(xiàn)：第一個(gè)NPC問(wèn)題 史提芬?guī)炜?Stephen Arthur Cook，1939)NP完全 性 理 論 的 奠 基 人 ， 他 在 1 9 7 1 年 論 文 ” T h e Complexity of Theorem Proving Procedures”中，給出了第一個(gè)NP完備的證明，即CookCook定理定理： 可滿足性問(wèn)題（Satisfiablity problem) 是NP完全問(wèn)題，亦即 SATSATNPCNPC。且證明了： SATSATP P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P=NPP=NP Cook于1961年獲Michigan大學(xué)學(xué)士學(xué)位，1962和

10、1966年分獲哈佛大學(xué)碩士與博士學(xué)位。1966-1970，他在UC Berkeley擔(dān)任助教授；1970年加盟多倫多大學(xué)，現(xiàn)為該校CS和數(shù)學(xué)系教授，他的論文開(kāi)啟了NP完備性的研究，令該領(lǐng)域于之后的十年成為計(jì)算機(jī)科學(xué)中最活躍和重要的研究。因其在計(jì)算復(fù)雜性理論方面的貢獻(xiàn)，尤其是在奠定NP完全性理論基礎(chǔ)上的突出貢獻(xiàn)而榮獲1982年度的圖靈獎(jiǎng)。13 NP-NP-完全性理論完全性理論n KarpKarp的貢獻(xiàn)的貢獻(xiàn) 理查德卡普（Richard Karp，1935-）1972年論文”Reducibility among Combinatorial Problems”發(fā)展和加強(qiáng)了由庫(kù)克提出的“NP完全性”理

11、論。 尤其是庫(kù) 克僅證明了命題演算的可滿足問(wèn)題是NP完全的，而卡普則證明了從組合優(yōu)化中引出的大多數(shù)經(jīng)典問(wèn)題大多數(shù)經(jīng)典問(wèn)題(背包問(wèn)題、覆蓋問(wèn)題、匹配問(wèn)題、分區(qū)問(wèn)題、路徑問(wèn)題、調(diào)度問(wèn)題等)都是都是NPNP完全問(wèn)題完全問(wèn)題。只要證明其中任一個(gè)問(wèn)題是屬于P類(lèi)的，就可解決計(jì)算復(fù)雜性理論中最大的一個(gè)難題，即P=?NP。 Karp于1955、1956和1959年分別獲哈佛大學(xué)文學(xué)學(xué)士、理學(xué)碩士和應(yīng)用數(shù)學(xué)博士學(xué)位，現(xiàn)任UC Berkeley計(jì)算機(jī)科學(xué)講座教授，美國(guó)科學(xué)院、美國(guó)工程院、美國(guó)藝術(shù)與科學(xué)院、歐洲科學(xué)院院士。因其在計(jì)算機(jī)科學(xué)領(lǐng)域的基礎(chǔ)貢獻(xiàn)曾獲圖靈獎(jiǎng)(1985)、馮諾依曼獎(jiǎng)、美國(guó)國(guó)家科學(xué)勛章、哈佛大學(xué)百

12、年獎(jiǎng)?wù)碌泉?jiǎng)項(xiàng).14 NP-NP-完全性理論完全性理論n NP-NP-完全性理論的局限性完全性理論的局限性 易解問(wèn)題：可多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題 難解問(wèn)題：需超多項(xiàng)式時(shí)間求解的問(wèn)題 NP-完全性理論既沒(méi)有找到第二類(lèi)問(wèn)題的多項(xiàng)式時(shí)間的算法，也沒(méi)有證明這樣的算法就不存在，而是證明了這類(lèi)問(wèn)題計(jì)算難度之等價(jià)性（彼此間困難程度相當(dāng)）。因此，NPC具有如下性質(zhì)：若若其中其中1 1個(gè)問(wèn)題多項(xiàng)式可解當(dāng)且僅當(dāng)其他所有個(gè)問(wèn)題多項(xiàng)式可解當(dāng)且僅當(dāng)其他所有NPCNPC問(wèn)題亦多項(xiàng)式可解問(wèn)題亦多項(xiàng)式可解n 難解問(wèn)題與易解問(wèn)題之相似性難解問(wèn)題與易解問(wèn)題之相似性 1）最短最短/ /最長(zhǎng)簡(jiǎn)單路徑最長(zhǎng)簡(jiǎn)單路徑 單源最短路徑問(wèn)題：對(duì)有向

13、圖G，時(shí)間O(VE)，P P問(wèn)題問(wèn)題 兩點(diǎn)間最長(zhǎng)路徑：NPCNPC問(wèn)題問(wèn)題，即使所有邊上權(quán)為1 2）歐拉環(huán)歐拉環(huán)/ /哈密爾頓圈哈密爾頓圈（G為無(wú)向圖或有向圖） 歐拉環(huán)：G中有通過(guò)每條邊恰好一次的環(huán)？P P，多項(xiàng)式時(shí)間可解 哈氏圈：G中有通過(guò)每個(gè)頂恰好1次的圈？NPCNPC15 NPNP完全問(wèn)題的求解完全問(wèn)題的求解n減少搜索量減少搜索量 簡(jiǎn)單算法是窮舉搜索，時(shí)間為指數(shù) 減少搜索量：分枝限界法，隱枚舉法、動(dòng)態(tài)規(guī)劃等 可以提高效率，但時(shí)間復(fù)雜度不變n優(yōu)化問(wèn)題優(yōu)化問(wèn)題 降低優(yōu)化要求，求近似解，以得到一個(gè)多項(xiàng)式時(shí)間的算法。即：找尋在容許的時(shí)間內(nèi)得到容許精度的近似最優(yōu)解的算法 16 16 16 16 1

14、6 16 | Presentation Title | Month 2010近似算法近似算法217 Ch.1Ch.1導(dǎo)論導(dǎo)論 現(xiàn)實(shí)中許多優(yōu)化問(wèn)題是NP-hard的，由復(fù)雜性理論知：若PNP(很可能為真)，就不可能找到多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間的算法來(lái)對(duì)問(wèn)題的所有輸入實(shí)例所有輸入實(shí)例求出最優(yōu)解最優(yōu)解。但若放松要求，就可能存在有效求解算法。 實(shí)用中可考慮3種放寬要求的可能性：1.1.超多項(xiàng)式時(shí)間啟發(fā)超多項(xiàng)式時(shí)間啟發(fā) 不再要求多項(xiàng)式時(shí)間算法，有時(shí)求解問(wèn)題存在超多項(xiàng)式時(shí)間算法，實(shí)用中相當(dāng)快。例如，0/1背包問(wèn)題是NPC問(wèn)題，但存在1個(gè)偽多項(xiàng)式時(shí)間算法很容易解決它. 缺點(diǎn)：缺點(diǎn)：該技術(shù)只對(duì)少數(shù)問(wèn)題有效。 18

15、 Ch.1Ch.1導(dǎo)論導(dǎo)論2.2.啟發(fā)式概率分析啟發(fā)式概率分析 不再要求問(wèn)題的解滿足所有的輸入實(shí)例。在某些應(yīng)用中，有可能輸入實(shí)例的類(lèi)被嚴(yán)格限制，對(duì)這些受限實(shí)例易于找到其有效算法。而這種結(jié)果往往歸功于對(duì)輸入實(shí)例約束的概率模型。 缺點(diǎn)：缺點(diǎn)：選取一個(gè)特殊的輸入分布往往是不易的。 3.3.近似算法近似算法 不再要求總是找到最優(yōu)解。在實(shí)際應(yīng)用中有時(shí)很難確定一個(gè)最優(yōu)解和近似最優(yōu)解(次優(yōu)解)之間的差別，因問(wèn)題的輸入實(shí)例數(shù)據(jù)本身就可能是近似的。 設(shè)計(jì)一個(gè)算法能夠求出所有情況下的次優(yōu)解來(lái)解NP-hard問(wèn)題往往是真正有效的手段。 19 Ch.1Ch.1導(dǎo)論導(dǎo)論n優(yōu)化問(wèn)題近似解分類(lèi)優(yōu)化問(wèn)題近似解分類(lèi) 1 1）容

16、易近似）容易近似 Knapsack，Scheduling，Bin Packing等 2 2）中等難度）中等難度 Vertex Cover，Euclidean TSP，Steiner Trees等 3 3）難于近似）難于近似 Graph Coloring，TSP，Clique等 這類(lèi)問(wèn)題即使找到很差的近似解也是NP-hard 20 1.11.1預(yù)備知識(shí)和基本定義預(yù)備知識(shí)和基本定義Def1.1 Def1.1 一個(gè)優(yōu)化問(wèn)題一個(gè)優(yōu)化問(wèn)題由三部分構(gòu)成：由三部分構(gòu)成：n 實(shí)例集實(shí)例集D D：輸入實(shí)例的集合：輸入實(shí)例的集合n 解集解集S(I)S(I)：輸入實(shí)例：輸入實(shí)例I I D D的所有可行解的集合的所有

17、可行解的集合n 解的值函數(shù)解的值函數(shù)f f：給每個(gè)解賦一個(gè)值，：給每個(gè)解賦一個(gè)值，f f：S(I)RS(I)Rn一個(gè)最大值優(yōu)化問(wèn)題一個(gè)最大值優(yōu)化問(wèn)題是：是： 對(duì)于給定的I D，找一個(gè)解 使得： ( ), ()( )IoptS Iff( )IoptS I 此最優(yōu)解的值稱(chēng)為OPT(I),即： 有時(shí)不太嚴(yán)格地可稱(chēng)其為最優(yōu)解( ) ()IoptOPT If21 1.11.1預(yù)備知識(shí)和基本定義預(yù)備知識(shí)和基本定義n裝箱問(wèn)題（裝箱問(wèn)題（BPBP） 非形式地，給定一個(gè)size在0,1之間的項(xiàng)的集合，要求將其放入單位size的箱子中，使得所用的箱子數(shù)目最少。故有最小優(yōu)化問(wèn)題： 1)實(shí)例: I=s1, s2, ,

18、 sn, 滿足i, si0,1 2)解: =B1, B2, ,Bk是I的一個(gè)不相交的劃分，使得 i, BiI 且最小優(yōu)化問(wèn)題是求最小的k 3)解的值：使用的箱子數(shù),即f()=k1ijj BS22 1.1 1.1 預(yù)備知識(shí)和基本定義預(yù)備知識(shí)和基本定義n約定約定 1）f的值域和I里的所有數(shù)是整數(shù) 易于擴(kuò)展至有理數(shù) 2）對(duì)任何 S(I)，f()受囿于多項(xiàng)式(對(duì)I中數(shù)的size) 只討論NP完全的優(yōu)化問(wèn)題，因?yàn)樗妆晦D(zhuǎn)換為判定問(wèn)題 典型情況是問(wèn)題1是問(wèn)題2的判定版本。若2是最大值問(wèn)題，則1的形式為： “是否存在 D(I)，使得f() k？”Def1.2Def1.2 若一個(gè)NPH判定問(wèn)題1是多項(xiàng)式可歸約

19、為計(jì)算一個(gè)優(yōu)化問(wèn)題2的解，則是2 NPH的 。23 1.1 1.1 預(yù)備知識(shí)和基本定義預(yù)備知識(shí)和基本定義n 近似算法的性能近似算法的性能 算法質(zhì)量(measure of goodness)是在最優(yōu)解和近似解之間建立某種關(guān)系，這種度量也稱(chēng)為性能保證性能保證(Performance guarantees)。Def1.3 Def1.3 一個(gè)近似算法A，是一個(gè)多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間求解優(yōu)化問(wèn)題的算法，使得對(duì)一個(gè)給定的的輸入實(shí)例I，它輸出某個(gè)解S(I)。通常，我們用A(I)表示算法A所獲得的解的值f()。（有時(shí)不太嚴(yán)格地也可表示其解）24 1.2 1.2 絕對(duì)性能保證絕對(duì)性能保證 在可行的時(shí)間內(nèi)，求裝箱問(wèn)

20、題的最優(yōu)解是不可能的，但可求次最優(yōu)解是多少？顯然，比最優(yōu)解多使用1個(gè)箱子的解是次最優(yōu)的。一般地，我們希望找到1個(gè)近似解，其值與最優(yōu)解的值相差某一小的常數(shù)。 顯然,我們期望對(duì)任何NP-hard問(wèn)題都有一個(gè)絕對(duì)近似算法，但是對(duì)于大多數(shù)NP-hard問(wèn)題，僅當(dāng)P=NP時(shí)，才能找到絕對(duì)近似算法(指多項(xiàng)式時(shí)間)。Def1.4Def1.4：絕對(duì)性能度量：絕對(duì)性能度量 一個(gè)絕對(duì)近似算法是優(yōu)化問(wèn)題的多項(xiàng)式時(shí)間近似算法A，使得對(duì)某一常數(shù)k0滿足： ID，|A(I)-OPT(I)| k25 1.2.1 1.2.1 絕對(duì)近似算法絕對(duì)近似算法1 1、圖的頂點(diǎn)著色、圖的頂點(diǎn)著色 使用最少的顏色數(shù)來(lái)為圖G的頂點(diǎn)上色，使得

21、所有相鄰的頂點(diǎn)均有不同的顏色，即使G是平面圖，該問(wèn)題的判定版本也是NP-hard的，它有1個(gè)絕對(duì)近似算法。Th1.1Th1.1：判定一個(gè)平面圖是否可3著色的問(wèn)題是NPC的。近似算法近似算法A(G)/A(G)/對(duì)任意平面圖G染色 1)檢驗(yàn)G是否可2染色(即G是二部圖?),若是則G可2染色; 2)否則,計(jì)算5染色;/;/可在多項(xiàng)式時(shí)間內(nèi)可在多項(xiàng)式時(shí)間內(nèi),任何平面圖G是/可5染色的(實(shí)際上四色定理告訴我們G是可4染色的) 這就證明了算法A比最優(yōu)解多用的顏色數(shù)不會(huì)超過(guò)2：Th1.2Th1.2：對(duì)給定的任意平面圖G，近似算法A的性能滿足: |A(G)-OPT(G)| 2 26 1.2.1 1.2.1 絕

22、對(duì)近似算法絕對(duì)近似算法2 2、圖的邊著色、圖的邊著色 使用最少的顏色為圖的邊上色，使得所有相鄰的邊有不同的顏色。如下定理(Vizing)說(shuō)明最大度數(shù)與邊著色數(shù)之關(guān)系：Th1.3Th1.3：任一圖至少需要，至多需要+1種顏色為邊著色 Vizing定理的證明給出了一個(gè)多項(xiàng)式時(shí)間的算法A找到+1邊著色，但令人驚奇的是邊著色問(wèn)題即使是很特殊的情況也是NP-hard的，正如下述的Holyer定理：Th1.4Th1.4：確定一個(gè)3正則平面圖所需的邊著色數(shù)問(wèn)題是NPH.綜上所述：存在絕對(duì)近似算法A，使得下述定理成立：Th1.5Th1.5：近似算法A有性能保證：|A(G)-OPT(G)| 127 1.2.2

23、1.2.2 絕對(duì)近似算法之否定絕對(duì)近似算法之否定 前面的例子似乎說(shuō)明只有很特殊的一類(lèi)優(yōu)化問(wèn)題可能有絕對(duì)近似算法：已知最優(yōu)解的值或值所在的小范圍。但最優(yōu)解的值不易確定時(shí)是否有絕對(duì)近似算法仍然是open. 對(duì)于大多數(shù)NP-hard問(wèn)題，存在絕對(duì)近似算法(多項(xiàng)式時(shí)間)當(dāng)且僅當(dāng)存在多項(xiàng)式的精確算法（即：可在多可在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解） 否定結(jié)果否定結(jié)果：證明問(wèn)題的絕對(duì)近似算法的不存在性！28 1.2.2 1.2.2 絕對(duì)近似算法之否定絕對(duì)近似算法之否定 最優(yōu)解是使得f(I) = 最大的可行解n0/10/1背包問(wèn)題背包問(wèn)題 問(wèn)題實(shí)例：l項(xiàng)集：項(xiàng)集：I=1,2,nI=1,2,nl大小

24、：大小：s s1 1,s,s2 2,s,sn nl利潤(rùn)：利潤(rùn)：p p1 1,p,p2 2,p,pn nl背包容量：背包容量：B B 問(wèn)題的一個(gè)可行解是子集II，i IisB該問(wèn)題(0/1背包）是NP-hard的，除非存在多項(xiàng)式時(shí)間算法能夠找到最優(yōu)解，否則不存在絕對(duì)近似算法。i Iip29 1.2.2 1.2.2 絕對(duì)近似算法之否定絕對(duì)近似算法之否定Pf：使用擴(kuò)放法反證。 假定存在算法A具有性能保證k（注意k是正整數(shù)）nTh.1.6Th.1.6 若PNP，則對(duì)任何確定的k，找不到近似算法A可解背包問(wèn)題使得：|A(I)-OPT(I)| k設(shè)I D，可構(gòu)造新實(shí)例I使得 si=si pi=(k+1)p

25、i即：除了利潤(rùn)擴(kuò)放k+1倍之外，其余參數(shù)不變。故I的可行解也是I的可行解，反之亦然。只是解的值相差k+1倍。在I上運(yùn)行算法A獲得解A(I)，設(shè)A在實(shí)例I上的解是： |A(I)-OPT(I)| k | (k+1)f()-(k+1)OPT(I)| k |f()-OPT(I)| k/(k+1) |f()-OPT(I)|=030 即：我們已經(jīng)找到了一個(gè)多項(xiàng)式時(shí)間的算法即：我們已經(jīng)找到了一個(gè)多項(xiàng)式時(shí)間的算法A A，它對(duì)背包問(wèn)題的任一輸入實(shí)例它對(duì)背包問(wèn)題的任一輸入實(shí)例I I，均能找到最優(yōu)，均能找到最優(yōu)解。解。31 1.2.2 1.2.2 絕對(duì)近似算法之否定絕對(duì)近似算法之否定PfPf：定義圖的m次冪Gm：取

26、G的m個(gè)拷貝，連接位于不同副本里的任意兩頂點(diǎn)。 ClaimClaim：G中最大團(tuán)的size為當(dāng)且僅當(dāng)Gm里最大團(tuán)的size是m（Ex.）n團(tuán)團(tuán)(Clique)(Clique)問(wèn)題問(wèn)題 找圖G中最大團(tuán)（最大完全子圖），該問(wèn)題是NP-hard的。Th.1.7Th.1.7 若PNP，則對(duì)于團(tuán)問(wèn)題不存在絕對(duì)近似算法上述證明之關(guān)鍵是Scaling性質(zhì)，輸入實(shí)例中數(shù)字間線性相關(guān)很易使其成立。對(duì)非數(shù)字問(wèn)題Scaling性質(zhì)是否仍然成立？32 1.2.2 1.2.2 絕對(duì)近似算法之否定絕對(duì)近似算法之否定 對(duì)于任給的Gm中體積為的團(tuán)，易于用多項(xiàng)式時(shí)間多項(xiàng)式時(shí)間在G中找到一個(gè)體積為/m的團(tuán)。因此我們能夠在G中找到

27、一個(gè)團(tuán)C，使得： | |C|-OPT(G) | k/(k+1)因?yàn)镃和OPT(G)均是整數(shù)，故C是最優(yōu)團(tuán)。反證：反證：設(shè)G是任意的無(wú)向圖，近似算法A給出的絕對(duì)誤差是k。在Gk+1上運(yùn)行A，若G中最大團(tuán)size為,則我們有|A(Gk+1)-OPT(Gk+1)| k |A(Gk+1)-(k+1)OPT(G)| k33 1.3 1.3 相對(duì)性能保證相對(duì)性能保證 1.3.11.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 雖然我們渴望得到絕對(duì)性能保證，但是較難的優(yōu)化問(wèn)題很難找到絕對(duì)近似算法。因此，需要放松對(duì)“好的近似算法”的要求。 考慮簡(jiǎn)單的多機(jī)調(diào)度問(wèn)題：輸入n個(gè)作業(yè)J1，J2，Jn，相應(yīng)的運(yùn)行時(shí)間為P1，P2，Pn，設(shè)

28、每個(gè)Pi是有理數(shù)。將n個(gè)作業(yè)分配到m臺(tái)同樣的機(jī)器上，以使得完成時(shí)間最短。完成時(shí)間完成時(shí)間定義為：所有機(jī)器上作業(yè)運(yùn)行總時(shí)間最長(zhǎng)的那一臺(tái)機(jī)器的運(yùn)行時(shí)間。 可行解集合可行解集合：n個(gè)作業(yè)被劃分為m個(gè)子集，一個(gè)解的值是所有子集中總運(yùn)行時(shí)間最長(zhǎng)的子集的運(yùn)行時(shí)間。該問(wèn)題即使在m=2時(shí)也是NP-hard的。34 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 Th.1.8 設(shè)A表示List調(diào)度算法，則對(duì)于所有輸入實(shí)例IList調(diào)度算法(Graham)：將n個(gè)作業(yè)依次以online的方式分配到m臺(tái)機(jī)器中的某一臺(tái)上，規(guī)則是將當(dāng)前作業(yè)分配到當(dāng)時(shí)負(fù)載最小的機(jī)器上，而機(jī)器負(fù)載是分配給它的所有作業(yè)的總的運(yùn)行時(shí)間。 界是緊致的

29、，因?yàn)榇嬖谝粋€(gè)實(shí)例I*，使得上式相等： A(I*)/OPT(I*)=2-1/m PfPf：先證近似比上界。不失一般性，假定所有作業(yè)分配完畢后，機(jī)器M M1 1的負(fù)載最大的負(fù)載最大。設(shè)L L表示M1上所有作業(yè)總運(yùn)行時(shí)間總運(yùn)行時(shí)間,( )12( )A IOPT Im35 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度Pf(Pf(續(xù)續(xù)) )：設(shè)Jj是M1上最后一個(gè)分配到的作業(yè)，則其它機(jī)器上的負(fù)載均大于等于L-Pj。這是因?yàn)楫?dāng)Jj被分配到M1時(shí)，M1是負(fù)載最小的機(jī)器，其負(fù)載為L(zhǎng)-Pj。于是可得： 由于A(I)=L，故有： OPT(I)(L-Pj)+Pj/m=A(I)-(1-1/m)Pj 必須有某臺(tái)機(jī)器執(zhí)行作

30、業(yè)Jj，OPT(I) Pj 于是：A(I)/OPT(I) 2-1/mJ Jj jL- PL- Pj jL L MMmmMM2 2MM1 1但I(xiàn)的最優(yōu)解的值顯然滿足：1()nijjiPm LPP1( )niiPOPT Im36 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度Pf(Pf(續(xù)續(xù)) )：現(xiàn)證近似比的緊確界?？紤]輸入實(shí)例I*，設(shè) n = m(m-1)+1設(shè)前n-1個(gè)作業(yè)每個(gè)均有運(yùn)行時(shí)間1，而最后1個(gè)作業(yè)Jn有Pn=m。易于證明：OPT(I*)=m，而A(I*)=2m-1故有： A(I*)/OPT(I*)=2-1/m MMmmMM1 1 MMm-1m-1 m個(gè)時(shí)間為1的Job J Jn n最最優(yōu)

31、優(yōu)解解MM1 1 MMm-1m-1 m-1m-1 近近似似解解 MMmmJ Jn n m m37 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 上述結(jié)果導(dǎo)出了近似算法質(zhì)量的另一種度量方法：相對(duì)性相對(duì)性能度量能度量。其形式化定義如下Def.1.5Def.1.5 設(shè)A是優(yōu)化問(wèn)題的一個(gè)近似算法，算法A在一個(gè)輸入實(shí)例I上的性能比性能比R RA A(I)(I)被定義為： 此定義統(tǒng)一使近似比(性能比)RA(I)1，越接近1越好( ) ( )( ) ) ( )AA IifOPT IRIOPT IifA I是最小化問(wèn)題（是最大化問(wèn)題 38 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 例如：對(duì)于List調(diào)度算法A,我

32、們有: RA=2-1/mDef1.6 Def1.6 對(duì)于優(yōu)化問(wèn)題，近似算法A的絕對(duì)性能比絕對(duì)性能比R RA A是 RA= inf rRA(I) r, ID 即： RA是性能比上界集合中的下確界(最大下界) 更好的調(diào)度是LPT(Longest Processing Time)：將作業(yè)按其運(yùn)行時(shí)間遞減序排序,然后用List策略調(diào)度,其結(jié)果: Th.1.9：LPT算法的性能（近似）比：Pf：當(dāng)m=1時(shí)， A(I)=OPT(I) A(I)/OPT(I)=4/3-1/3 設(shè)對(duì)某個(gè)m1，該定理不成立。4133LPTRm 39 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 這與I是違反定理的最少作業(yè)數(shù)的實(shí)例矛盾

33、矛盾,IILPT的調(diào)度次序是J1,J2,Jn,其完成時(shí)間是A(I)。設(shè)其中最遲完成的作業(yè)是Jk，則k=n。否則，若k kn n，算法A運(yùn)行作業(yè)J1,J2,Jk(記為實(shí)例II)的完成時(shí)間仍是A(I)，即A(I)=A(I)，而對(duì)最優(yōu)解顯然OPT(I) OPT(I)，故有：( )( )41( )( )33A IA IOPT IOPT ImPf(Pf(續(xù)續(xù)) )：則可設(shè)違反該定理具有最少作業(yè)數(shù)的實(shí)例I是J1,J2,Jn, 不妨設(shè)P1 P2 Pn40 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 另一方面，因?yàn)?現(xiàn)證明：對(duì)于實(shí)例I的最優(yōu)調(diào)度，在任何機(jī)器上分配的作業(yè)數(shù)不超過(guò)2，因此n2m Jn是LPT調(diào)度A中

34、最遲完成的作業(yè)，在A中它開(kāi)始于時(shí)刻A(I)-Pn，且此刻其它機(jī)器均無(wú)空余時(shí)間，即:111( )nniiA IPPmA(I)A(I) MMmmMMi iMM1 1P Pn n 111( )ninimA IPPmm 11( )niiOPT IPm1( )41( )1133( )( )( )nnmOPT IPPA ImmmOPT IOPT ImOPT I 41 1.3.1 1.3.1 多機(jī)調(diào)度多機(jī)調(diào)度 Pn是時(shí)間最短的作業(yè) 實(shí)例I的最優(yōu)調(diào)度中任何機(jī)器上的作業(yè)2 當(dāng)最優(yōu)調(diào)度在任何機(jī)器上至多包含2個(gè)作業(yè)時(shí)，LPT也是最優(yōu)的。證明如下： 不妨設(shè)n=2m，若nm. Pi,PjPs,Pt，交換Pj和Pt，則

35、Pi+PtPi+Pj Ps+PjPi+Pj交換后的調(diào)度O的最遲完成時(shí)間只可能減少，故O也是最優(yōu)調(diào)度。對(duì)于i,jm可類(lèi)似證明。必有最優(yōu)調(diào)度使J1,.,Jm分別分配到M1,Mm上，當(dāng)將Jm+1,.,J2m分配到M臺(tái)機(jī)器上時(shí)，LPT是將長(zhǎng)時(shí)間的作業(yè)分配到輕負(fù)載上，必與該最優(yōu)調(diào)度結(jié)果相同。( )411(2)( )33A ImOPT Im 43 1.3 1.3 相當(dāng)性能保證相當(dāng)性能保證 但未必有但未必有: :Def1.7Def1.7：一個(gè)優(yōu)化問(wèn)題的近似算法A, 其漸近性能比為:inf |,( ) with ( )AARrN Z R Ir forIDOPT IN 有時(shí)，絕對(duì)性能比可能并不是好的性能保障。因

36、為可能存在輸入實(shí)例使得最優(yōu)解的值很小，而近似算法的性能也僅與最優(yōu)值稍有不同，但此時(shí)其近似比仍然會(huì)過(guò)大。為此可定義：顯然有:1AARR 對(duì)于有Scaling性質(zhì)的問(wèn)題，近似算法的絕對(duì)性能比和漸近性能比是相同的，為什么？但多數(shù)優(yōu)化問(wèn)題無(wú)此性質(zhì)！AARR44 1.3 1.3 相當(dāng)性能保證相當(dāng)性能保證 1.3.2 裝箱問(wèn)題（BP） 對(duì)于一個(gè)最小化最小化問(wèn)題，如何求性能比的上界？ 1）證明A(I) 關(guān)于某個(gè)參數(shù)x的上界； 2）證明OPT(I)關(guān)于x的下界然后從這兩個(gè)不等式中消除x即可的性能比。裝箱定義如前。即：設(shè)有n件物品，每件物品大小Si0,1(1in)，按某種策略將其裝入大小為大小為1 1的若干箱子

37、中，使箱子數(shù)盡可能小。45 1.3.2 1.3.2 裝箱問(wèn)題（裝箱問(wèn)題（BPBP） n 首次適應(yīng)首次適應(yīng)(First Fit, FF)(First Fit, FF)算法算法 FFFF策略策略：依次將物品裝箱，設(shè)當(dāng)前要裝第i件，B1,B2,Bj是當(dāng)前已開(kāi)過(guò)的箱子，則從頭依次掃描箱子，將物品i放入第1個(gè)適合(指大小夠放)的箱子中；若不存在適合的箱子，則新開(kāi)箱子Bj+1，將物品i放入其中。ClaimClaim：對(duì)所有實(shí)例，RFF(I)2Pf:Pf:在整個(gè)裝箱過(guò)程中至多只有1個(gè)箱子是大于半空的。若否，不妨設(shè)Bi和Bj均大于半空且i0兩類(lèi)近似算法之間的近似性能（相對(duì)誤差）：兩類(lèi)近似算法之間的近似性能（相

38、對(duì)誤差）：A是一個(gè)f(n)-近似算法當(dāng)且僅當(dāng)對(duì)每個(gè)size為n的輸入實(shí)例I，有：nBP的一個(gè)近似算法A滿足：|A(I)-OPT(I)|O( lg2OPT(I) )蘊(yùn)含著漸近性能比為1。|( )( )|( )( )OPT IA If nOPT I2|( )( )|( )1( )( )( )|( )( )|(lg( )111( )( )( )( )A IOPT IA IOPT IOPT IA IA IOPT IOOPT TOPT IOPT IOPT IOPT I 當(dāng)61 1.4 1.4 其他其他 n近似方案近似方案(Approximation Scheme)一個(gè)優(yōu)化問(wèn)題一個(gè)優(yōu)化問(wèn)題的近似方案是一個(gè)

39、算法的近似方案是一個(gè)算法A A，它以實(shí)例，它以實(shí)例I I和和誤差界誤差界作為輸入，且有性能保證作為輸入，且有性能保證: R: RA A( I, ( I, ) ) 1+1+。對(duì)于最小化問(wèn)題，對(duì)于最小化問(wèn)題，是相對(duì)誤差。實(shí)際上，算法是相對(duì)誤差。實(shí)際上，算法A A對(duì)應(yīng)一對(duì)應(yīng)一個(gè)算法族個(gè)算法族AA：00使得使得n多項(xiàng)式近似方案多項(xiàng)式近似方案(PAS: Polynomial Approximation Scheme)是一近似方案是一近似方案AA ，對(duì)任一確定的，對(duì)任一確定的，每個(gè)算法均以其，每個(gè)算法均以其sizeIsizeI的多項(xiàng)式時(shí)間運(yùn)行。的多項(xiàng)式時(shí)間運(yùn)行。1AR n完全多項(xiàng)式近似方案完全多項(xiàng)式近似方

40、案(FPAS: Fully PAS)是一近似方案是一近似方案AA ，對(duì)任一確定的，對(duì)任一確定的，每個(gè)算法均以，每個(gè)算法均以其其sizeIsizeI和和1/1/的多項(xiàng)式時(shí)間運(yùn)行的多項(xiàng)式時(shí)間運(yùn)行62 1.4 1.4 其他其他 n理想的近似方案理想的近似方案近似方案實(shí)際上研究近似算法的近似方案實(shí)際上研究近似算法的運(yùn)行時(shí)間運(yùn)行時(shí)間和和近似質(zhì)量近似質(zhì)量之之間的關(guān)系（二者間如何折衷？）。希望：近似算法的運(yùn)間的關(guān)系（二者間如何折衷？）。希望：近似算法的運(yùn)行時(shí)間并不隨著性能比的減少而增長(zhǎng)太快！行時(shí)間并不隨著性能比的減少而增長(zhǎng)太快！理想情況理想情況：減小減小1 1個(gè)常數(shù)因子，為獲得預(yù)期的近似質(zhì)個(gè)常數(shù)因子，為獲得

41、預(yù)期的近似質(zhì)量，所增加的運(yùn)行時(shí)間不應(yīng)超過(guò)量，所增加的運(yùn)行時(shí)間不應(yīng)超過(guò)1 1個(gè)常數(shù)因子個(gè)常數(shù)因子( (盡管兩常盡管兩常數(shù)因子不一定相同數(shù)因子不一定相同) )nPAS VS FPASPAS VS FPAS背包問(wèn)題的背包問(wèn)題的PASPAS中，算法中，算法A A的運(yùn)行時(shí)間一般是的運(yùn)行時(shí)間一般是n nO(1/O(1/) )；多；多機(jī)調(diào)度的機(jī)調(diào)度的PASPAS中，算法中，算法A A的運(yùn)行時(shí)間為的運(yùn)行時(shí)間為O(mO(m1/1/) )。顯然，。顯然，減小一點(diǎn)將會(huì)引起算法時(shí)間的急劇增加。為此，引進(jìn)減小一點(diǎn)將會(huì)引起算法時(shí)間的急劇增加。為此，引進(jìn)FPASFPAS可克服此缺點(diǎn)。可克服此缺點(diǎn)。63 1.4 1.4 其他其他 n例子：調(diào)度問(wèn)題的近似方案例子：調(diào)度問(wèn)題的近似方案假定假定nmnm，運(yùn)行時(shí)間為降序，運(yùn)行時(shí)間為降序(ij(iPPj j) )，對(duì)每一整數(shù)，對(duì)每一整數(shù)k k 0,n0,n定義算法定義算法A Ak k：Algorithm Ak：InputInput：n n個(gè)作業(yè)的運(yùn)行時(shí)間個(gè)作業(yè)的運(yùn)行時(shí)間PP1 1,P,Pn n 和機(jī)器數(shù)和機(jī)器數(shù)m m；OutputOutput：一個(gè)可行的調(diào)度；：一個(gè)可行的調(diào)度；Step1Step1：最優(yōu)調(diào)度前：最優(yōu)調(diào)度前k k個(gè)作業(yè)個(gè)作業(yè)J J1 1,J,Jk k；Step2Step2：從前一步所獲得的部分調(diào)度