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

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

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

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

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

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

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

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

9、-NP-完全性理論完全性理論n Cook的貢獻：第一個NPC問題 史提芬?guī)炜?Stephen Arthur Cook，1939)NP完全 性 理 論 的 奠 基 人 ， 他 在 1 9 7 1 年 論 文 ” T h e Complexity of Theorem Proving Procedures”中，給出了第一個NP完備的證明，即CookCook定理定理： 可滿足性問題（Satisfiablity problem) 是NP完全問題，亦即 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é)系教授，他的論文開啟了NP完備性的研究，令該領(lǐng)域于之后的十年成為計算機科學(xué)中最活躍和重要的研究。因其在計算復(fù)雜性理論方面的貢獻，尤其是在奠定NP完全性理論基礎(chǔ)上的突出貢獻而榮獲1982年度的圖靈獎。13 NP-NP-完全性理論完全性理論n KarpKarp的貢獻的貢獻 理查德卡普（Richard Karp，1935-）1972年論文”Reducibility among Combinatorial Problems”發(fā)展和加強了由庫克提出的“NP完全性”理

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

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

13、圖G，時間O(VE)，P P問題問題 兩點間最長路徑：NPCNPC問題問題，即使所有邊上權(quán)為1 2）歐拉環(huán)歐拉環(huán)/ /哈密爾頓圈哈密爾頓圈（G為無向圖或有向圖） 歐拉環(huán)：G中有通過每條邊恰好一次的環(huán)？P P，多項式時間可解 哈氏圈：G中有通過每個頂恰好1次的圈？NPCNPC15 NPNP完全問題的求解完全問題的求解n減少搜索量減少搜索量 簡單算法是窮舉搜索，時間為指數(shù) 減少搜索量：分枝限界法，隱枚舉法、動態(tài)規(guī)劃等 可以提高效率，但時間復(fù)雜度不變n優(yōu)化問題優(yōu)化問題 降低優(yōu)化要求，求近似解，以得到一個多項式時間的算法。即：找尋在容許的時間內(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)實中許多優(yōu)化問題是NP-hard的，由復(fù)雜性理論知：若PNP(很可能為真)，就不可能找到多項式時間多項式時間的算法來對問題的所有輸入實例所有輸入實例求出最優(yōu)解最優(yōu)解。但若放松要求，就可能存在有效求解算法。 實用中可考慮3種放寬要求的可能性：1.1.超多項式時間啟發(fā)超多項式時間啟發(fā) 不再要求多項式時間算法，有時求解問題存在超多項式時間算法，實用中相當(dāng)快。例如，0/1背包問題是NPC問題，但存在1個偽多項式時間算法很容易解決它. 缺點：缺點：該技術(shù)只對少數(shù)問題有效。 18

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、業(yè)Jj，OPT(I) Pj 于是：A(I)/OPT(I) 2-1/mJ Jj jL- PL- Pj jL L MMmmMM2 2MM1 1但I的最優(yōu)解的值顯然滿足：1()nijjiPm LPP1( )niiPOPT Im36 1.3.1 1.3.1 多機調(diào)度多機調(diào)度Pf(Pf(續(xù)續(xù)) )：現(xiàn)證近似比的緊確界。考慮輸入實例I*，設(shè) n = m(m-1)+1設(shè)前n-1個作業(yè)每個均有運行時間1，而最后1個作業(yè)Jn有Pn=m。易于證明：OPT(I*)=m，而A(I*)=2m-1故有： A(I*)/OPT(I*)=2-1/m MMmmMM1 1 MMm-1m-1 m個時間為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 多機調(diào)度多機調(diào)度 上述結(jié)果導(dǎo)出了近似算法質(zhì)量的另一種度量方法：相對性相對性能度量能度量。其形式化定義如下Def.1.5Def.1.5 設(shè)A是優(yōu)化問題的一個近似算法，算法A在一個輸入實例I上的性能比性能比R RA A(I)(I)被定義為： 此定義統(tǒng)一使近似比(性能比)RA(I)1，越接近1越好( ) ( )( ) ) ( )AA IifOPT IRIOPT IifA I是最小化問題（是最大化問題 38 1.3.1 1.3.1 多機調(diào)度多機調(diào)度 例如：對于List調(diào)度算法A,我

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

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

34、最遲完成的作業(yè)，在A中它開始于時刻A(I)-Pn，且此刻其它機器均無空余時間，即: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 多機調(diào)度多機調(diào)度 Pn是時間最短的作業(yè) 實例I的最優(yōu)調(diào)度中任何機器上的作業(yè)2 當(dāng)最優(yōu)調(diào)度在任何機器上至多包含2個作業(yè)時，LPT也是最優(yōu)的。證明如下： 不妨設(shè)n=2m，若nm. Pi,PjPs,Pt，交換Pj和Pt，則

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

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

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

38、對誤差）：A是一個f(n)-近似算法當(dāng)且僅當(dāng)對每個size為n的輸入實例I，有：nBP的一個近似算法A滿足：|A(I)-OPT(I)|O( lg2OPT(I) )蘊含著漸近性能比為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)一個優(yōu)化問題一個優(yōu)化問題的近似方案是一個

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

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

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