《算法設(shè)計(jì)與分析》第06章.ppt

《《算法設(shè)計(jì)與分析》第06章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》第06章.ppt（112頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,第2部分 算法設(shè)計(jì)策略,6.1 一般方法 6.2 背包問(wèn)題 6.3 帶時(shí)限的作業(yè)排序 6.4 最佳合并模式 6.5 最小代價(jià)生成樹(shù) 6.6 單源最短路徑 6.7 磁帶最優(yōu)存儲(chǔ) 6.8 貪心法的基本要素,第6章 貪心法,最優(yōu)化問(wèn)題（optimization problems）是指這樣一類問(wèn)題，問(wèn)題給定某些約束條件（constraint），滿足這些約束條件的問(wèn)題解稱為可行解（feasible solution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問(wèn)題還給出了某個(gè)數(shù)值函數(shù)，稱為目標(biāo)函數(shù)（objective function），使目標(biāo)函數(shù)取最大（或最小）值的可行解稱為最優(yōu)解（op

2、timal solution）。,6.1 一般方法,貪心法是通過(guò)分步?jīng)Q策（stepwise decision）的方法來(lái)求解問(wèn)題的。 貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)（optimization criterion）。 在根據(jù)最優(yōu)量度標(biāo)準(zhǔn)選擇分量的過(guò)程中，還需要使用一個(gè)可行解判定函數(shù)。 貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當(dāng)前看似最佳選擇，必須進(jìn)一步證明該算法最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。,貪心技術(shù)(Greedy Technique),某一問(wèn)題的n個(gè)輸入,該問(wèn)題的一種解（可行解）,是A的一 個(gè)子集,滿足一定 的條件,約束條件,目標(biāo)函數(shù),取極值,最優(yōu)解,【程序6

3、1】貪心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;in;i+) SType x=Select(a); if (Feasiable(solution,x) solution=Union(solution,x); return solution; ,7,找零錢(qián)問(wèn)題(change-making problem),用當(dāng)?shù)孛骖~為d1d2dm的最少數(shù)量的硬幣找出金額為n的零錢(qián)。 如d1=25,d2=10,d3=5,d4=1，n=48 該問(wèn)題的一個(gè)解是： 1個(gè)25，2個(gè)10，3個(gè)1，且該解是最優(yōu)的。 這種

4、方法稱為貪心法，建議通過(guò)一系列步驟來(lái)構(gòu)造問(wèn)題的解，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問(wèn)題的完全解。 必須滿足：可行、局部最優(yōu)、不可取消,8,又如：d1=11,d2=5,d3=1,n=15 該問(wèn)題的一個(gè)解是： 1個(gè)11，4個(gè)1，該解不是最優(yōu)的。 最優(yōu)解：3個(gè)5 本質(zhì)上由硬幣面值種類決定（問(wèn)題其本身固有的特點(diǎn)） 。,貪心策略最優(yōu)解的證明,基本思想 設(shè)X=x1,x2,.,xn為貪心策略得到的解 設(shè)Y=y1,y2,.,yn為該問(wèn)題的最優(yōu)解 很明顯，XY，如果成立，則不用證明了。 證明過(guò)程： 依次比較X和Y中的每個(gè)元素，如果發(fā)現(xiàn)不一樣，則用X中的替換Y中相應(yīng)元素，比較完后得到一個(gè)新的解Y=X

5、此時(shí)，如能證明Y的最優(yōu)值就是Y的最優(yōu)值或者比Y還好，則說(shuō)明X就是最優(yōu)解。,問(wèn)題 對(duì)容量為M的背包進(jìn)行最佳裝載的問(wèn)題。,6.2 背包問(wèn)題,6.2.1 問(wèn)題描述,已知一個(gè)載重為M的背包和n件物品，第i件物品的重量為 wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi0，pi0，0in。所謂背包問(wèn)題是指求一種最佳裝載方案，使得收益最大。所以，背包問(wèn)題是現(xiàn)實(shí)世界一個(gè)常見(jiàn)的最優(yōu)化問(wèn)題。 兩類背包問(wèn)題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為 0/1背包問(wèn)題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問(wèn)題或簡(jiǎn)稱背包問(wèn)題。,6.2.2 貪心法求解,背

