算法設(shè)計(jì)練習(xí)題

1、算法設(shè)計(jì)練習(xí)題一. 計(jì)算復(fù)雜性1 P184 10.3 設(shè)計(jì)一個(gè)多項(xiàng)式時(shí)間的算法判斷一個(gè)無(wú)向圖G是否是2可著色的算法：2-COLORING輸入：無(wú)向圖G(V, E)輸出：該圖是2可著色的，則輸出yes；否則，輸出no.1. 取任一節(jié)點(diǎn)，標(biāo)記為白色2. 所有與它鄰接的節(jié)點(diǎn)標(biāo)記為黑色3. 對(duì)任意已標(biāo)記的節(jié)點(diǎn)v，將所有與v鄰接且未標(biāo)記的節(jié)點(diǎn)標(biāo)記為與v相反的顏色4. 重復(fù)步驟3，直到不存在與已標(biāo)記節(jié)點(diǎn)鄰接且還未標(biāo)記的節(jié)點(diǎn)5. 如果圖中還有未標(biāo)記的節(jié)點(diǎn)，那么這些節(jié)點(diǎn)一定在一個(gè)新的連通分量中，再選 擇其中一個(gè)節(jié)點(diǎn)標(biāo)記為白色，轉(zhuǎn)到步驟36. 如果得到的圖中，所有鄰接的節(jié)點(diǎn)都標(biāo)記為不同的顏色，則輸出yes；否則

2、，輸出no.End 2-COLORING 時(shí)間復(fù)雜度分析：在n個(gè)頂點(diǎn)和m條邊的圖上進(jìn)行分析，算法的運(yùn)行時(shí)間是2 P185-186 10.16 團(tuán)集問(wèn)題的NP完全性是由可滿足性問(wèn)題歸約到它證明的，給出一個(gè)從頂點(diǎn)覆蓋到團(tuán)集的較簡(jiǎn)單的歸約法1：規(guī)約方法：設(shè)G=（V，E）是連通無(wú)向圖，SV是一個(gè)團(tuán)集當(dāng)且僅當(dāng)是中的一個(gè)頂點(diǎn)覆蓋。證明：設(shè)e=(u,v)是G中的任意邊，SV是一個(gè)團(tuán)集當(dāng)且僅當(dāng)u和v都在S中，即是中的一個(gè)頂點(diǎn)覆蓋。法2：證明：設(shè)G=（V，E）是連通無(wú)向圖，SV是G中的一個(gè)獨(dú)立集，則S是的一個(gè)團(tuán)集，獨(dú)立集poly團(tuán)集。因?yàn)轫旤c(diǎn)覆蓋poly獨(dú)立集，根據(jù)定理10.3，頂點(diǎn)覆蓋poly團(tuán)集。3 P18

3、5-186 10.26 用頂點(diǎn)覆蓋問(wèn)題規(guī)約到集合覆蓋問(wèn)題，證明集合覆蓋問(wèn)題是NP完全問(wèn)題。證明：第一步是說(shuō)明集合覆蓋問(wèn)題是NP的。因?yàn)橐粋€(gè)不確定性算法可以從猜測(cè)一個(gè)集合X的子集族F開(kāi)始，然后驗(yàn)證是否存在F中的k個(gè)子集的并是集合X。第二步證明頂點(diǎn)覆蓋問(wèn)題可以在多項(xiàng)式時(shí)間內(nèi)規(guī)約到集合覆蓋問(wèn)題。設(shè)任意連通無(wú)向圖G=(V,E)，集合X為G中所有與邊相鄰的頂點(diǎn)的集合，其子集族則是每個(gè)頂點(diǎn)與其相鄰的頂點(diǎn)構(gòu)成的子集。集合X是滿足集合覆蓋的當(dāng)且僅當(dāng)X的子集族中存在k個(gè)子集的并是X，當(dāng)且僅當(dāng)G中存在大小為k的頂點(diǎn)覆蓋。4 P215 12.16 證明：設(shè)x1,x2,xn是一個(gè)正實(shí)數(shù)集合。對(duì)于每一個(gè)實(shí)數(shù)xi，我們使

