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

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

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

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

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

6、IR問題是(n logn)，ALL NEAREST POINT問題也是(n logn)。二. 隨機算法1 P241 14.2 假定你有一枚硬幣，請設(shè)計一個有效的隨機算法用來生成整數(shù)1,2.n的隨機排列，n為正整數(shù)，分析你的算法的時間復(fù)雜性。基本思想：從空序列開始，逐個向序列添加1, 2, , n。根據(jù)二分搜索的思想，并利用多次拋硬幣，來隨機確定每個添加的數(shù)在序列中的位置。算法 RANDOMIZE2 輸入：正整數(shù)n 輸出：1, 2, , n的一個隨機排列。 A1=1 for i=2 to n j=randombisearch(1, i-1)/在數(shù)組A中隨機確定i的插入位置。 insert(A ,

7、 j, i) /在數(shù)組A的j位置上插入值i。 end for output A1.n end RONDOMIZE2 過程 randombisearch(low, high)/ 利用二分搜索在Alow.high+1中隨機確定值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時間復(fù)雜性：(n2) 2 P241 14.5 在算法RANDOMIZEDQUICKSORT的討論中曾說過，為算法QUICKSORT得到一個O（log n）期望時間的一種可能性，是通過排列輸入元素使它們的次序變成隨機的來獲得的。描述一個O（n）時間算法，先隨機排列下算法思想：對預(yù)排序的數(shù)組進行隨機排列，使該數(shù)組與原先相比顯得無序。盡量避免QUICKSORT算法最壞情況的發(fā)生即n2時間，使之更趨近于最佳情況nlogn時間。算法PRE_DISPOSE輸入：n個元素的數(shù)組a1n輸出：隨機排列的數(shù)組a for i=1 to n P =random(n)/隨

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

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

11、then xk=temprandom(1, j) /隨機選取一個位置放皇后 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行的皇后移到下一個位置。 if place(k) then /第k行的當前位置可放置皇后。 if k=n then Flag_Accu =true /xm+1.n是一個解 else /xm+1.k是精確解答時的部分解 k=k+1 /前進到下一行 x

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

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

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

15、hen/找到l值最大的可以放進去的箱子 lj=lj-ui elsek+/開啟新的箱子 lk=lk-ui; end ifsort(l1k)/對前k個箱子的l值從大到小排序 end for return k end BF2 P255 15.10V1V2如圖：V3V4按照算法，先得到頂點的度數(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é)長給的）15.14考

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

17、集問題的啟發(fā)式算法的近似度是無界的。證明：反證法：假定該啟發(fā)式算法的近似度是有界的，則由于的任意性，構(gòu)造如下：設(shè)是一個具有6個頂點的無向完全圖，是 具有3個頂點的無向完全圖，取,顯然，且由于是近似算法，不可能輸出的都是具有個頂點的團集,故而：導(dǎo)出矛盾！4 P256 15.16給出著色問題的一個近似算法:找出給一個無向圖著色,使得相鄰頂點著不同顏色的最少顏色數(shù)。證明或否定該算法的近似度是有界的算法思想：對無向圖進行分類討論算法：COLORING輸入：無向圖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ōu)解，因為在else語句中出現(xiàn)的情況不是3可著色就是4可著色的，任何一個圖形并不都滿足3可著色，3著色是NP完全問題,但是任何一個平面圖G都是4可著色的，所以這時我們返回4，即 A(I)=4, OPT(I)=3 RA(I)=A(I)/OPT(I)=4/3 所以1<=RA(I)<=4/3該算法的近似度是有