6、包問(wèn)題 背包問(wèn)題的解可以表示成一個(gè)n-元組：X=(x0,x1,xn1)，0 xi1，0in，每個(gè)xi是第i件物品裝入背包中的部分。 判定可行解的約束條件是：,背包問(wèn)題的最優(yōu)解必須使下列目標(biāo)函數(shù)取最大值：,例61 設(shè)有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15)。,背包問(wèn)題(Knapsack Problem),方案1：按物品價(jià)值降序裝包,方案2：按物品重量升序裝包,方案3：按物品價(jià)值與重量比值的降序裝包,【程序62】背包問(wèn)題的貪心算法 template class Knapsack publ

7、ic: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n; ;,template void Knapsack:GreedyKnapsack(float* x) /前置條件：wi已按pi/wi的非增次序排列 float u=m; for (int i=0;iu) break; xi=1.0; u=u-wi; if (i=n) xi=u/wi; ,6.2.3 算法正確性,定理61 如果p0/w0p1/w1pn1/wn1，則

8、程序62求得的背包問(wèn)題的解是最優(yōu)解。,證明： 設(shè)X=(x0, x1, , xn-1)， 0 xj 1 ,0in是貪心背包算法所生成的貪心解。 如果所有的xi都等于1,則顯然X就是問(wèn)題的最優(yōu)解。否則， 設(shè)j是使xi1的最小下標(biāo)。由算法的執(zhí)行過(guò)程可知， 解的形式為： X=(1, , 1,xj,0, , 0) 即xi=1 0ij, 0 xj 1,xi=0 jin-1,假設(shè)Y是問(wèn)題的最優(yōu)解：Y=(y0, y1, , yn-1) 且有： 若X Y，則X就是最優(yōu)解。否則， X和Y至少在1個(gè)分量上存在不同。 設(shè)k是使得yk xk的最小下標(biāo)，則有yk xk?？煞忠韵虑闆r說(shuō)明： a) 若kj，則xk=1。因?yàn)閥

9、k xk,從而有yk xk b) 若k=j，由于 ，且對(duì)1ij，有yi=xi=1,而對(duì)jin,有xi0；故此時(shí)若ykxk，則將有 ，與Y是可行解相矛盾。而yk xk,所以yk xk c) 若kj，則 ，不能成立,在Y中作以下調(diào)整：將yk 增加到xk ，因?yàn)閥kxk,為保持解的可行性，必須從(yk+1,yn-1)中減去同樣多的量。設(shè)調(diào)整后的解為Z=(z0, z1, ,zk,zk+1, , zn-1)，其中zixi，0ik，且有： Z的效益值有：,差值0,由以上分析得， 若 ，則Y將不是最優(yōu)解； 若 ，則或者Z=X，則X就是最優(yōu)解； 或者ZX，則重復(fù)以上替代過(guò)程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換

10、成X，從而證明X是最優(yōu)解,最優(yōu)裝載,有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 1.算法描述 最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。具體算法描述如下頁(yè)。,template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n

11、,2.貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。 3.最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為 O(nlogn)。,活動(dòng)安排問(wèn)題,活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。,設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用

12、同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si fi 。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容。,template void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,下面

13、給出解活動(dòng)安排問(wèn)題的貪心算法GreedySelector :,各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列,由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。 算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可

14、以用O(nlogn)的時(shí)間重排。,例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：,算法greedySelector 的計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。,若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。 貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。,6.3.1

