算法分析與設計2007第d講

《算法分析與設計2007第d講》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、第D講上次內(nèi)容：(1)TSP問題近似性能比為2的近似算法。(2)近似算法設計：TSP問題近似度為3/2近似算法。(3)多任務排工近似度為2-1/m的近似算法。(4)獨立任務排工的多項式時間近似算法。再解釋絕對近似性能比：我們設計了算法以后希望能找到一個界r,使得RA(I)￡r。r顯然比1.8不會小。比如說能找到r=2.5，使得RA(I)￡2.5=r。(*)如果算法A求解每個實例I都會有RA(I)<2.5，(**)顯然對于算法A，必有小于2.5的r1，使得RA(I)￡r1。兩件事(*)和(**)都很難做到。但是如果可以碰

2、到這么一種情況：能夠找到r，使得RA(I)￡r=2，又能舉出一個實例I，滿足RA(I)=r=2。絕對近似性能比定義的原因即在于此。漸進近似性能比也具有同樣的含義。回到另一面去看看定理：若P1NP，則圖的著色問題不存在的多項式時間近似算法。已知圖的3著色問題是NP-hard問題，兩個圖相乘是什么意思：第11頁第D講G=G1*G2的做法反證法，若圖著色問題存在<的近似算法，則存在K，當OPT(G)3K時，A(G)

3、*=G*G’(2)調(diào)用算法A得到著色數(shù)A(G*)。分析：(3x)若G可以三著色?OPT(G*)￡3K，A(G*)<(4/3)3K=4K(4x)若G不能三著色?OPT(G*)34K(說明為什么)，A(G*)3OPT(G*)34K所以：(3)A(G*)<4K，回答Yes。(4)若A(G*)34K，回答No。定理7.13：若P1NP，則貨郎旅游問題不存在近似度<￥的多項式時間近似算法。為什么不說絕對近似性能比呢？頂點個數(shù)少時，枚舉也能得到較好的解。說明：TSP問題不是在metric空間，所以不滿足三角不等式。第11頁第D講證

4、明：實際是證明若反之，則Hamilton回路問題存在多項式時間精確算法。(1)用反證法，設存在常數(shù)K，使￡K。即存在算法A，對TSP的任意最優(yōu)解值超過某個常數(shù)的實例G，有：A(G)￡K*OPT(G)。(2)設GH=(V,E)是Hamilton回路問題任意實例，由GH構造TSP問題實例GTSP如下：lV(GTSP)=V(GH)=Vl(3)分析GH存在hamilton回路?OPT(GTSP)=

5、V

6、A(GTSP)￡K*OPT(GTSP)=K

7、V

8、GH不存在Hamilton回路?OPT(GTSP)>K

9、V

10、第11頁第D講A(

11、GTSP)3OPT(GTSP)>K

12、V

13、這樣我們就能設計Hamilton回路問題的多項式時間算法。說明：(1)找錯一條邊，就會出大問題，近似度超過任意常數(shù)，邊太長了。(2)這不是metric空間的TSP問題，是任意空間的TSP問題，不存在任意常數(shù)近似度的近似算法。§7.3多項式時間近似方案獨立任務排工的進一步討論，n個任務，m臺機器，每個任務加工時間長度ti。新算法，想辦法多費點功夫，前K個任務求最優(yōu)排工。也與問題有關。(1)任務排序：T={T1,T2,…,Tn}，t13t23…3tn(2)確定正整數(shù)K,對前K個任務，

14、求最優(yōu)排工，后n-K個任務，按照先大后小順序排工。上述算法叫F。舉個例子：T={T1,T2,T3,T4,T5,T6}加工時間：8，6，5，4，4，1T1,T2,T3,T4先求最優(yōu)排工。后兩任務再排，得15。最優(yōu)為14。第11頁第D講這個不是最優(yōu)的。定理7.14：m臺處理器，獨立任務排工。實例I。證明：(1)設T是前K個任務的排工時間長度，若F(I)=T，則F(I)=OPT(I)，以下設F(I)>T。(2)在[0，F(xiàn)(I)-tk+1]區(qū)間所有處理器非空閑。由(1)決定，最后完成任務為Tj，j>k，所以[0,F(I)-tj

15、]區(qū)間所有機器非空閑，又tk+13tj最后一個完成的任務tj

16、度越好。定義7.2：若問題p的近似算法A(e)若滿足對任意實例I任意e>0(1)RA(e)[I]<1+e(2)A(e)的時間復雜度是實例I的多項式函數(shù)，則，A(e)稱為求解問題p的多項式時間近似方案。解釋：(1)1+e很容易說明，但后面的多項式不容易說明,時間復雜度一定與e有關。例子：近似性能比為1+e，時間復雜度為：O()，O(