3、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講證明：實際是證明若反之，則Hamilton回路問題存在多項式時間精確算法。(1)用反證法，設(shè)存在常數(shù)K，使￡K。即存在算法A，對TSP
4、的任意最優(yōu)解值超過某個常數(shù)的實例G，有：A(G)￡K*OPT(G)。(2)設(shè)GH=(V,E)是Hamilton回路問題任意實例，由GH構(gòu)造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(GTSP)3OPT(GTSP)>K
11、V
12、這樣我們就能設(shè)計Hamilton回路問題的多項式時間算法。說明：(1)找錯一條邊，就會出大問題，近似度超過任意常數(shù)，邊太長了。(2)這不
13、是metric空間的TSP問題，是任意空間的TSP問題，不存在任意常數(shù)近似度的近似算法?！?.3多項式時間近似方案獨立任務(wù)排工的進一步討論，n個任務(wù)，m臺機器，每個任務(wù)加工時間長度ti。新算法，想辦法多費點功夫，前K個任務(wù)求最優(yōu)排工。也與問題有關(guān)。(1)任務(wù)排序：T={T1,T2,…,Tn}，t13t23…3tn(2)確定正整數(shù)K,對前K個任務(wù)，求最優(yōu)排工，后n-K個任務(wù)，按照先大后小順序排工。上述算法叫F。舉個例子：T={T1,T2,T3,T4,T5,T6}加工時間：8，6，5，4，4，1T1,T2,T3,T4先求最優(yōu)排工。后兩任務(wù)再排，得15。最優(yōu)為14。第
14、11頁第D講這個不是最優(yōu)的。定理7.14：m臺處理器，獨立任務(wù)排工。實例I。證明：(1)設(shè)T是前K個任務(wù)的排工時間長度，若F(I)=T，則F(I)=OPT(I)，以下設(shè)F(I)>T。(2)在[0，F(xiàn)(I)-tk+1]區(qū)間所有處理器非空閑。由(1)決定，最后完成任務(wù)為Tj，j>k，所以[0,F(I)-tj]區(qū)間所有機器非空閑，又tk+13tj最后一個完成的任務(wù)tj15、+)tk+1，最少也這么大。￡第一個不等號由(**)而來，第二個不等號由(***)而來。(5)分析算法時間復(fù)雜度TA(m,n)=O(mk+nlogn)，k=m，近似性能比小于1+1/2，k=2m；近似性能比小于1+1/3；說明：k越大時間復(fù)雜度越高，解的優(yōu)化程度越好。定義7.2：若問題p的近似算法A(e)若滿足對任意實例I任意e>0(1)RA(e)[I]<1+e(2)A(e)的時間復(fù)雜度是實例I的多項式函數(shù)，則，A(e)稱為求解問題p的多項式時間近似方案。解釋：(1)1+e很容易說明，但后面的多項式不容易說明,時間復(fù)雜度一定與e有關(guān)。例子：近似性能比為1+e，時
16、間復(fù)雜度為：O()，O(