15、問(wèn)題描述,設(shè)有一個(gè)單機(jī)系統(tǒng)、無(wú)其它資源限制且每個(gè)作業(yè)運(yùn)行相等時(shí)間，不妨假定每個(gè)作業(yè)運(yùn)行1個(gè)單位時(shí)間?，F(xiàn)有n個(gè)作業(yè)，每個(gè)作業(yè)都有一個(gè)截止期限di0，di為整數(shù)。如果作業(yè)能夠在截止期限之內(nèi)完成，可獲得pi0的收益。問(wèn)題要求得到一種作業(yè)調(diào)度方案，該方案給出作業(yè)的一個(gè)子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調(diào)度作業(yè)運(yùn)行，該子集中的每個(gè)作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說(shuō)這種作業(yè)調(diào)度是最優(yōu)的。,6.3 帶時(shí)限的作業(yè)排序,6.3.2 貪心法求解,例62 設(shè)有4個(gè)作業(yè)，每個(gè)作業(yè)的時(shí)限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15

16、,27)。,【程序63】帶時(shí)限作業(yè)排序的貪心算法 void GreedyJob(int d, Set X, int n) /前置條件：p0p1,pn-1 X=0; for (int i=1;in;i+) if ( 集合 Xi 中作業(yè)都能在給定時(shí)限內(nèi)完成) X=Xi; ,6.3.3 算法正確性,定理62 程序62的貪心算法對(duì)于帶時(shí)限作業(yè)排序問(wèn)題將得到最優(yōu)解。,證明： 設(shè)X =(x0, x1, , xK)是由貪心算法6-2所得的作業(yè)集合貪心解， Y =(y0, y1, , yr)是一個(gè)最優(yōu)解的作業(yè)集合。 若Y=X，則X就是最優(yōu)解；否則 ，則至少存在兩個(gè)作業(yè)a和b，使得aX且 ,bY且 。（為什么）

17、 并設(shè)a是這樣的一個(gè)具有最高效益值的作業(yè) (由算法的處理規(guī)則可得：對(duì)于在Y中而不在X中的作業(yè)所有b，有：papb),設(shè)和分別是X和Y的可行的調(diào)度表。因?yàn)閄和Y都是可行解，故這樣的調(diào)度表一定存在； 設(shè)x是既屬于X又屬于Y的一個(gè)作業(yè)，并設(shè)x在調(diào)度表中的調(diào)度時(shí)刻是t，t+1，而在中的調(diào)度時(shí)刻是t，t+1。 在X和Y中作如下調(diào)整： 若tt，則將中在t，t+1時(shí)刻調(diào)度的那個(gè)作業(yè)（如果有的話）與x相交換。如果X中在t，t+1時(shí)刻沒(méi)有作業(yè)調(diào)度，則直接將x移到t，t+1調(diào)度。新的調(diào)度表也是可行的。, 若tt，則在中作類似的調(diào)換，即將中在t，t+1時(shí)刻調(diào)度的那個(gè)作業(yè)（如果有的話）與x相交換。如果Y中在t，t+1

18、時(shí)刻沒(méi)有作業(yè)調(diào)度，則直接將x移到t，t+1調(diào)度。同樣，新的調(diào)度表也是可行的。 對(duì)X和Y中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為和，則在和中X和Y中所有的共有作業(yè)將在相同時(shí)間被調(diào)度。,設(shè)a在中的調(diào)度時(shí)刻是ta, ta+1， b是中該時(shí)刻調(diào)度的作業(yè)，則有papb（為什么？）。 在中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合Y=（Y-b）a的 一個(gè)可行的調(diào)度表，且Y的效益值不小于X的效益值。而Y中比Y少了一個(gè)與X不同的作業(yè)。 重復(fù)上述的轉(zhuǎn)換，可使Y在不減效益值的情況下轉(zhuǎn)換成X。從而X至少有和Y一樣的效益值。所以X也是最優(yōu)解。 證畢。,=（x z ） =（ z x ） =（y x ）

