計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第15章

PAGE12第15章 近似算法找出一類圖的例子說明近似算法Approx-Vertex-Cover始終得不到它的最佳解。解： 有奇數(shù)個(gè)頂點(diǎn)的一根直線就是這類圖的例子。如下圖所示，設(shè)這根線的頂點(diǎn)數(shù)為2k+1，那么最佳解是k個(gè)不相鄰的頂點(diǎn)。但是近似算法Approx-Vertex-Cover每次取兩個(gè)相鄰點(diǎn)，也就是取一系列的邊，而且所取的相鄰的兩條邊中間最多可間隔一個(gè)點(diǎn)，所以取最少邊的做法是，如下圖所示，從一頭開始，取第2條邊。然后，隔一個(gè)點(diǎn)取一條邊，直到無邊可取。這時(shí)，如果還剩2個(gè)點(diǎn)，則必須再取一條邊，否則算法停止。經(jīng)過簡單分析可知，這個(gè)最佳解一共取了2k3條邊，也就是2×2k3個(gè)頂點(diǎn)。因?yàn)?×2k34k3>11234最佳解是C={2,4,6,8}567891234近似算法Approx-Vertex-Cover最好解是C={2,3,5,6,8,9}56789證明算法Approx-Vertex-Cover選出的邊的集合是一個(gè)局部最大(maximal)匹配。局部最大是指不能夠再加一條邊到這個(gè)集合中而仍能形成匹配。證明： 因?yàn)樗惴ˋpprox-Vertex-Cover每選出一條邊之后，這條邊的兩個(gè)頂點(diǎn)就從圖里刪去，后面選出的邊不可能與這條邊共頂點(diǎn)，所以所有選出的邊都是兩兩不相交的，因此算法Approx-Vertex-Cover選出的邊的集合是一個(gè)匹配。又因?yàn)檫@個(gè)集合中頂點(diǎn)形成一個(gè)頂點(diǎn)復(fù)蓋，因此圖里剩下的每條邊必定與這個(gè)集合中某頂點(diǎn)關(guān)聯(lián)，所以這個(gè)匹配不可能再擴(kuò)大了。在證明圖的頂點(diǎn)復(fù)蓋問題是NPC問題時(shí)，我們把clique問題歸約到圖的頂點(diǎn)復(fù)蓋問題，并證明圖G(V,E)有一個(gè)k-clique當(dāng)且僅當(dāng)其補(bǔ)圖G有一個(gè)(n-k)的頂點(diǎn)復(fù)蓋，這里n=|V|。因?yàn)轫旤c(diǎn)復(fù)蓋問題有近似度為2的多項(xiàng)式算法，那么，是否可以利用這個(gè)關(guān)系，使得clique問題也有近似度為常數(shù)的多項(xiàng)式算法呢？解： 雖然G(V,E)的最大clique對應(yīng)G的最小頂點(diǎn)復(fù)蓋，Clique問題不能由此得到近似度為常數(shù)的多項(xiàng)式算法。假設(shè)我們用頂點(diǎn)復(fù)蓋的近似算法求圖G(V,E)的團(tuán)如下：構(gòu)造G(V,E)的補(bǔ)圖G。用近似度為2的頂點(diǎn)復(fù)蓋算法求G的頂點(diǎn)復(fù)蓋C。由C得到原圖的clique=V–C。假設(shè)上面算法產(chǎn)生的頂點(diǎn)復(fù)蓋C有|C|=k個(gè)頂點(diǎn)，而最小頂點(diǎn)復(fù)蓋C*有k*<k個(gè)頂點(diǎn)，k/k*2。如果我們用頂點(diǎn)復(fù)蓋C得到G中一個(gè)有(n-k)個(gè)頂點(diǎn)的clique，因?yàn)樽畲骳lique有n-k*個(gè)點(diǎn)，那么這個(gè)近似解有近似度(n-k*)/(n-k)=1+(k-k*)/(n-k)。這個(gè)比例不能保證小于某常數(shù)。如果k接近n，而且k約等于2k*，這個(gè)比例會(huì)趨向無窮大。我們看個(gè)例子。如果G是如下圖(a)所示的有2m+1個(gè)頂點(diǎn)的圖。如果我們用近似度為2的算法求頂點(diǎn)復(fù)蓋，可能取m條垂直邊，得到如圖(a)所示的2m個(gè)點(diǎn)的頂點(diǎn)復(fù)蓋C。如果用這個(gè)C在原圖中找一個(gè)clique，我們得到只有一個(gè)頂點(diǎn)的clique，而G的最小頂點(diǎn)復(fù)蓋，如圖(b)所示，只需m個(gè)點(diǎn)，原圖G的最大的clique有(m+1)個(gè)頂點(diǎn)。上述算法對這個(gè)例子得到的近似度是m+1112345678911121314近似算法Approx-Vertex-Cover最壞解是C={1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19}151617181910112345678911121314最小復(fù)蓋是C*={1,3,5,7,9,12,14,16,18}151617181910某教授提出了下面這個(gè)求頂點(diǎn)復(fù)蓋的啟發(fā)式算法：找到圖中一個(gè)有最大度數(shù)(degree)的頂點(diǎn)，把這個(gè)點(diǎn)選入頂點(diǎn)復(fù)蓋，然后把這個(gè)點(diǎn)以及與該點(diǎn)關(guān)聯(lián)的邊從圖中刪去。然后，不斷重復(fù)這一過程直到圖中不再有邊為止。證明這個(gè)算法不能保證近似度2。(提示：構(gòu)造一個(gè)二部圖使左邊的點(diǎn)在算法執(zhí)行中不被刪去，而右邊的點(diǎn)逐步被刪去，并使右邊的點(diǎn)的個(gè)數(shù)大于左邊點(diǎn)的個(gè)數(shù)一倍。)解： 讓我們構(gòu)造一個(gè)二部圖使左邊的點(diǎn)在算法執(zhí)行中不被刪去，而右邊的點(diǎn)逐步被刪去，并使右邊的點(diǎn)的個(gè)數(shù)大于左邊點(diǎn)的個(gè)數(shù)一倍。讓我們構(gòu)造一個(gè)具體例子加以說明。為簡單起見，我們假定，如果兩個(gè)頂點(diǎn)，分別在左右兩邊，并有相同的最大度數(shù)時(shí)，算法取右邊的頂點(diǎn)。如下圖(a)所示，先左右各構(gòu)造6個(gè)點(diǎn)和6條不相交的邊。對這個(gè)圖而言，這個(gè)啟發(fā)式算法會(huì)選取右邊6個(gè)點(diǎn)。我們在(a)的基礎(chǔ)上，在右邊加上3個(gè)點(diǎn)得到圖(b)，其中每個(gè)新加的點(diǎn)與左邊兩個(gè)點(diǎn)相連。這樣一來，啟發(fā)式算法需要?jiǎng)h去9個(gè)點(diǎn)了。再往下，在(b)的基礎(chǔ)上，把左邊6個(gè)點(diǎn)分為2組，每組3個(gè)點(diǎn)。然后在右邊加上2個(gè)新的頂點(diǎn)，分別與左邊兩組中點(diǎn)相連得到圖(c)。根據(jù)算法，對圖(c)，我們需要?jiǎng)h去11個(gè)點(diǎn)。再往下，在(c)的基礎(chǔ)上，我們在右邊加一個(gè)點(diǎn)，并把它與左邊的4個(gè)點(diǎn)相連得到圖(d)。顯然，算法會(huì)刪去圖(d)中12個(gè)點(diǎn)。最后一步，我們在(d)的基礎(chǔ)上在右邊加一個(gè)點(diǎn)，并把它與左邊的5個(gè)點(diǎn)相連得到圖(e)。顯然，算法會(huì)刪去圖(e)中13個(gè)點(diǎn)。而最佳解是6個(gè)頂點(diǎn)，即左邊6個(gè)頂點(diǎn)。因?yàn)?3/6>2，所以這個(gè)算法不能保證近似度2。從構(gòu)造過程看，這個(gè)算法不可能有常數(shù)倍的近似度。如果一開始左右各構(gòu)造n個(gè)點(diǎn)和n條不相交的邊，那么，我們在右邊可以順序加n2個(gè)點(diǎn)，n3個(gè)點(diǎn)，n4個(gè)點(diǎn)，…，nn個(gè)點(diǎn)。這導(dǎo)致這個(gè)啟發(fā)式算法得到的頂點(diǎn)復(fù)蓋的頂點(diǎn)個(gè)數(shù)是n+n2+n3+n4+…+nnnlnn。因?yàn)檫@個(gè)圖的最小復(fù)蓋只含左邊(a)(a)(b)(c)(d)(e)考慮下面這個(gè)求貨郎擔(dān)回路的近似算法。我們假定完全圖G(V,E)中邊上的權(quán)滿足三角不等式。算法從任一點(diǎn)rV開始。Closest-Point-TSP(G(V,E),r)Sr //S中頂點(diǎn)將順序組成一個(gè)回路，開始時(shí)含一個(gè)點(diǎn)rwhileSV findedge(u,v)suchthatw(u,v)=min{w(u,v)|uS,vV-S} //找出集合S和V-S之間有最小權(quán)值的邊(u,v)， SS{v}，并且把v插在u后面。endwhilereturnSEnd請證明算法Closest-Point-TSP是個(gè)近似度為2的算法。證明： 我們考慮回路S在插入一個(gè)點(diǎn)后總長會(huì)增加多少。算法循環(huán)開始前其總長W(S)=0。每當(dāng)循環(huán)找到集合S和V-S之間最小權(quán)值的邊(u,v)并把v插入時(shí)，總長會(huì)增加多少呢？當(dāng)?shù)谝粭l邊(u,v)=(r,v)被選取時(shí)，總權(quán)值是w(r,v)+w(v,r)=2w(r,v)。在以后的每一步中，假設(shè)在插入v之前，回路中頂點(diǎn)u后面的點(diǎn)是z，那么插入后總長增加的值應(yīng)該是=w(u,v)+w(v,z)-w(u,z)。根據(jù)三角不等式，w(v,z)w(v,u)+w(u,z)，所以有=w(u,v)+w(v,z)-w(u,z)w(u,v)+[w(v,u)+w(u,z)]-w(u,z)=2w(u,v)。因此，當(dāng)算法結(jié)束時(shí)，回路總長小于等于所有選取的邊(u,v)的總權(quán)值的2倍。我們注意到，集合S和V-S形成頂點(diǎn)V的一個(gè)割，而且這個(gè)割不會(huì)切到前面已選中的邊，所以算法找到的邊的集合實(shí)際上組成了一個(gè)最小支撐樹(MST)。所以，當(dāng)算法結(jié)束時(shí)，回路總長小于等于最小支撐樹的總權(quán)值的2倍。因?yàn)樽钚≈螛涞目倷?quán)值小于等于任一個(gè)貨郎擔(dān)回路的總權(quán)值，所以算法Closest-Point-TSP是個(gè)近似度為2的算法。這個(gè)算法可以這樣理解:從點(diǎn)r開始，用Prim算法計(jì)算MST，每當(dāng)邊(u,v)被選入MST時(shí)，把v插入到S形成的回路中點(diǎn)u的后面。假設(shè)貨郎擔(dān)問題中的頂點(diǎn)是二維平面中的點(diǎn)，而每兩點(diǎn)之間的邊的權(quán)值就是這兩點(diǎn)之間在二維平面中的直線距離(亦稱歐基里得距離，或歐氏距離)。請證明，任何一條最小貨郎擔(dān)回路不會(huì)自身相交。證明： 我們用反證法證明。假設(shè)有一條最小貨郎擔(dān)回路自身相交于一點(diǎn)x，并假設(shè)相交于x的兩條邊是(a,b)和(u,v)。如下圖(a)所示，這個(gè)回路可由4段路徑組成，邊(a,b)，路徑b到u,邊(u,v)，和路徑v到a。那么，如圖(b)所示，我們可以得到另外一個(gè)更小權(quán)值的貨郎擔(dān)回路如下：邊(a,u)，路徑u到b,邊(b,v)，和路徑v到a，這里路徑u到b是把原路徑b到u反向得到。這個(gè)回路有更小權(quán)值是因?yàn)椋盒禄芈返臋?quán)值=原回路的權(quán)值+w(v,b)+w(a,u)–(w(u,v)+w(a,b))=原回路的權(quán)值+w(v,b)+w(a,u)–(w(u,x)+w(x,v)+w(a,x)+w(x,b))。但由于歐氏距離滿足三角不等式，我們有w(v,b)w(v,x)+w(x,b) //如果相等，必有v=x，或b=x。w(a,u)w(a,x)+w(x,u) //如果相等，必有a=x，或u=x。顯然，上面兩個(gè)不等式不可能同時(shí)成為等式，否則，必有v=a，或u=b。這樣的話，這個(gè)回路經(jīng)過點(diǎn)a或點(diǎn)b兩次，不可能是貨郎擔(dān)回路。因此，必有：新回路的權(quán)值<原回路的權(quán)值。這與原回路為最小貨郎擔(dān)回路矛盾。aabuv(a)xabuv(b)x定理15.4的一個(gè)弱化形式是|C||C*|max{|S||SF}。給出這一弱化形式的簡單證明。證明： 假設(shè)最優(yōu)解C*選中的集合為S1，S2，…，Sh*，這里h*=|C*|。再假設(shè)a1，a2，…，ah*是這些集合依次復(fù)蓋新元素的個(gè)數(shù)。顯然有a1+a2+…+ah*=m,這里m是F中所有集合所包含的不同元素的個(gè)數(shù)，即m=|SεFS|。設(shè)k=max{|S||SF}，因?yàn)閍imax{|S||SF}=k，我們有m≤kh*。再看近似算法的解C。因?yàn)榻扑惴窟x一個(gè)集合，該集合都會(huì)復(fù)蓋至少一個(gè)新元素，所以|C|m。因此有|C|m≤kh*=k|C*|=|C*|max{|S||SF}。圖G(V,E)的一個(gè)割(cut)就是一個(gè)頂點(diǎn)的劃分(S,V-S)，即把V分為兩個(gè)集合S和V-S。所有穿越邊的集合稱為這個(gè)割的邊的集合，記為C(S,V-S)={(u,v)E|uS，vV–S}。假設(shè)圖G(V,E)的邊有正權(quán)值，C(S,V-S)中所有邊的總權(quán)值稱為這個(gè)割的權(quán)值，記為W(S,V-S)。圖G(V,E)的最大割(MAX-CUT)問題就是找出有最大權(quán)值的割。考慮下面隨機(jī)化的近似算法。Randomized-MAX-CUT(G(V,E)) S //S初始化為空集foreachvV vrandomnumber(0or1) //產(chǎn)生0或1的隨機(jī)數(shù)，各占50%槪率 ifv=1 thenSS{v} endifendforreturrnSEnd請證明算法Randomized-MAX-CUT有隨機(jī)近似度2。證明： 我們假定圖G有n個(gè)頂點(diǎn)和m條邊。每個(gè)頂點(diǎn)有1/2的概率被選入S。我們假定每個(gè)頂點(diǎn)的選擇是獨(dú)立的。因此，每條邊(u,v)成為割的邊的概率是：Prob(uS)Prob(vV-S)+Prob(vS)Prob(uV-S)=0.50.5+0.50.5=0.5。所以算法產(chǎn)生的割的權(quán)值的期望值是：E[W(S,V-S)]=(u,v)∈E=(u,v)∈E=0.5(u,v)∈E因?yàn)樽罴呀庵懈畹目倷?quán)值不會(huì)大于所有邊的權(quán)值之和，所以算法的隨機(jī)近似度是E((n,m))(u,v)∈Ewu,v/[0.5(u,v)∈E第14章習(xí)題16中講到裝箱問題(bin-packing)如下。假設(shè)有n個(gè)物體，O1,O2,…,On，需要裝箱。這n個(gè)物體分別有體積si，并且滿足0<si￡1(1in)。假定每個(gè)箱子的容積是1，我們希望用最少的箱子把它們裝入。我們假定任何一組物體，只要它們的總體積不超過1，都可以裝入一個(gè)箱子之中。我們已在這個(gè)習(xí)題中證明了，這個(gè)問題的判斷型問題是NP難問題。假設(shè)S=i=1nFirst-Fit(S[1..n]) //S[i](1in)代表物體Oi，也代表其體積sim1 //到目前為止已啟用的箱子數(shù)C[1]1 //箱子1所余容積B[1] //箱子1已裝物體的集合，開始是空的fori1ton //逐個(gè)檢查物體S[i]，并決定放入哪個(gè)箱子 j1 //從箱子1順序檢查每個(gè)箱子 whileS[i]>C[j] //箱子j所余容積不夠 jj+1 //順序檢查下一個(gè)箱子 endwhile ifj>m //已啟用的箱子中沒有一個(gè)可容納S[i]，j=m+1 then mm+1 //開一個(gè)新箱子，現(xiàn)在m=j了 C[m]1 B[m] endif B[j]B[j]{S[i]} //把物體Oi放入箱子j中 C[j]C[j]–S[i] //更新箱子j的剩余容積endforreturnm,B[1..m] //用了m個(gè)箱子，B[1]到B[m]是各箱子中所裝物體的集合End證明最佳解至少用S個(gè)箱子。證明算法First-Fit結(jié)束時(shí)，最多有一個(gè)箱子有大于或等于0.5的剩余容積，其它箱子所裝物體總?cè)莘e一定大于0.5。證明算法First-Fit是一個(gè)近似度2的近似算法。解：(a) 因?yàn)镾=i=1nsi是所有物體的總?cè)莘e，所用箱子的總?cè)莘e必須大于或等于S。因?yàn)槊總€(gè)箱子的容積是1，所以至少要用用反證法證明。為此，假設(shè)有兩個(gè)箱子Bi和Bj(1≤i<jm)在算法First-Fit結(jié)束時(shí)，有ci>0.5和cj>0.5。顯然，B1到Bm各箱子中至少有一個(gè)物體，否則不會(huì)被啟用。又假設(shè)最后放入箱子Bj中的物體是Ok，那么其容積必有sk<0.5，否則Bj的剩余容積不可能大于0.5。那么，根據(jù)算法，在把Ok放入Bj之前，算法一定先檢查過箱子Bi。因?yàn)樵谒惴‵irst-Fit結(jié)束時(shí)，有ci>0.5，那么在算法為Ok檢查箱子Bi時(shí)，也必定有ci>0.5。這時(shí)，根據(jù)算法，應(yīng)該把Ok放入Bi中，而不應(yīng)放入Bj中。這是一個(gè)矛盾。所以，算法First-Fit結(jié)束時(shí)，最多有一個(gè)箱子有大于或等于0.5的容積為空。由(a)知最佳解C*需要至少S個(gè)箱子，即|C*|S。由(b)知，算法First-Fit使用的箱子數(shù)m滿足關(guān)系0.5(m-1)<S。所以有m<2S+12S+1。因?yàn)閙是整數(shù)，所以有m2S。這也就是說，算法First-Fit的近似度是(n)2S/|C*|2S/S=2。在14章習(xí)題14中曾考慮過兩個(gè)處理器調(diào)度問題?，F(xiàn)在考慮m2個(gè)處理器的調(diào)度問題。我們把這個(gè)優(yōu)化問題再敘述一遍。假設(shè)我們有n個(gè)獨(dú)立的任務(wù)，J1，J2，...，Jn，要從時(shí)間t=0開始在m(2)個(gè)同樣的處理器上執(zhí)行(mn)。假設(shè)Ji(1in)需要Ti(>0)秒的時(shí)間完成并且一旦開始執(zhí)行，必須不中斷地在同一個(gè)處理器上運(yùn)行直至完成。我們希望找到一個(gè)調(diào)度，即任務(wù)安排，使這n個(gè)任務(wù)可以在最短時(shí)間內(nèi)完成，即從t=0開始到任務(wù)全部完成的時(shí)間跨度(makespan)最小。讓我們用M1，M2，...，Mm表示這m個(gè)處理器。假設(shè)我們按以下方法順序安排J1，J2，...，Jn：當(dāng)我們安排Ji時(shí)(1in)，我們順序檢查處理器M1，M2，...，Mm，找到一個(gè)有最早空閑時(shí)刻的處理器Mk時(shí)，把Ji分配給它，并更新它的下一個(gè)空閑時(shí)刻。一開始，所有處理器的空閑時(shí)刻為0。請給出這個(gè)調(diào)度的偽碼，并使之有復(fù)雜度O(nlgm)。證明上面的調(diào)度算法是近似度為2的多項(xiàng)式算法。解：(a) 為方便起見，我們用M[k]表示分配給處理器Mk的任務(wù)集合，用A[k]表示其下一個(gè)最早空閑時(shí)刻，即可用時(shí)刻。輸出變量T是所有任務(wù)完成的時(shí)刻。Multiprocessor-Scheduling(M[1..m],J[1..n],T[1..n])fork1tom M[k] //開始時(shí)，各處理器任務(wù)為空集 A[k]0 //處理器Mk的初始可用時(shí)刻為0endfor //初始化完成H[1..m]A[1..m]Build-Min-Heap(H[1..m],1) //H是個(gè)最小堆，H[i]的關(guān)鍵字是它指向的A[i]fori1ton //逐個(gè)檢查任務(wù)，并分配它一個(gè)處理器 ifH[1]=A[k] then M[k]M[k]{J[i]} //把任務(wù)J[i]分配給Mk A[k]A[k]+T[i] //更新Mk的可用時(shí)刻 Min-Heapify(H[1..m],1) //把堆修復(fù) endifTA[1] //找出所有任務(wù)完成的時(shí)刻fork2tom ifA[k]>T thenTA[k] endifendforreturnT,M[1..m]End算法的主要部分是循環(huán)，一共n次，而每次的主要工作是堆的修復(fù)。因?yàn)槎训男迯?fù)需要O(lgm)時(shí)間，因此算法的復(fù)雜度是O(nlgm)。(b) 現(xiàn)在證明上面的調(diào)度算法是近似度為2的多項(xiàng)式算法。我們注意到，分配給任一個(gè)處理器的任務(wù)會(huì)從t=0開始，一個(gè)接一個(gè)地被順序執(zhí)行，所以任一個(gè)處理器不會(huì)有中間停頓后再工作的情況。假設(shè)最后一個(gè)完成的任務(wù)是Ji(1in)它在時(shí)刻T完成。假設(shè)任務(wù)Ji被分配給處理器Mk。那么它在t’=T–Ti時(shí)刻開始執(zhí)行Ji。我們可斷定，在t=0到t=t’這段時(shí)間內(nèi)，每個(gè)處理器都是在工作的，否則Ji應(yīng)該會(huì)分配給更早結(jié)束任務(wù)的處理器。因此任何一個(gè)最優(yōu)解需要至少t’時(shí)間完成所有任務(wù)。另外，任何最優(yōu)解需要Ti時(shí)間完成任務(wù)Ji，因此最優(yōu)解需要至少max(t’,Ti)時(shí)間完成所有任務(wù)。因?yàn)樯厦嫠惴ㄐ枰臅r(shí)間是T=t’+Ti，所以有近似度(n,m)(t’+Ti)/max(t’,Ti)2。假設(shè)G(V,E)是一個(gè)無向圖。對每個(gè)正整數(shù)k，我們可以定義一個(gè)新的圖G(k)(V(k),E(k))，其中頂點(diǎn)集合V(k)是所有V中頂點(diǎn)的k元組，即V(k)={(v1,v2,...,vk)|viV，1ik}。注意，這里同一頂點(diǎn)可多次出現(xiàn)。集合V(k)中兩點(diǎn)，(v1,v2,...,vk)和(w1,w2,...,wk)之間有邊當(dāng)且僅當(dāng)vi=wi或者(vi,wi)E(1ik)。證明G(k)中最大團(tuán)所含頂點(diǎn)數(shù)是G中最大團(tuán)所含頂點(diǎn)數(shù)的k次方。證明，如果有近似度為常數(shù)的多項(xiàng)式算法求最大團(tuán)，那么就有多項(xiàng)式機(jī)制求最大團(tuán)。證明：(a) 如果G中最大團(tuán)C所含頂點(diǎn)數(shù)是c，那么，由C中頂點(diǎn)組成的所有k元組之間必定有邊，因此這些k元組組成G(k)中一個(gè)團(tuán)。這樣的k元組個(gè)數(shù)為ck，所以G(k)至少含有一個(gè)團(tuán)，它所含頂點(diǎn)數(shù)是G中最大團(tuán)所含頂點(diǎn)數(shù)的k次方。反之，如果G(k)有一個(gè)最大團(tuán)C’，那么，把它的頂點(diǎn)的k元組中的k個(gè)頂點(diǎn)看為k個(gè)分量的話，團(tuán)C’中每個(gè)分量中頂點(diǎn)必定組成G中一個(gè)團(tuán)。因?yàn)镃’是最大團(tuán)，所以每個(gè)分量組成的團(tuán)必定相等，否則不會(huì)最大。另外，這個(gè)由分量組成的G中團(tuán)必定是G中最大的，否則，用G中最大的團(tuán)作分量，可以得到G(k)中比C’更大的團(tuán)。如果有近似度為常數(shù)1+c(c>0)的多項(xiàng)式算法A求最大團(tuán)。我們可以有如下多項(xiàng)式機(jī)制求最大團(tuán)。Max-Clique(G(V,E),)kc/構(gòu)造G(k)(V(k),E(k))調(diào)用多項(xiàng)式算法A求G(k)最大團(tuán)C’取C’中一分量中頂點(diǎn)集合CreturnCEnd我們證明C的近似度是1+。設(shè)最佳解為C*。根據(jù)(a)，G(k)的最大團(tuán)有頂點(diǎn)|C*|k個(gè)。因?yàn)锳的近似度為1+c，所以有|C*|k|C'|1+c。由(a)部分證明知，|C’|=|C|k，我們得到|C*|k|C|k1+c。因此Max-Clique有近似度|C*||C|(1+c)1/k。因?yàn)?1+)k>1+k=1+c/1+c，我們有(1+c)1/k1+。因此Max-Clique有近似度1+。另外，Max-Clique的時(shí)間復(fù)雜度可分析如下。設(shè)算法A有多項(xiàng)式時(shí)間P(n)=O(nh)。這里，n是圖中頂點(diǎn)個(gè)數(shù)，h>0是多項(xiàng)式的階。因?yàn)镚(k)的頂點(diǎn)數(shù)|V(k)|=nk，算法中第2步和第3步的時(shí)間為T(n)=O(nkh)。因?yàn)閗=c/<c/+1，T(n*如果在第10題中的m個(gè)處理器和n個(gè)任務(wù)的調(diào)度算法執(zhí)行之前先把n個(gè)任務(wù)按所需時(shí)間遞減排序，則可使其近似度更好。請證明如果有T1T2...Tn，那么這個(gè)算法有近似度43-13m。這個(gè)算法稱為LPT(LongestProcessingTime)算法。(提示：假設(shè)最佳解需要總共t*時(shí)間，而近似算法產(chǎn)生的調(diào)度中最后一個(gè)完成的任務(wù)是Jk，其處理時(shí)間為Tk。討論兩種情形，Tkt*/3和Tk>t*/3證明： 假設(shè)最佳解需要總共t*時(shí)間，而近似算法產(chǎn)生的調(diào)度中最后一個(gè)完成的任務(wù)是Jk，其處理時(shí)間為Tk。因?yàn)樾蛱柎笥趉的任務(wù)不影響近似解的時(shí)間跨度，我們可以刪去不考慮。設(shè)近似解中Jk開始執(zhí)行的時(shí)刻為sk，那么從t=0到t=sk，所有處理器都是在不停工作中，所以除Jk外的總工作量應(yīng)大于msk，即mski=1kTi-Tk，也就是sk(i=1kTi)/m-Tk/m。因?yàn)槿魏谓?，包括最?yōu)解，其時(shí)間跨度必大于或等于(i=1kTi)/m，下面分兩種情況：如果Tkt*/3，那么近似解的時(shí)間跨度是t=sk+Tk(t*-Tk/m)+Tk=t*+Tk(1-1/m)t*+t*/3-t*/3=4t*/3-t*/3m所以，近似度為(n,m)=t/t*4/3-1/3m。如果Tk>t*/3，那么在最優(yōu)解里面，每個(gè)處理器只能承擔(dān)一個(gè)或兩個(gè)任務(wù)，這是因?yàn)樽钚〉娜蝿?wù)Tk>t*/3。進(jìn)一步，存在一個(gè)最優(yōu)解滿足如下條件：如果一個(gè)處理器順序執(zhí)行兩個(gè)任務(wù)，分別需時(shí)a和b，我們可假定先處理時(shí)間較長的，即ab。如果有一個(gè)處理器只執(zhí)行一個(gè)任務(wù)，需時(shí)c，那么c比有兩個(gè)任務(wù)的處理器中a和b都要大或相等，即cab，否則，可將a和c對調(diào)得更優(yōu)解。如果一個(gè)處理器順序執(zhí)行兩個(gè)任務(wù)，分別需時(shí)ab，而另一個(gè)處理器順序執(zhí)行兩個(gè)任務(wù)，分別需時(shí)cd，并且有ac，那么，必有bd。否則把b和d對調(diào)后得更優(yōu)解。不難看出，滿足以上條件的最優(yōu)解與近似算法產(chǎn)生的解相同，因此，如果Tk>t*/3，那么t/t*=14/3-1/3m。*重新考慮15.8.2節(jié)中任務(wù)均勻分配問題。我們把問題改一下，這次，我們不限定個(gè)人最多可分配的工作量，但要求一個(gè)人最少分到的工作量最大。這是個(gè)最大化問題。證明這個(gè)問題沒有近似度小于2的多項(xiàng)式近似算法，除非P=NP。證明： 我們可以類似地證明。我們把3-SAT問題多項(xiàng)式鴻溝歸約到這個(gè)最大化問題。這個(gè)任務(wù)均勻分配問題的構(gòu)造與15.8.2節(jié)中完全一樣。只不過，在這之上再加一步構(gòu)造。我們以=(xyz)(xyz)(xyz)為例解釋如何把3-SAT問題的一個(gè)實(shí)例多項(xiàng)式鴻溝歸約到這個(gè)最大化的任務(wù)均勻分配問題的一個(gè)實(shí)例。第一步，構(gòu)造與15.8.2節(jié)中完全一樣的任務(wù)均勻分配問題。下面圖(a)描述了對上面實(shí)例進(jìn)行這一步多項(xiàng)式鴻溝歸約后的實(shí)例。=(xyz)(xyz)(xyz)C3x1x2x2x1ax1ax2bx2bx11122y1y2y2y11122ay1ay2by2by1z1z2z2z11122az1az2bz2bz1C11C211(a)用二部圖表示的部分構(gòu)造好的任務(wù)分配問題在這一步構(gòu)造中，如果變量x出現(xiàn)k次，則有k對任務(wù)(xi，xi)被構(gòu)造(1ik)。假設(shè)一共有N對這樣的任務(wù)，那么這樣的任務(wù)一共有2N個(gè)。顯然，如果每個(gè)變量x和它的非x出現(xiàn)相同次數(shù)，那么任務(wù)的個(gè)數(shù)2N就正好等于文字的個(gè)數(shù)，2N=3m，否則，2N>3m。這些任務(wù)中，N個(gè)有工作量2，N個(gè)有工作量1。加上為m個(gè)子句構(gòu)造的任務(wù)C1，C2，…，Cm，任務(wù)總量是3N+m。在這一步中，我們還構(gòu)造了2N個(gè)工人。第二步，為了使每個(gè)工人正好平均能分到工作量2，我們再加上4N-(3N+m)=N-m個(gè)任務(wù)，每個(gè)任務(wù)的工作量為1，并且使每個(gè)工人都能勝任這些新加的任務(wù)。如果用二部圖來表示，這一步的構(gòu)造是在代表任務(wù)這一側(cè)加上p=N-m個(gè)任務(wù)頂點(diǎn)，每個(gè)頂點(diǎn)有權(quán)值1，并與另一側(cè)代表工人的所有點(diǎn)相連。我們用1，2，…，p來表示這些任務(wù)或頂點(diǎn)。顯然，上面的構(gòu)造算法只需多項(xiàng)式時(shí)間?，F(xiàn)在我們證明：這個(gè)3-SAT的實(shí)例可被滿足當(dāng)且僅當(dāng)所構(gòu)造的任務(wù)可分配給工人使每人工作量至少為2。如果這個(gè)3-SAT的實(shí)例不可被滿足，那么無論怎樣分配構(gòu)造的任務(wù)，至少有一人工作量小于等于1。證明：(A) 先證明(1)。假設(shè)這個(gè)3-SAT的實(shí)例可被滿足，我們可以這樣分配任務(wù)：如果變量x=1，那么把任務(wù)xi分配給axi，把任務(wù)xi分配給bxi(1ik)。每個(gè)axi的工作量是1，而每個(gè)bxi的工作量是2(1ik)。反之，如果變量x=0(x=1)，那么把任務(wù)xi分配給axi，把任務(wù)xi+1分配給bxi(1ik-1)，然后把任務(wù)x1分配給bxk。這時(shí)，每個(gè)axi的工作量是2，而每個(gè)bxi的工作量是1(1ik)?？傊?，中賦值為另外，因?yàn)槊恳蛔泳銫中至少有一文字賦值為1，可把任務(wù)C分配給對應(yīng)這一文字的工人，使其總工作量為2。因此，所有任務(wù)可分配完畢使得每人的工作量是1或2。因?yàn)橛衜個(gè)子句，所以有N+m個(gè)工人拿到2個(gè)工作量，有p=N-m個(gè)工人拿到1個(gè)工作量，我們可以把1，2，…，p分配給這p個(gè)人，使每人正好有工作量2?，F(xiàn)在假設(shè)構(gòu)造的任務(wù)可分配完畢使得每人的工作量至少為2，我們證明原3-SAT實(shí)例可滿足。因?yàn)槊咳说墓ぷ髁恐辽?，而總量是4N，所以每個(gè)人必須正好有工作量2。由圖(a)知，在為變量x構(gòu)造的2k個(gè)工人中，每人必須正好得到一個(gè)，除子句對應(yīng)的任務(wù)外，的任務(wù)。這相當(dāng)于書中圖15-3中二部圖的一個(gè)完美匹配。而且，從圖15-3看出，為每個(gè)變量構(gòu)造的圖中，只有兩種完美匹配，要么每個(gè)axi的工作量是1，而每個(gè)bxi的工作量是2(1ik)，或相反。如果每個(gè)axi的工作量是1，我們可以在中賦值x=1，否則為0。這個(gè)賦值可滿足這個(gè)3-SAT實(shí)例，這是因?yàn)槊總€(gè)子句C對應(yīng)的任務(wù)一定分配給了一個(gè)工人，他的工作量，除C外，在圖15.3中是1。因?yàn)?B) 現(xiàn)在證明(2)。如果這個(gè)3-SAT的實(shí)例不可被滿足，由上面證明可知，任何一種任務(wù)的分配中都會(huì)有至少一個(gè)工人的工作量小于2，否則每人的工作量必定為2。那么，由(1)得出，這個(gè)3-SAT的實(shí)例可被滿足，從而矛盾。因?yàn)楣ぷ髁勘仨毷钦麛?shù)，那么必定有一個(gè)工人的工作量等于0或等于1。根據(jù)鴻溝定理，這個(gè)任務(wù)均勻分配問題不存在小于2近似度的多項(xiàng)式算法，除非P=NP。給定一個(gè)加權(quán)的連通圖G(V,E)，最小-最大(min-max)2-樹支撐森林的問題是找出一個(gè)2-樹支撐森林，T1和T2，使得max{W(T1),W(T2)}在所有2-樹支撐森林中是最小的。在第14章習(xí)題23中我們證明了最小-最大2-樹支撐森林的問題是個(gè)NP難問題。請證明以下簡單快捷的多項(xiàng)式算法是這個(gè)問題的一個(gè)近似度為2的近似算法。Min-Max-2-Tree-Spanning-Forest(G(V,E))用Kruskal或Prim算法計(jì)算G(V,E)的一個(gè)最小支撐樹T找出T中有最大權(quán)值的邊eFT–{e}returnFEnd(請注意，這個(gè)算法也是第9章習(xí)題14(a)中的算法。它產(chǎn)生的解不僅是本題的一個(gè)近似度為2的解，同時(shí)也是一個(gè)最小2-樹支撐森林。)證明： 由第9章習(xí)題14(a)知，最小支撐數(shù)MST的權(quán)值等于最小2-樹支撐森林F的權(quán)值加上最大邊，即W(MST)=W(F)+w(最大邊)=W(T1)+W(T2)+w(最大邊)。這里的最大邊指的是MST中的權(quán)值最大的邊。假設(shè)最小-最大2-樹支撐森林的最佳解是{T*1，T*2}。我們有如下關(guān)系：max{W(T1),W(T2)}W(T1)+W(T2)W(T*1)+W(T*2)2max{W(T*1),W(T*2)}。所以，算法Min-Max-2-Tree-Spanning-Forest是最小-最大2-樹支撐森林問題的一個(gè)近似算法，并有近似度2。圖G1(V1,E1)與圖G2(V2,E2)的復(fù)合(composition)得到一個(gè)新的圖G(V,E)，記為G=G1[G2]。其中V=V1V2，即V={(u,v)|uV1,vV2}。另外，V中兩點(diǎn)(u1,v1)，(u2,v2)之間有邊，當(dāng)且僅當(dāng)(u1,u2)E1或者(u1=u2并且有(v1,v2)E2)。注意，圖G中頂點(diǎn)(u,v)是個(gè)無序?qū)Γ?u,v)=(v,u)，但是圖的復(fù)合有順序，G1[G2]G2[G1]。下面是一個(gè)例子的圖示。uu1u2v1v2v3G1G2G1[G2](u1,v1)(u1,v2)(u1,v3)(u2,v1)(u2,v2)(u2,v3)(u1,v1)(u1,v2)(u1,v3)(u2,v1)(u2,v2)(u2,v3)G2[G1]證明，如果圖G1是一個(gè)有h個(gè)頂點(diǎn)的完全圖，那么圖G2可以k-著色，當(dāng)且僅當(dāng)圖G1[G