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