19、=（ y x ） (a) x與z交換前 (b) x與z交換后 =（y x ） =（ y x ） =（x z ） =（ z x ） (c) x與z交換前 (d) x與z交換后 圖6-1 使相同作業(yè)在相同時(shí)刻被調(diào)度,6.3.4 可行性判定,定理63 X=（x0,x1,xk）是k個(gè)作業(yè)的集合，=（0, 1,k）是X 的一種特定排列，它使得d 0 d1dk ，其中， dj是作業(yè)j的時(shí)限。X是一個(gè)可行解當(dāng)且僅當(dāng)X中的作業(yè)能夠按次序調(diào)度而不會(huì)有作業(yè)超期。,方法一：枚舉法，檢驗(yàn)X中作業(yè)所有可能的排列，對(duì)于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成 若X中有k個(gè)作業(yè)，則將要檢查k!個(gè)序列 判

20、斷策略： 對(duì)于一個(gè)給定作業(yè)處理序列i1i2ik,由于作業(yè)ij完成的最早時(shí)間是j，因此只要判斷出排列中的每個(gè)作業(yè)的期限有dijj，就可得知是一個(gè)允許的調(diào)度序列，從而X是一可行解。 反之，如果排列中有一個(gè)作業(yè)有dijj,則將是一個(gè)行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)ij不能在其期限之前完成。,方法二：檢查X中作業(yè)的一個(gè)特定序列就可判斷X的可行性：這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列,證明： 如果X中的作業(yè)可以按照的次序而又不違反任何一個(gè)作業(yè)期限的情況來(lái)處理，則X是一個(gè)可行解 現(xiàn)證若X是一個(gè)可行解，是否代表一個(gè)可行的調(diào)度序列？ X是可行解 必存在一可行的調(diào)度序列 r1r2rk，使得drjj,

21、 1jk。 若 ，則即是可行的調(diào)度序列。否則， ，令a是使得raia的最小下標(biāo)（如下圖）, i1 i2 ia ic ik r1 r2 ra rb rk,設(shè)rb=ia。則有： ba 且 dradrb 故，在中調(diào)換ra與rb，所得的新序列 s1s2sk的處理次序不違反任何一個(gè)期限，而中位置a及a之前的作業(yè)均與相同。 重復(fù)上述過(guò)程，則可將轉(zhuǎn)換成且不違反任何一個(gè)期限，故是一個(gè)可行的調(diào)度序列 故定理得證。,6.3.5 作業(yè)排序貪心算法,定理63提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標(biāo)準(zhǔn)，即按作業(yè)收益的非增次序選擇下一個(gè)作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X。,【程序64】

22、帶時(shí)限的作業(yè)排序程序 int JS(int *d, int *x, int n) /設(shè)p0p1pn-1 int k=0; x0=0; for (int j=1;j=0 ,6.3.6 一種改進(jìn)算法,本小節(jié)將介紹一種帶時(shí)限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時(shí)間從(n2)減少到接近O(n)。,例63 設(shè)n=5個(gè)作業(yè)， 作業(yè)的時(shí)限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益為: (p0,p1,p2,p3,p4)=(20,15,10,5,1)。,【程序65】使用并查集的帶時(shí)限作業(yè)排序 int FJS(int *d,int *x,int n) UFSe

23、t s(n); int b,k=-1,*f=new intn+1; for (int i=0;i=n;i+) fi=i;,for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1); s.Union(t,r); fr=ft; delete f; return k; ,多機(jī)調(diào)度問(wèn)題,多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。 這個(gè)問(wèn)題是NP完全問(wèn)題，到目前為止還沒(méi)有有效的解法。對(duì)于這一類問(wèn)題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好

24、的近似算法。,約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。,采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。 按此策略，當(dāng) nm時(shí)，只要將機(jī)器i的0, ti時(shí)間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時(shí)間。 當(dāng)nm時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為O(nlogn)。,例如，設(shè)7個(gè)獨(dú)立作業(yè)1,2,3,4,5,6,7由3臺(tái)機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時(shí)間分別為2,14,4,16,6,5,3。按算法greedy產(chǎn)生的作業(yè)調(diào)度