4、它和二維平面中的點(diǎn) (x1,1),(xj,0) | j2,n 相聯(lián)系，這樣，所構(gòu)造的n個(gè)點(diǎn)都位于三角形邊上。如果我們用TRIANGULATION問(wèn)題的任何算法求解構(gòu)造的實(shí)例，輸出將是根據(jù)它們的x坐標(biāo)排序的構(gòu)造點(diǎn)的表，遍歷表并讀出每點(diǎn)的第一個(gè)坐標(biāo)，結(jié)果是排序好的數(shù)。所以，排序問(wèn)題規(guī)約到TRIANGULATION問(wèn)題，排序問(wèn)題是(n logn)，TRIANGULATION問(wèn)題也是(n logn)。5 P215 12.17 證明：設(shè)x1,x2,xn是一個(gè)升序排列的正實(shí)數(shù)集合，及實(shí)數(shù)x。對(duì)于實(shí)數(shù)x及每一個(gè)實(shí)數(shù)xi，我們使它和二維平面中的點(diǎn)(x,0),(xi,0) | i1,n 相聯(lián)系，這樣，所構(gòu)造的點(diǎn)

5、都位于x軸上。如果我們用NEAREST POINT問(wèn)題的任何算法求解，輸出就是二分搜索要查找的數(shù)。所以，二分搜索問(wèn)題規(guī)約到NEAREST POINT問(wèn)題，二分搜索問(wèn)題是(logn)，NEAREST POINT問(wèn)題也是(logn)。6 P215 12.18證明：設(shè)x1,x2,xn是一個(gè)正實(shí)數(shù)集合，對(duì)于每一個(gè)實(shí)數(shù)xi，我們構(gòu)造點(diǎn)(xi,0)與之對(duì)應(yīng)，于是這些點(diǎn)在x軸上。如果我們用ALL NEAREST POINT問(wèn)題的任何算法求解，輸出將是每個(gè)點(diǎn)(xi,0)對(duì)應(yīng)的最近點(diǎn)對(duì)(xi,0)，(xj,0)。所以，CLOSEST-PAIR問(wèn)題規(guī)約到ALL NEAREST POINT問(wèn)題，CLOSEST-PA

6、IR問(wèn)題是(n logn)，ALL NEAREST POINT問(wèn)題也是(n logn)。二. 隨機(jī)算法1 P241 14.2 假定你有一枚硬幣，請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的隨機(jī)算法用來(lái)生成整數(shù)1,2.n的隨機(jī)排列，n為正整數(shù)，分析你的算法的時(shí)間復(fù)雜性?；舅枷耄簭目招蛄虚_(kāi)始，逐個(gè)向序列添加1, 2, , n。根據(jù)二分搜索的思想，并利用多次拋硬幣，來(lái)隨機(jī)確定每個(gè)添加的數(shù)在序列中的位置。算法 RANDOMIZE2 輸入：正整數(shù)n 輸出：1, 2, , n的一個(gè)隨機(jī)排列。 A1=1 for i=2 to n j=randombisearch(1, i-1)/在數(shù)組A中隨機(jī)確定i的插入位置。 insert(A ,

7、 j, i) /在數(shù)組A的j位置上插入值i。 end for output A1.n end RONDOMIZE2 過(guò)程 randombisearch(low, high)/ 利用二分搜索在Alow.high+1中隨機(jī)確定值i的插入位置，/ 并返回該位置。if low>high then return lowelse mid= k=random(1,2) /拋一次硬幣。 if k=1 then high=mid-1 /插入位置在Alow.mid中。 else low=mid+1 /插入位置在Amid+1.high+1中。 return randombisearch(low, high)e

8、nd if end randombisearch時(shí)間復(fù)雜性：(n2) 2 P241 14.5 在算法RANDOMIZEDQUICKSORT的討論中曾說(shuō)過(guò)，為算法QUICKSORT得到一個(gè)O（log n）期望時(shí)間的一種可能性，是通過(guò)排列輸入元素使它們的次序變成隨機(jī)的來(lái)獲得的。描述一個(gè)O（n）時(shí)間算法，先隨機(jī)排列下算法思想：對(duì)預(yù)排序的數(shù)組進(jìn)行隨機(jī)排列，使該數(shù)組與原先相比顯得無(wú)序。盡量避免QUICKSORT算法最壞情況的發(fā)生即n2時(shí)間，使之更趨近于最佳情況nlogn時(shí)間。算法PRE_DISPOSE輸入：n個(gè)元素的數(shù)組a1n輸出：隨機(jī)排列的數(shù)組a for i=1 to n P =random(n)/隨

