算法習(xí)題答案第3章貪心

1算法設(shè)計與分析習(xí)題第三章貪心算法高興宇23.1

Kruskal算法中判定新增一條邊是否構(gòu)成回路的問題可以用集合運(yùn)算實現(xiàn)：(1)Unite(T1,T2)：將圖G的兩個連通分支T1、T2合并，所得結(jié)果為新的連通分支T；(2)Find(v)：返回節(jié)點v所在的連通分支；如果Unite()、Find()已經(jīng)定義，則Kruskal算法中對當(dāng)前邊e取舍與否的處理如下：S1：對e=<a,b>，如果Find(a)=Find(b)，則新增邊e將形成回路，舍棄；S2：否則實施增加邊e的操作：添加e并執(zhí)行Unite(Find(a),Find(b))；3問題1：按照以上描述，寫出Kruskal算法的偽語言描述。

解：Kruskal算法的偽語言描述如下：S1：對G的邊按照權(quán)進(jìn)行遞增排序，得e1,e2,…,em，滿足w(ek)≤w(ek+1),k=1,2,…,m-1；S2：初始化操作：確定每個節(jié)點所在連通分支，T=,g=0,t=0,k=1，并且對于所有的Find(ai)，都有：Find(ai)=i,i=0,1,…,n-1。S3：對于ek的兩個頂點ak,bk，如果Find(a)=Find(b)，則k=k+1，轉(zhuǎn)S3；

S4：T=T{ek},Unite(Find(a),Find(b)),t=t+1,g=g+w(ek+1),k=k+1；S5：如果t<n-1則轉(zhuǎn)S3；

S6：輸出T,g，終止。