25、如下圖所示，所需的加工時(shí)間為17。,6.4.1 問(wèn)題描述,兩路合并外排序算法通過(guò)反復(fù)執(zhí)行將兩個(gè)有序子文件合并成一個(gè)有序文件的操作，最終將n個(gè)長(zhǎng)度不等的有序子文件合并成一個(gè)有序文件。 合并n個(gè)有序子文件成為一個(gè)有序文件的合并過(guò)程可以有多種方式，稱為合并模式。 在整個(gè)合并過(guò)程中，需從外存讀寫(xiě)的記錄數(shù)最少的合并方案稱為最佳合并模式（optimal merge pattern）。,6.4 最佳合并模式,例64 設(shè)有5個(gè)有序子文件（F1,F2,F3,F4,F5），其長(zhǎng)度分別為（20，30，30，10，5）?，F(xiàn)通過(guò)兩兩合并將其合并成一個(gè)有序文件。,帶權(quán)外路徑長(zhǎng)度是針對(duì)擴(kuò)充二叉樹(shù)而言的。擴(kuò)充二叉樹(shù)（exte

26、nded binary tree）中除葉子結(jié)點(diǎn)外，其余結(jié)點(diǎn)都必須有兩個(gè)孩子。擴(kuò)充二叉樹(shù)的帶權(quán)外路徑長(zhǎng)度（weighted external path length）定義為：,6.4.2貪心法求解,兩路合并最佳模式問(wèn)題的最優(yōu)量度標(biāo)準(zhǔn)為帶權(quán)外路徑長(zhǎng)度最小。,兩路合并最佳模式的貪心算法簡(jiǎn)述如下： 設(shè)Ww0,w1 ,wn1是n個(gè)有序文件的長(zhǎng)度；以每個(gè)權(quán)值作為根結(jié)點(diǎn)值，構(gòu)造n棵只有根的二叉樹(shù)； 選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)，作為左右子樹(shù)構(gòu)造一棵新二叉樹(shù)，新樹(shù)根的權(quán)值是兩棵子樹(shù)根的權(quán)值之和； 重復(fù)第2步，直到合并成一棵二叉樹(shù)為止。,【程序66】?jī)陕泛喜⒆罴涯Ｊ降呢澬乃惴?template struct HN

27、ode /優(yōu)先權(quán)隊(duì)列中的元素的類型 operator T()const return weight; BTNode *ptr; T weight; ;,template BTNode* CreateHfmTree (T* w,int n) /w 為一維數(shù)組保存n個(gè)權(quán)值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;i(wi); a.ptr=p;a.weight=wi; pq.Append(a); ,for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a)

28、; return a.ptr; ,6.4.3 算法正確性,定理64 設(shè)有n個(gè)權(quán)值W=w0,w1 ,wn1作為外結(jié)點(diǎn)的權(quán)值，構(gòu)造兩路合并樹(shù)的貪心算法將生成一棵具有最小帶權(quán)外路徑長(zhǎng)度的二叉樹(shù)。,6.5.1 問(wèn)題描述,問(wèn)題 一個(gè)無(wú)向連通圖的生成樹(shù)是一個(gè)極小連通子圖，它包括圖中全部結(jié)點(diǎn)，并且有盡可能少的邊。 一棵生成樹(shù)的代價(jià)是樹(shù)中各條邊上的代價(jià)之和。一個(gè)網(wǎng)絡(luò)的各生成樹(shù)中，具有最小代價(jià)的生成樹(shù)稱為該網(wǎng)絡(luò)的最小代價(jià)生成樹(shù)（minimum-cost spanning tree）。,6.5 最小代價(jià)生成樹(shù),網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)cvw