9、機(jī)選擇小于n的數(shù) Q=random(n) /隨機(jī)選擇小于n的數(shù) 互換aP和aQ end forend PRE_DISPOSE3 P241 14.7 考慮對(duì)算法BINARYSERCH做如下修改見(jiàn)1.3節(jié)，在每次迭代中，隨機(jī)的選擇剩下的位置來(lái)代替搜索區(qū)間減半設(shè)元素存儲(chǔ)在一維數(shù)組C中，第0個(gè)位置不放元素，若每次生成的隨機(jī)數(shù)都是要查找的剩余元素的第一個(gè)且未找到要搜索的數(shù)，則時(shí)間復(fù)雜度計(jì)算公式如下：計(jì)算得到時(shí)間復(fù)雜度為4 寫(xiě)出n皇后問(wèn)題的如下隨機(jī)算法：先在棋盤(pán)上隨機(jī)放置m(m<n)個(gè)互不沖突的皇后，然后用回溯法搜索其余皇后的位置。算法 NQUEENS_RAN_ACCU輸入：正整數(shù)n,m，其中n表示

10、棋盤(pán)緯度，m表示隨機(jī)算法和回溯算法的處理的 劃分， m<n。輸出：若找到解，則輸出n皇后問(wèn)題的一個(gè)解x1.n,否則輸出無(wú)解Flag_Random=true /隨機(jī)查找時(shí)是否有解得標(biāo)記Flag_Accu=false/精確查找時(shí)是否有解得標(biāo)記k=1 xm+1=0/精確查找初始化while k<=n and Flag_Random if k<=m/隨機(jī)算法 j=0for i=1 to n /尋找第k行所有可放置皇后的位置。 if place(k) then /若第k行的位置i可放置皇后, j+; tempj=i; /則存儲(chǔ)該位置。 end if end for if j>0

11、then xk=temprandom(1, j) /隨機(jī)選取一個(gè)位置放皇后 else Flag_Random =false/表示找不到解 end if k+ else if k>m/回溯算法 while k>m and not Flag_Accu while xk< n and not Flag_Accu xk=xk+1 /試將第k行的皇后移到下一個(gè)位置。 if place(k) then /第k行的當(dāng)前位置可放置皇后。 if k=n then Flag_Accu =true /xm+1.n是一個(gè)解 else /xm+1.k是精確解答時(shí)的部分解 k=k+1 /前進(jìn)到下一行 x

12、k=0 end if end if /否則，剪枝 end while k=k-1/回溯 end while if k =m break; /退出整個(gè)循環(huán) end ifend whileif Flag_Random and Flag_Accu then output x /輸出一個(gè)解 else output “No solution”/輸出無(wú)解三. 近似算法1 對(duì)于裝箱問(wèn)題，分別寫(xiě)出近似算法FF和BF。思路:1.最先適配法(FF)：箱子編號(hào)為1, 2, , n，初始時(shí)各箱子為空。各項(xiàng)按u1, u2, , un的順序裝箱，裝項(xiàng)ui時(shí)，將其裝入序號(hào)最小的可容得下該項(xiàng)的箱子中（即裝入滿足l<=

13、1-si的序號(hào)最小的箱子中，其中l(wèi)表示箱子的已填充容量）。 2.最佳適配法(BF)：箱子編號(hào)為1, 2, , n，初始時(shí)各箱子為空。各項(xiàng)按u1, u2, , un的順序裝箱，裝項(xiàng)ui時(shí)，將其裝入滿足l<= 1-si并且使l值最大的箱子中。算法FF輸入: n個(gè)項(xiàng)的集合u1n, n個(gè)箱子的容量l1n，其中0<=ui<=1，li=1.輸出: 裝這n個(gè)項(xiàng)的最少箱子的個(gè)數(shù)k k=1;/箱子的個(gè)數(shù) for i=1 to n/裝項(xiàng)ui時(shí)，將其裝入序號(hào)最小的可容得下該項(xiàng)的箱子中 j=1 flag=false; while j<=k and not flag/從序號(hào)最小的開(kāi)始查找 if

