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

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

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

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

5、 若NTM在每一步都恰有2步可供選擇，則回答實例需考察2p(n)種不同的可能性。 存在多項式時間的算法嗎？ 多項式時間內可驗證問題（指驗證其解的正確性）8 P、NP及及NPC類問題類問題n 多一歸約多一歸約 假設L1和L2是兩個判定問題，f將L1的每個實例I變換成L2的實例f(I)。若對L1的每個實例I，I的答案為“是”當且僅當f(I)是L2的答案為“是”的實例，則稱f是從L1到L2的多一歸約，記作： L1mL2（傳遞關系）（傳遞關系） 直觀意義：將求解L1的問題轉換為求解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關系關系 NP-hard問題至少跟NPC問題一樣難。 NPC問題肯定是NP-hard的，但反之不一定 例：停機問題是NP-hard而非NPC的。 該問題不可判定，

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

8、克斯方程的存在性與光滑性7.貝赫和斯維訥通戴爾猜想11 P、NP及及NPC類問題類問題n P、NP、NPC和和NP-hard之關系之關系 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問題 史提芬庫克(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當且僅當當且僅當P=NPP=NP Cook于1961年獲Michigan大學學士學位，1962和

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

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

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

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

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

15、 Ch.1Ch.1導論導論2.2.啟發式概率分析啟發式概率分析 不再要求問題的解滿足所有的輸入實例。在某些應用中，有可能輸入實例的類被嚴格限制，對這些受限實例易于找到其有效算法。而這種結果往往歸功于對輸入實例約束的概率模型。 缺點：缺點：選取一個特殊的輸入分布往往是不易的。 3.3.近似算法近似算法 不再要求總是找到最優解。在實際應用中有時很難確定一個最優解和近似最優解(次優解)之間的差別，因問題的輸入實例數據本身就可能是近似的。 設計一個算法能夠求出所有情況下的次優解來解NP-hard問題往往是真正有效的手段。 19 Ch.1Ch.1導論導論n優化問題近似解分類優化問題近似解分類 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預備知識和基本定義預備知識和基本定義Def1.1 Def1.1 一個優化問題一個優化問題由三部分構成：由三部分構成：n 實例集實例集D D：輸入實例的集合：輸入實例的集合n 解集解集S(I)S(I)：輸入實例：輸入實例I I D D的所有可行解的集合的所有

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

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

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

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

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

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

23、1.2.2 絕對近似算法之否定絕對近似算法之否定 前面的例子似乎說明只有很特殊的一類優化問題可能有絕對近似算法：已知最優解的值或值所在的小范圍。但最優解的值不易確定時是否有絕對近似算法仍然是open. 對于大多數NP-hard問題，存在絕對近似算法(多項式時間)當且僅當存在多項式的精確算法（即：可在多可在多項式時間內找到最優解項式時間內找到最優解） 否定結果否定結果：證明問題的絕對近似算法的不存在性！28 1.2.2 1.2.2 絕對近似算法之否定絕對近似算法之否定 最優解是使得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的，除非存在多項式時間算法能夠找到最優解，否則不存在絕對近似算法。i Iip29 1.2.2 1.2.2 絕對近似算法之否定絕對近似算法之否定Pf：使用擴放法反證。 假定存在算法A具有性能保證k（注意k是正整數）nTh.1.6Th.1.6 若PNP，則對任何確定的k，找不到近似算法A可解背包問題使得：|A(I)-OPT(I)| k設I D，可構造新實例I使得 si=si pi=(k+1)p

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

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

27、一個團C，使得： | |C|-OPT(G) | k/(k+1)因為C和OPT(G)均是整數，故C是最優團。反證：反證：設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 多機調度多機調度 雖然我們渴望得到絕對性能保證，但是較難的優化問題很難找到絕對近似算法。因此，需要放松對“好的近似算法”的要求。 考慮簡單的多機調度問題：輸入n個作業J1，J2，Jn，相應的運行時間為P1，P2，Pn，設

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

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

30、業Jj，OPT(I) Pj 于是：A(I)/OPT(I) 2-1/mJ Jj jL- PL- Pj jL L MMmmMM2 2MM1 1但I的最優解的值顯然滿足：1()nijjiPm LPP1( )niiPOPT Im36 1.3.1 1.3.1 多機調度多機調度Pf(Pf(續續) )：現證近似比的緊確界。考慮輸入實例I*，設 n = m(m-1)+1設前n-1個作業每個均有運行時間1，而最后1個作業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最最優

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

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

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

34、最遲完成的作業，在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 多機調度多機調度 Pn是時間最短的作業 實例I的最優調度中任何機器上的作業2 當最優調度在任何機器上至多包含2個作業時，LPT也是最優的。證明如下： 不妨設n=2m，若nm. Pi,PjPs,Pt，交換Pj和Pt，則

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

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

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

38、對誤差）：A是一個f(n)-近似算法當且僅當對每個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 當61 1.4 1.4 其他其他 n近似方案近似方案(Approximation Scheme)一個優化問題一個優化問題的近似方案是一個

39、算法的近似方案是一個算法A A，它以實例，它以實例I I和和誤差界誤差界作為輸入，且有性能保證作為輸入，且有性能保證: R: RA A( I, ( I, ) ) 1+1+。對于最小化問題，對于最小化問題，是相對誤差。實際上，算法是相對誤差。實際上，算法A A對應一對應一個算法族個算法族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理想的近似方案理想的近似方案近似方案實際上研究近似算法的近似方案實際上研究近似算法的運行時間運行時間和和近似質量近似質量之之間的關系（二者間如何折衷？）。希望：近似算法的運間的關系（二者間如何折衷？）。希望：近似算法的運行時間并不隨著性能比的減少而增長太快！行時間并不隨著性能比的減少而增長太快！理想情況理想情況：減小減小1 1個常數因子，為獲得預期的近似質個常數因子，為獲得

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