29、表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。,6.5.2 貪心法求解,最優(yōu)量度標(biāo)準(zhǔn) 選擇使得迄今為止已入選S中邊的代價(jià)之和增量最小的邊 克魯斯卡爾算法的貪心準(zhǔn)則是：按邊代價(jià)的非減次序考察E中的邊，從中選擇一條代價(jià)最小的邊e=(u,v)。 普里姆算法的貪心準(zhǔn)則是：在保證S所代表的子圖是一棵樹(shù)的前提下選擇一條最小代價(jià)的邊e=(u,v)。,最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。將介紹的構(gòu)造最小生成樹(shù)的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這兩個(gè)算法做貪心選擇的方式不同，它們都利用

30、了下面的最小生成樹(shù)性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。,【程序67】最小代價(jià)生成樹(shù)的貪心算法 ESetType SpanningTree(ESetType E, int n) /G=(V,E)為無(wú)向圖 ESetType S=; int u,v,k=0; EType e; while (kn-1 ,6.5.3Prim(普里姆)算法,【程序68】普里姆算法 template struct ENode /帶權(quán)圖的

31、邊結(jié)點(diǎn) int adjVex; T w; ENode* nextArc; ;,template class Graph public: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode* a; int n; ;,template void Graph:Prim(int s) /公有成員函數(shù) int* nearest=new intn,*lowcost=new intn; Prim(s,nearest,lowcost); for(int j=0;jn;j+) cou

32、t(nearestj,“ j,lowcostj) ; coutendl; delete nearest; delete lowcost; ,template void Graph:Prim(int k, int* nearest,T* lowcost) /私有成員函數(shù) bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true;,for (i=

33、1;inextArc) int j= p-adjVex; if (!markj ) 普里姆算法的運(yùn)行時(shí)間是O(n2)。,6.5.4 克魯斯卡爾算法,克魯斯卡爾算法從邊的集合E中，按照邊的權(quán)值從小到大的次序依次選取邊加以考察。 template struct eNode operator T ()const return w; int u,v; T w; ;,【程序69】克魯斯卡爾算法 template void Graph:Kruskal( PrioQueue ,while (kn-1 克魯斯卡爾算法的時(shí)間復(fù)雜度為 O（elog e）。,6.5.5 算法正確性,定理65 設(shè)圖G=（V，E）是一

34、個(gè)帶權(quán)連通圖，U是V的一個(gè)真子集。若邊(u,v)E是所有uU, vV-U的邊中權(quán)值最小者，那么一定存在G的一棵最小代價(jià)生成樹(shù)T=(V,S)，(u,v)S。這一性質(zhì)稱為MST（minimum spanning tree）性質(zhì)。,定理66 普里姆算法和克魯斯卡爾算法都將產(chǎn)生一個(gè)帶權(quán)無(wú)向連通圖的最小代價(jià)生成樹(shù)。,6.6.1 問(wèn)題描述,單源最短路徑問(wèn)題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點(diǎn)sV，求從s到其余各結(jié)點(diǎn)的最短路徑，其中，s稱為源點(diǎn)。,6.6 單源最短路徑,6.6.2 貪心法求解,迪杰斯特拉（Dijkstra） 算法 首先求得長(zhǎng)度最短的一條最短路徑，再求得長(zhǎng)度次短的一條最短路徑，依此類推

35、，直到從源點(diǎn)到其它所有結(jié)點(diǎn)之間的最短路徑都已求得為止。,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T* ,private: int Choose(int* d, bool* s); T*a; int n; ;,template int MGraph:Choose(int* d, bool* s) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin ,temp

36、late void MGraph:Dijkstra(int s, T* ,inSs=true; ds=0; for (i=1;in-1;i+) k=Choose(d,inS); inSk=true; for (j=0; jn; j+) if (!inSj ,6.6.4 算法正確性,定理67 已知帶權(quán)有向圖G=(V,E)，其源點(diǎn)為s，迪杰斯特拉算法使得對(duì)所有i，iV-s，di(s,i)，且一旦di= (s,i)，它將不再改變。 定理68 已知帶權(quán)有向圖G=(V,E)，其源點(diǎn)為s，迪杰斯特拉算法使得對(duì)所有結(jié)點(diǎn)i和j, iS，jV-S，必有didj。,定理69 已知帶非負(fù)權(quán)值的有向圖G=(V,E)，

37、路徑（s=v0, ,vi,vk=t）是從s到vk的一條最短路徑，viV，0ikn，則子路徑（s=v0, ,vi）和（vi,vk=t）必定分別是從s到vi 和vi到t的最短路徑。 定理610 已知帶非負(fù)權(quán)值的有向圖G=(V,E)，其源點(diǎn)為s，迪杰斯特拉算法結(jié)束時(shí)，對(duì)所有結(jié)點(diǎn)i，有di=(s,i)。,6.7.1 單帶最優(yōu)存儲(chǔ),問(wèn)題 設(shè)有n個(gè)程序編號(hào)為0,n-1，存放在長(zhǎng)度為L(zhǎng)的磁帶上，程序i在磁帶上的存儲(chǔ)長(zhǎng)度為ai，0in。 假定每個(gè)程序被檢索地概率相等，則平均檢索時(shí)間（mean retrieval time MRT）定義為 單帶最優(yōu)存儲(chǔ)問(wèn)題是求這n個(gè)程序的一種排列，使得MRT有最小值。,6.7

38、磁帶最優(yōu)存儲(chǔ),例65 設(shè)n=3，(a0,a1,a2)=(5,10,3)。,貪心法求解 量度標(biāo)準(zhǔn)：計(jì)算迄今為止已選的那部分程序的D值，選擇下一個(gè)程序應(yīng)使得該值增加最小。 定理611 設(shè)有n個(gè)程序0,1,n-1, 程序i的長(zhǎng)度為ai，0in，且有a0a1an1，=(0,1,n1)是這n個(gè)作業(yè)的一種排列。那么只有當(dāng)j=j，0in時(shí)，D()=有最小值。,6.7.2 多帶最優(yōu)存儲(chǔ),問(wèn)題 設(shè)有m1條磁帶T0,T1,Tm1和n個(gè)程序。要求將此n個(gè)程序分配到這m條磁帶上，令I(lǐng)j,0jm 是存放在第j條磁帶上的程序子集的某種排列，D(Ij) 的定義如前面相同，那么，求m條磁帶上檢索一個(gè)程序的平均檢索時(shí)間的最小值

39、等價(jià)于求 的最小值。,【程序611】多帶最優(yōu)存儲(chǔ) #include void Store(int n, int m) int j = 0; for (int i=0; in; i+) cout 將程序i 加到磁帶 jendl; j=(j+1)% m; coutendl; ,定理612 設(shè)有n個(gè)程序0,1,n-1, 程序i的長(zhǎng)度為ai，0in，且有a0a1an1， 程序611 實(shí)現(xiàn)將n個(gè)程序分配到m條磁帶上，且有最小TD值。,6.8.1 最優(yōu)量度標(biāo)準(zhǔn),選擇最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法求解問(wèn)題的核心問(wèn)題。 貪心算法每一步作出的選擇可以依賴以前作出的選擇，但不依賴將來(lái)的選擇，也不依賴于子問(wèn)題的解。 對(duì)于一個(gè)貪心算法，必須證明所采用的量度標(biāo)準(zhǔn)能夠?qū)е乱粋€(gè)整體最優(yōu)解。,6.8 貪心法的基本要素,6.8.2 最優(yōu)子結(jié)構(gòu),最優(yōu)子結(jié)構(gòu)特性是關(guān)于問(wèn)題最優(yōu)解的特性。當(dāng)一個(gè)問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，則稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)特性（optimal substructure）。 一般而言，如果一個(gè)最優(yōu)化問(wèn)題的解結(jié)構(gòu)具有元組形式，并具有最優(yōu)子結(jié)構(gòu)特性，我們可以嘗試選擇量度標(biāo)準(zhǔn)。,