14、lj>ui then/找到可以放進(jìn)去的箱子 lj=lj-ui flag=true; else j+/繼續(xù)尋找 end if end while if not flag then/沒(méi)有找到可以放進(jìn)去的箱子 k+/開(kāi)啟新的箱子 lk=lk-ui; end if end for return kend FF算法BF 輸入: n個(gè)項(xiàng)的集合u1n, n個(gè)箱子的容量l1n，其中0<=ui<=1，li=1. 輸出:裝這n個(gè)項(xiàng)的最少箱子的個(gè)數(shù)k k=1;/箱子的個(gè)數(shù) for i=1 to n/裝項(xiàng)ui時(shí)，將其裝入滿足l<= 1-si的箱子中使l值最大的箱子中 if lj>ui t

15、hen/找到l值最大的可以放進(jìn)去的箱子 lj=lj-ui elsek+/開(kāi)啟新的箱子 lk=lk-ui; end ifsort(l1k)/對(duì)前k個(gè)箱子的l值從大到小排序 end for return k end BF2 P255 15.10V1V2如圖：V3V4按照算法，先得到頂點(diǎn)的度數(shù)降序排列：V1、V2、V3、V4（度數(shù)均為2），先將V1添加到覆蓋中，刪除邊 V1 ，V4和 V1，V2，接著添加V2，刪除邊 V2，V3，添加V3，刪除邊 V3，V4。故得覆蓋 V1，V2，V3，而最佳覆蓋為 V1，V3或 V2，V4。3 P256 15.14 15.15（這兩題的答案是學(xué)長(zhǎng)給的）15.14考

16、慮在給定的圖G中找出最大團(tuán)集問(wèn)題的近似算法，基本步驟：1、 C=2、 向C中添加一個(gè)頂點(diǎn)（該頂點(diǎn)不在C中，與C中每個(gè)頂點(diǎn)相連接）3、 重復(fù)步驟2，直到C=G 或者G-C中任一點(diǎn)x與C中點(diǎn)都不是全部相連Solution:這里取,。則題目算法尋求最大團(tuán)集，這是最大化問(wèn)題，近似度分三種情況討論：若若是由個(gè)無(wú)向完全圖：之簡(jiǎn)單并，則=。上式個(gè)頂對(duì)于不是由、討論的無(wú)向圖，則可以去掉一些邊，這些邊及跟這些邊相連的頂點(diǎn)不構(gòu)成圖的完全子圖，最后圖分解成獨(dú)立的“較小”的無(wú)向圖（即團(tuán)集）的簡(jiǎn)單并。轉(zhuǎn)為討論的情形。結(jié)論：這個(gè)近似算法可能達(dá)到的近似度具有如下形式：， =，。 1515證明練習(xí)15.14中給出的查找最大團(tuán)

17、集問(wèn)題的啟發(fā)式算法的近似度是無(wú)界的。證明：反證法：假定該啟發(fā)式算法的近似度是有界的，則由于的任意性，構(gòu)造如下：設(shè)是一個(gè)具有6個(gè)頂點(diǎn)的無(wú)向完全圖，是 具有3個(gè)頂點(diǎn)的無(wú)向完全圖，取,顯然，且由于是近似算法，不可能輸出的都是具有個(gè)頂點(diǎn)的團(tuán)集,故而：導(dǎo)出矛盾！4 P256 15.16給出著色問(wèn)題的一個(gè)近似算法:找出給一個(gè)無(wú)向圖著色,使得相鄰頂點(diǎn)著不同顏色的最少顏色數(shù)。證明或否定該算法的近似度是有界的算法思想：對(duì)無(wú)向圖進(jìn)行分類(lèi)討論算法：COLORING輸入：無(wú)向圖G(V,E)輸出：著色的顏色數(shù)if V=0 then return 0 end ifif E=0 then return 1 end ifif G是二分圖 return 2 end ifelse return 4end ifend COLORING證明：在上述算法A中，在V=0，E=0， G是二分圖情況都屬于最優(yōu)解，所以其RA(I)=1;而只有else語(yǔ)句不是最優(yōu)解，因?yàn)樵趀lse語(yǔ)句中出現(xiàn)的情況不是3可著色就是4可著色的，任何一個(gè)圖形并不都滿足3可著色，3著色是NP完全問(wèn)題,但是任何一個(gè)平面圖G都是4可著色的，所以這時(shí)我們返回4，即 A(I)=4, OPT(I)=3 RA(I)=A(I)/OPT(I)=4/3 所以1<=RA(I)<=4/3該算法的近似度是有