4問題2：在初始化中，如何確定每個節(jié)點所在的連通分支？解：初始化時，認(rèn)為每個節(jié)點都處在相互孤立的連通分支里面，即Find(ak)=k。問題3：實現(xiàn)Find()、Unite()的時間復(fù)雜度是多少？解：實現(xiàn)Unite()的時間復(fù)雜度為O(n)；實現(xiàn)Find()的時間復(fù)雜度要根據(jù)存儲圖G連通分支的數(shù)據(jù)結(jié)構(gòu)來確定，如果是數(shù)組則為O(1)。53.2設(shè)連通無向圖G采用鄰接矩陣表示，V(G）={1,2,…,n}。按照習(xí)題1的提示，寫出Kruskal算法的實現(xiàn)代碼（包括Unite()、Find()的實現(xiàn)）。3.3設(shè)連通無向圖G采用鄰接表表示。按照習(xí)題1的提示，寫出Kruskal算法的實現(xiàn)代碼（包括Unite()、Find()的實現(xiàn)）。3.4算法3.2的實現(xiàn)中最小生成樹采用(n-1)

2維數(shù)組表示。請改寫這段實現(xiàn)代碼，其中最小生成樹也用鄰接矩陣表示。63.5設(shè)連通無向圖G采用鄰接表表示，寫出求最小生成樹Prim算法的實現(xiàn)代碼。解：設(shè)G=<V,E,w>,V={v1,v2,…,vn},E={e1,e2,…,em}，鄰接表為Neighbor[1..n]。S1：初始化：取v=v1,T={v},g=0,V=V–{v}；S2：在Neighbor[T]中尋找vk，且min(w(vi,vk))最小，記e=<vj,vk>，這里vj等于使min(w(vi,vk))取最小值的vi，viT；S3：T=T{e},V=V–{vj},g=g+w(vj,vk)；S4：如果V則轉(zhuǎn)S2；S5：輸出T,g，終止。73.6連通無向圖G各邊權(quán)互不相同，e是圖G的最小權(quán)邊，證明e必在G的任意最小生成樹中出現(xiàn)。證明：記T是G的最小生成樹，且eE(T)?，F(xiàn)在將e加入T中，因為T是生成樹，所以加入e后T+{e}中一定存在回路，設(shè)回路為L，現(xiàn)在將回路L中的另外一條邊e′刪除，則T+{e}-{e′}也是G的一棵生成樹，因G各邊權(quán)互不相同且e是圖G的最小權(quán)邊，顯然w(T+{e}-{e′})<w(T)，這與T的定義矛盾，得證。83.7連通無向圖G各邊權(quán)互不相同，e是G中某個回路上的最大權(quán)邊，證明G′=<V,E-|e|>必有一棵最小生成樹T，T同時也是G的最小生成樹。證明：因為e是G中某個回路上的邊，所以G′=<V,E-|e|>仍然是連通圖，則G′一定有最小生成樹，記為T。然后由定理3.1引理（對G中任一基本回路C，則C中權(quán)最大的邊e不在G的最小生成樹中）可得，T同時也是G的最小生成樹。93.8如果T、T′都是圖G的最小生成樹，分別將T、T′中各邊按權(quán)排列，證明所得兩序列各項權(quán)相等。

證明：設(shè)w(T)表示樹T的總權(quán)值，則顯然w(T)=w(T′)。下面用數(shù)學(xué)歸納法證明：(1)當(dāng)圖G只有一條或兩條邊時，命題顯然成立。(2)假設(shè)當(dāng)圖G中有K(K≥2)條邊時命題依然成立，即對于T和T′中各邊權(quán)序列有ej=ej′，其中0≤j≤K。

10討論有K+1條邊的情況。設(shè)nT和nT′為新的最小生成樹。分為兩種情況討論：(1)當(dāng)G-nT和G-nT′有公共邊時，則圖G中含有回路，取該回路中權(quán)值最大的一條邊e，由定理3.1引理(對G中任一基本回路C，C中權(quán)最大的邊e不在G的最小生成樹中可知，e不在nT和nT′中，則nT和nT′也是G-e的最小生成樹，這就變?yōu)榱薑條邊的情況，由假設(shè)知nT和nT′中各邊權(quán)值按序相等。(2)當(dāng)G-nT和G-nT′沒有公共邊時，設(shè)圖G的頂點數(shù)為v，則圖G中有且僅有2(v-1)條邊，即nT+nT′=E，E為圖G的邊集，不然G-nT和G-nT′將會有公共邊。則圖G任意相鄰的兩點之間將有兩條邊，并且一條在nT中一條在nT′中。如圖所示：11如果a和a′的權(quán)值不等，b和b′中權(quán)值不等，則可以這樣選取生成樹：取a和a′中的權(quán)值較小邊，取b和b′中權(quán)值較小邊，這樣可得到一棵新的樹rT，顯然rT的權(quán)值小于等于nT和nT′的權(quán)值，僅當(dāng)a和a′的權(quán)值相等，b和b′中權(quán)值相等。rT的權(quán)值才會與nT和nT′的權(quán)值相等，否則rT才是最小生成樹，這與nT和nT′的最小生成樹的假定矛盾。于是得出當(dāng)變數(shù)為K+1時，nT和nT′各邊權(quán)值按序相等。綜合以上得知命題成立。123.9修改Dijkstra算法的實現(xiàn)代碼，使之能夠求源點到指定點的最短路徑。

3.10G=<V,E>是一個單源有向圖，如果其中邊權(quán)有負(fù)數(shù)，Dijkstra算法的正確性如何？如果需要更改，試寫出修改后的實現(xiàn)代碼。解：如果權(quán)為負(fù)數(shù)是合法的，顯然如果邊權(quán)有負(fù)數(shù)，Dijkstra算法返回結(jié)果的正確性將會下降。在錯誤僅僅是正負(fù)符號錯誤而絕對值正確的情況下，在使用邊權(quán)值時取其絕對值。133.11G=<V,E>是一個單源有向圖，邊e=<u,v>表示節(jié)點u到v的信道，p(u,v)表示節(jié)點u到v信道故障概率(0≤p(u,v)≤1)。設(shè)各信道故障概率都是獨立的，設(shè)計一個算法求源點到指定點的最可靠信道。

解：同3.9，只不過權(quán)值是概率值，并且源點v0到點v的權(quán)重是所經(jīng)路徑各信道故障概率的乘積，即：dj=min{dj,dk

p(k,j)},初始化時源點v0到不相鄰點v

間的dv=1（不連通相當(dāng)于故障概率為1）。最后，同樣是求源點到指定點的最小值。143.12對于背包問題可以考慮兩種貪心選擇：(1)總是選擇當(dāng)前能夠裝入B中的最大價值物品裝入；(2)按照ci/ai大小選擇當(dāng)前能夠裝入B中的物品；

問題1：分別按以上兩種貪心選擇策略寫出求解算法，并對解的精確性進(jìn)行討論。

問題2：一般背包問題：解向量：x=<x1,x2,…,xn>取值修改為0≤xi≤1(i=1,2,…,n)，重新按以上兩種貪心選擇策略寫出求解算法，并對解的精確性進(jìn)行討論。15分析：對于0-1背包問題，不能使用貪心算法，因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。而背包問題就可考慮貪心算法。用貪心法解決背包問題的基本步驟是，首先計算每種物品單位重量的價值，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位價值次高的物品盡可能多的裝入背包。依此策略一直執(zhí)行下去，直到背包裝滿為止。解：算法具體描述如下：

typedefstruct{floatw;//重量

floatv;//物品價值

inti;//物品的序號

}noded[5];16Floatknapsack(noded[5],floatc){//對各種物品依照單位重量的價值從小到大排序；

floatopt=0,x[5];inti;for(i=0;i<5;i++)x[i]=0;//初始化，0代表沒有選中，1代表選中

for(i=0;i<5;i++){if(d[i].w>c)break;x[d[i].i]=1;Opt+=d[i].v;C-=d[i].w;}if(i<5)//不能將物品裝入多次{x[d[i].i]=c/d[i].w;opt+=x[d[i].i]*d[i].v;}returnopt;}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從小到大排序。因此，算法的計算時間上限為O(nlogn)。173.13硬幣找兌問題：設(shè)硬幣面值分別為100分，50分，20分，10分，5分，1分，如果要求找兌n分錢，求使用硬幣枚數(shù)最少的方法。設(shè)計求解該問題的算法并且證明你的算法是最優(yōu)的。

分析：用貪心算法求解：每次總是選取當(dāng)前能夠使用的最大面值的硬幣，直到總面值和為n。

貪心算法：總是作出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題它能產(chǎn)生整體最優(yōu)解。但其解必然是最優(yōu)解的很好近似解。貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。該算法存在問題：

1.不能保證求得的最后解是最佳的；

2.不能用來求最大或最小解問題；

3.只能求滿足某些約束條件的可行解的范圍。18實現(xiàn)該算法的過程：從問題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do

求出可行解的一個解元素；由所有解元素組合成問題的一個可行解；貪心算法的基本要素：1.貪心選擇性質(zhì)：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。（與動態(tài)規(guī)劃的主要區(qū)別）2.采用自頂向下，以迭代的方式作出相繼的貪心選擇，每作一次談心選擇就將所求問題簡化為一個規(guī)模更小的子問題。3.對于一個具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的最優(yōu)解。通?？梢允紫茸C明問題的一個整體最優(yōu)解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優(yōu)解。19貪心算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪心算法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間。貪心算法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪心算法不要回溯。例如平時購物找錢時，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪心算法。這種方法在這里總是最優(yōu)，是因為銀行對其發(fā)行的硬幣種類和硬幣面值的巧妙安排。對于美國的硬幣體系{1,5,10,25}，它總能產(chǎn)生出最優(yōu)的解法。然而對于其他體系，如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪心算法，應(yīng)找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優(yōu)的解應(yīng)是3個5單位面值的硬幣。20解：硬幣找兌問題用貪心算法來求解。具體算法如下：

intdollar(intn;intm[6]){intt=0;for(inti=0;i<6;i++){while(n>=m[i]){n=n-m[i];t++;}}}

注意：常犯的錯誤是將while循環(huán)寫成了多個if語句。213.14設(shè)有n個磁盤文件f1,f2,…,fn，每個文件占用一個磁盤。文件fi的檢索概率為pi，且。磁頭從當(dāng)前磁道移動到被檢索信息磁道需要的時間與這兩個磁道之間的徑向距離成正比。如果文件fi位于第i道，則檢索這n個文件的期望時間是，其中dij是磁道從第i道移動到第j道需要的時間。設(shè)計一個算法來安排這n個文件在磁盤上的位置，使得檢索這n個文件的期望時間最小。解：把檢索概率大的文件安排在相鄰的磁道，并且將文件按檢索概率降序排列，概率最大的安排在最中間磁道，其余的文件分列其兩邊。

223.15套匯是指利用若干貨幣兌換率的差異來牟利的行為。如果1美元買0.7英鎊，1英鎊買9.5法郎，1法郎買0.16美元，則通過1美元買入，得到0.7×9.5×0.16=1.064美元。從而獲利6.4%。設(shè)已知有可以互相兌換的n種貨幣c1,c2,,cn，其兌換表為R=(rij)nn，其中rij表示1個單位的貨幣ci可以買到的貨幣cj的數(shù)量，初始資金為V。

問題1：設(shè)計一個有效算法，用于確定是否存在一個貨幣序列ci1,ci2,,cin，使得：ri1,i2

ri2,i3rik,i1>1(1<k≤n)23與求解單源最短通路問題Dijkstra算法思想相似，只不過這里所求的是最大值。將貨幣集分為兩個子集C=S