第3章 算法之貪心算法

1、第三章 算法之貪心算法本章主要知識點（46學(xué)時）： 3.1 活動安排問題 3.2 貪心算法的基本要素 3.3 最優(yōu)裝載 3.4 哈夫曼編碼 3.5 單源最短路徑 3.6 最小生成樹 3.7 多機調(diào)度問題引言【找零錢問題】希望用數(shù)目最少的硬幣找零假設(shè)提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。 假設(shè)需要找67美分，25+25+10+5+1+1，共6枚。假設(shè)提供了數(shù)目不限的面值為1 1美分、5美分及1美分的硬幣？找零15美分 11+1+1+1+1，共5枚（貪心算法） 5+5+5，共3枚（非貪心算法）在一些情況下，即使貪心算法不能得到在一些情況下，即使貪心算法不能得到整體最

2、優(yōu)解整體最優(yōu)解，其，其最終結(jié)果卻是最終結(jié)果卻是最優(yōu)解的很好近似最優(yōu)解的很好近似。引言貪心算法：總是做出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心法的基本思路：從問題的某一個初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到某算法中的某一步不能再繼續(xù)前進(jìn)時，算法停止。引言貪心法存在的問題：1. 不能保證求得的最后解是最佳的；2. 不能用來求最大或最小解問題；3. 只能求滿足某些約束條件的可行解的范圍。 3.1 活動安排問題【活動安排問題】就是要在所給的活動集合中選出最大的相容活動子集合。該問題要求高效地安排一系列爭用

3、某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)sjfi時，活動i與活動j相容。復(fù)雜性分析由于輸入的活動以其完成時間的升序排列，所以算法greedySelector每次總是選擇最早完成時間的相容活動加

4、入集合A中。為未安排活動留下盡可能多的時間。該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的活動。一個實例例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：說明若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。貪心算法并不總能求得問題的整體最優(yōu)解。對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。貪心算法描述public static int greedySelector(int s, int

5、 f, boolean a) int n=s.length-1;a1=true; /選擇最早結(jié)束活動選擇最早結(jié)束活動int j=1;/j表示已安排活動編號表示已安排活動編號int count=1;/已安排活動數(shù)已安排活動數(shù)for (int i=2;i=fj) ai=true;j=i;count+; else ai=false;return count;各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列 復(fù)雜性分析算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的升序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動

6、未按非減序排列，可以用O(nlogn)的時間重排。3.2 貪心算法的基本要素對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)： 貪心選擇性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì)。1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題

7、。2.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。0-1背包問題與背包問題0-1背包問題： 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？ 在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問題: 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。這2類問題都具

8、有最優(yōu)子結(jié)構(gòu)性質(zhì)，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 貪心方法的數(shù)據(jù)選擇策略1、以、以價值價值為量度標(biāo)準(zhǔn)為量度標(biāo)準(zhǔn)按價值從高到低的次序?qū)⑽锲芬患诺奖嘲磧r值從高到低的次序?qū)⑽锲芬患诺奖嘲兄小?、以以容量容量作為量度作為量度按物品重量的從清到重次序來把物品放入背包。按物品重量的從清到重次序來把物品放入背包。3、采用、采用單位價值單位價值為度量標(biāo)準(zhǔn)為度量標(biāo)準(zhǔn)使物品的裝入次序使物品的裝入次序按按pi/wi比值的從大到小比值的從大到小來考來考慮。慮。用貪心策略求解背包問題時，首先要選出最用貪心策略求解背包問題時，首先要選出最優(yōu)的度量標(biāo)準(zhǔn)。優(yōu)的度量標(biāo)準(zhǔn)。算法思

9、路算法思路1).將各物體按將各物體按單位價值單位價值由高到低排序由高到低排序. 2).取價值最高者放入背包取價值最高者放入背包.3).計算背包剩余空間計算背包剩余空間.4).重復(fù)重復(fù)2-3直到背包剩余容量直到背包剩余容量=0或物體全部裝或物體全部裝入背包為止。入背包為止。用貪心算法解背包問題的基本步驟考慮下列情況的背包問題考慮下列情況的背包問題 n=3,M=20,(p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10) 其中的其中的4個可行解是：個可行解是：背包問題void Knapsack(int n,float M,float v,float w,float

10、 x) Sort(n,v,w); /計算每種物品單位重量的價值Vi/Wiint i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi; /允許放入一個物品的一部分void 0-1-Knapsack(int n,float M,float v,float w,float x) /不一定是最優(yōu)解不一定是最優(yōu)解 Sort(n,v,w); int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;0-1背包問題貪心選擇

11、之所以不能得到最優(yōu)解：因為無法保證最終能將背包裝滿，部分閑置的背包空間使總價值降低了。0-1背包問題與背包問題102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥2401002012030601010020601012030601010020802012020300-1背包背包物品價值及重量思考題-0/1背包問題在雜貨店比賽中你獲得了第一名，獎品是一車免費雜貨。店中有N種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為C，物品i需占用wi的空間，價值為pi。你的目標(biāo)是使車中裝載的物品價值最大。當(dāng)然，所裝貨物不能超過車的容量，且同一種物

12、品不得拿走多件。如何選擇量度標(biāo)準(zhǔn)才能找到最優(yōu)解？若N=2, w=100,10,10,p=20,15,15,C=105。利用價值貪心準(zhǔn)則時所得結(jié)果是否是最優(yōu)？問題: 設(shè)一個由N個城市v1,v2,vn組成的網(wǎng)絡(luò), ci,j 為從vi 到vj的代價不妨設(shè)ci,j = cj,i ,且ci,i= .一推銷員要從某城市出發(fā)經(jīng)過每城市一次且僅一次后返回出發(fā)地問如何選擇路線使代價最小。抽象描述抽象描述:將城市以及之間的道路抽象為一個無向圖G, G中每邊的權(quán)值表示這段線路的代價. 問題轉(zhuǎn)化為求一條最佳周游路線:從一點出發(fā),經(jīng)過每點一次且僅一次并返回原點,且該路線的總代價最小. 1 2 7 51 4 4 32 4

13、 1 27 4 1 35 3 2 3 C=思考題-旅行商問題(Traveling Salesman Problem)費用矩陣思考題-旅行商問題(貨郎擔(dān)問題) 首先在圖中選一條代價最小的邊。為了選擇下一條邊，先要檢查一下候選邊與已選入的邊之間是否滿足以下兩點： 1)不會有三條邊(候選邊及已入選邊)與同一頂點相關(guān)聯(lián)。 2)不會使入選邊形成回路，除非入選邊的個數(shù)已等于圖中的頂點總數(shù)。在滿足以上兩點的候選邊中，挑選最短的邊作為入選邊。如此做下去，直到得到一個經(jīng)過所有頂點的回路。最后求得的回路是125341，代價是14。實際圖11最小代價的回路是12543一1，代價是10。輸入:城市的數(shù)目n,代價矩陣c

14、=c(1.n,1.n).輸出: 最小代價路線1. tour:=0; / tour 紀(jì)錄路線/2. cost:=0; / cost 紀(jì)錄到目前為止的花費/3. v:=N; / N為起點城市, v為當(dāng)前出發(fā)城市/4. for k:=1 to N-1 do 5. tour:= tour+(v,w) /(v,w)為從v到其余城市代價中值最小的邊/6. cost:= cost+c(v,w) 7 v:=w8 tour:= tour+(v,N)9 cost:= cost+c(v,N) print tour, cost 算法的最壞時間復(fù)雜性為O(n2)*該算法不能求的最優(yōu)解.思考題-旅行商問題(貨郎擔(dān)問題)3

15、.3 最優(yōu)裝載有一批集裝箱要裝上一艘載重量為C的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。問題可形式化描述為其中變量xi=0表示不裝入集裝箱i，xi=1表示裝入集裝箱i。nixcxwxiniiinii110max11，3.3 最優(yōu)裝載例例設(shè)設(shè)N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。所考察貨箱的次序為所考察貨箱的次序為 t1.8=7, 3, 6, 8, 4, 1, 5, 2。貨箱。貨箱7, 3, 6, 8, 4, 1的總重量為的總重量為390個單位且已被裝載個單位且已被裝

16、載, 剩下的裝載能力為剩下的裝載能力為10 ,小于任意貨箱小于任意貨箱.所以得到解所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1算法思路算法思路 將裝船過程劃為多步選擇，每步裝一個將裝船過程劃為多步選擇，每步裝一個貨箱，每次貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱從剩下的貨箱中選擇重量最輕的貨箱.如如此下去直到所有貨箱均裝上船或船上不能再容納其此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。他任何一個貨箱。3.3 最優(yōu)裝載算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。void Loading(int x

17、, Type w, Type c, int n) int *t = new int n+1;Sort(w, t, n); /按貨箱重量排序按貨箱重量排序O(nlogn)for (int i = 1; i = n; i+) xi = 0; /O(n)for (int i = 1; i = n & wti = c; i+) xti = 1; c -= wti; /調(diào)整剩余空間調(diào)整剩余空間思考設(shè)設(shè)N=8,w1，w8=100, 200, 50, 90, 150, 50, 20, 80，C=400。編程求t 哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。哈夫曼編

18、碼壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。3.4 哈夫曼編碼例如一個包含100,000個字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長編碼需要300,000位，而按表中變長編碼方案，文件的總碼長為：（451+133+123+163+94+54）1000=224,000。比用定長碼方案總碼長較少約45%。1.前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使

19、譯碼方法非常簡單。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點都有2個兒子結(jié)點。平均碼長定義為：碼長: )()()()(cdcdcfTBTTCc使平均碼長達(dá)到最小的前綴碼編碼方案稱為使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集給定編碼字符集C的最優(yōu)前綴碼。的最優(yōu)前綴碼。2.構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結(jié)點開始，執(zhí)行|C|1次的“合并”運算后產(chǎn)生最終所要求的樹T。2.構(gòu)造哈夫曼樹構(gòu)造最優(yōu)二叉樹的算法是由哈夫曼提出的，所以稱之為哈夫曼算法，具體敘述如下

20、： 根據(jù)與n個權(quán)值w1,w2,.,wn對應(yīng)的n個結(jié)點構(gòu)成n棵二叉樹的森林F=T1,T2,.,Tn,其中每棵二叉樹Ti(1=i=n)都由一個權(quán)值為wi的根結(jié)點，其左右子樹均為空； 在森林F中選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左右子樹，且置新樹的附加根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和； 從F中刪除這兩棵樹，同時把新樹加入F中； 重復(fù)(2)和(3)，直到F中只含有一棵樹為止。此樹便是哈夫曼樹。算法說明在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率

21、的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n1次的合并總共需要O(nlogn)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn) 。3.5 單源最短路徑(Single-Source Shortest-Paths Problem) 給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源。單源

22、最短路徑問題：已知圖G（V，E），找出從某給定的源結(jié)點SV到V中的每個結(jié)點的最短路徑。3.5.1 Dijkstra算法Dijkstra算法是解單源最短路徑問題的貪心算法。基本思想：設(shè)置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。（1）初始時，S中僅含有源節(jié)點。（2）設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，用數(shù)組Di記錄頂點i當(dāng)前所對應(yīng)的最短特殊路徑長度。（3）Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組D作必要的修改。（4）一旦S包含了所有V中頂點，

23、dist就記錄了從源到所有其它頂點之間的最短路徑長度。1、 Dijkstra算法的基本思想設(shè)S為最短距離已確定的頂點集（紅點集）V-S是最短距離尚未確定的頂點集（藍(lán)點集）。初始化初始化 最初只有源點s的最短距離是已知的(D(s)=0)，故紅點集S=s 。重復(fù)以下工作，重復(fù)以下工作，按路徑長度遞增次序產(chǎn)生各頂點最短路按路徑長度遞增次序產(chǎn)生各頂點最短路徑徑 在當(dāng)前藍(lán)點集中選擇一個最短距離最小的藍(lán)點來擴充紅點集，以保證算法按路徑長度遞增的次序產(chǎn)生各頂點的最短路徑。 當(dāng)藍(lán)點集中僅剩下最短距離為的藍(lán)點，或者所有藍(lán)點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。一個實例Dijkstra(G，D，s)

24、 /Dijkstra 算法算法 O(V2) /初始化操作初始化操作 S=s；Ds=0； /設(shè)置初始的紅點集及最短距離設(shè)置初始的紅點集及最短距離 for( all i V-S ) Di=Gsi； /O(V) /擴充紅點集擴充紅點集 for (i=1;iDk+Gkj) Dj=Dk+Gkj； #define VEX 5/定義結(jié)點的個數(shù)定義結(jié)點的個數(shù)#define maxpoint 100double graphmaxpoint= 0 , 10 , -1 , 30 , 100 , -1 , 0 , 50 , -1 , -1 , -1 , -1 , 0 , -1 , 10 , -1 , -1 , 20

25、, 0 , 60 , -1 , -1 , -1 , -1 , 0 ; /鄰接矩陣，鄰接矩陣，-1代表節(jié)點間無邊相連代表節(jié)點間無邊相連int Rmaxpoint=0,Bmaxpoint;int DVEX,PVEX;/定義數(shù)組定義數(shù)組D用來存放結(jié)點特殊用來存放結(jié)點特殊距離，距離，P數(shù)組存放父親結(jié)點數(shù)組存放父親結(jié)點/初始時，紅點集中僅有源結(jié)點初始時，紅點集中僅有源結(jié)點0R0=1; B0=0;for(int i=1;iVEX;i+) /初始化藍(lán)點集節(jié)點初始化藍(lán)點集節(jié)點Bi=1;/對數(shù)組對數(shù)組D、P進(jìn)行初始化進(jìn)行初始化 for(i=0;iVEX;i+)Di=graph0i; if(Di!=-1) Pi=

26、0; else Pi=-1;for(int k=1;kVEX;k+) /每次從藍(lán)點集中取出具有最短特殊路長每次從藍(lán)點集中取出具有最短特殊路長度的結(jié)點度的結(jié)點min for(int min=0;Bmin=0;) min+; for(int j=min;jVEX;j+) /求藍(lán)點集結(jié)點最小下標(biāo)元素求藍(lán)點集結(jié)點最小下標(biāo)元素if(Dj!=-1&DjDmin&Bj=1) min=j; coutmin=min ; /將具有最短特殊路長度的結(jié)點將具有最短特殊路長度的結(jié)點min添加到紅點集中添加到紅點集中 Rmin=1; Bmin=0; /對數(shù)組對數(shù)組D作必要的修改作必要的修改 for(j=1

27、;jDmin+graphminj|Dj=-1) Dj=Dmin+graphminj; /每次迭代求最小值，最后每次迭代求最小值，最后一次即為到源點的最短路徑一次即為到源點的最短路徑 Pj=min; 3.5.2 Dijkstra算法Relax描述du:su的距離 pu:記錄前一節(jié)點Relax松弛算法Init-single-source(G,s) for each vVG dodv= pv=NIL ds=0, ps=NILRelax(u,v,w) if dvdu+w(u,v)then dv=du+wu,v pv=u 算法描述dijkstra(G,w,s)1. Init-single-source(

28、G,s) /O(v)2. S=s 3. Q=VG-s4.while Q do u=min(Q) /用數(shù)組O(V) S=Su for each vadju & v Q /O(E) do Relax(u,v,w)算法基本思想3.5.3 Bellman-Ford算法思想 dijkstra算法的前提是所有邊是正的 Bellman-Ford算法允許負(fù)邊 初始化：將除源點外的所有頂點的最短距離估計值 dv +, ds 0; 迭代求解：反復(fù)對邊集E中的每條邊進(jìn)行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）(1) 檢驗負(fù)權(quán)回路：如果存在負(fù)邊，則算法返回f

29、alse，表明問題無解；否則算法返回true，并且從源點可達(dá)的頂點v的最短距離保存在 dv中。3.5.3 Bellman-Ford算法思想dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負(fù)邊 Init-single-source(G,s) for i 1 to |VG| - 1 /O(V) 3. do for each edge (u, v) EG/O(E)4. do RELAX(u, v, w) 5. for each edge (u, v) EG /O(E)6. do if du + w(u, v) dv 7. then return FALSE /存在負(fù)環(huán)8. r

30、eturn TRUE存在負(fù)權(quán)回路的圖是不能求兩點間最短路徑，因為存在負(fù)權(quán)回路的圖是不能求兩點間最短路徑，因為只要在負(fù)權(quán)回路上不斷兜圈子，所得的最短路長度只要在負(fù)權(quán)回路上不斷兜圈子，所得的最短路長度可以任意小?？梢匀我庑　?.5.4 其他最短路徑問題其他最短路徑問題單目標(biāo)單目標(biāo)最短路徑問題最短路徑問題(Single-Destination Shortest-Paths Problem)：找出圖中每一頂點v到某指定頂點u的最短路徑。只需將圖中每條邊反向，就可將這一問題變?yōu)閱卧醋疃搪窂絾栴}，單目標(biāo)u變?yōu)閱卧袋cu。單頂點對單頂點對間最短路徑問題間最短路徑問題(Single-Pair Shortest-

31、Paths Problem)：對于某對頂點u和v，找出從u到v的一條最短路徑。顯然，若解決了以u為源點的單源最短路徑問題，則上述問題亦迎刃而解。而且從數(shù)量級來說，兩問題的時間復(fù)雜度相同。所有頂點對所有頂點對間最短路徑問題間最短路徑問題(All-Pairs Shortest-Paths Problem)：對圖中每對頂點u和v，找出u到v的最短路徑問題。這一問題可用每個頂點作為源點調(diào)用一次單源最短路徑問題算法予以解決。3.6 最小生成樹設(shè)G =(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和

32、稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)cvw表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。1、最小生成樹性質(zhì)用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。Prim算法和Kruskal算法2個算法都利用了最小生成樹性質(zhì)：最小生成樹性質(zhì)：設(shè)G=(V，E)是一個連通網(wǎng)絡(luò)，U是頂點集V的一個真子集。若(u，v)是G中所有的一個端點在U(uU)里、另一個端點不在U(即vV-U)里的邊中，具有最小權(quán)值的一條邊，則一

33、定存在G的一棵最小生成樹包括此邊(u，v)。這個性質(zhì)稱為MST（Minimum Spanning Tree ）性質(zhì)。1、最小生成樹性質(zhì)MST性質(zhì)的證明： 約定：集合U中的頂點紅色頂點V-U中的頂點藍(lán)色頂點連接紅點和藍(lán)點的邊紫色邊權(quán)最小的紫邊稱為輕邊(即權(quán)重最“輕”的邊)。用反證法證明MST性質(zhì)1、最小生成樹性質(zhì)假設(shè)G中任何一棵MST都不含輕邊(u，v)。則若T是G的一棵MST，則它不含此輕邊。由于T是包含了G中所有頂點的連通圖，所以T中必有一條從紅點u到藍(lán)點v的路徑P，且P上必有一條紫邊(u ，v )連接紅點集和藍(lán)點集，否則u和v不連通。當(dāng)把輕邊(u，v)加入樹T時，該輕邊和P必構(gòu)成了一個回路

34、。刪去紫邊(u ，v )后回路亦消除，由此可得另一生成樹T 。 T 和T的差別僅在于T用輕邊(u，v)取代了T中權(quán)重可能更大的紫邊(u ，v )。因為w(u，v)w(u ，v )，所以 w(T)=w(T)+w(u，v)-w(u，v)w(T)故T亦是G的MST，它包含邊(u，v)，這與假設(shè)矛盾。 所以，MST性質(zhì)成立。2、Prim（普里姆）算法設(shè)G=(V,E)是連通帶權(quán)圖，V=1,2,n。構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置U=1，然后，只要U是V的真子集，就作如下的貪心選擇：選取滿足條件iU，jV-U，且cij最小的邊，將頂點j添加到U中。這個過程一直進(jìn)行到U=V時為止。在這個

35、過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如圖所示。2、Prim（普里姆）算法PrimMST(G，T，r) /求圖G的以r為根的MST，結(jié)果放在T中 T=；U=1; while(U!=V) /O(V) (i,j)=iU，jV-U，且cij最小的邊/O(V) T=T (i，j) /輕邊 (i，j) 加入T U=U j; / 節(jié)點j 加入U，變?yōu)榧t點 http:/ 2、Prim（普里姆）算法如何有效地找出滿足條件iU, jV-U，且權(quán)cij最小的邊(i,j)？ 較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。 在Prim算法執(zhí)行過

36、程中，先找出V-U中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，將j添加到U中，并對closest和lowcost作必要的修改。3、Kruskal（克魯斯卡爾）算法Kruskal算法構(gòu)造最小生成樹的基本思想：(1)將G的n個頂點看成n個孤立的連通分支。(2)將所有的邊按權(quán)從小到大排序。(3)從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當(dāng)查看到第k條邊(v,w)時，如果端點v和w分別是當(dāng)前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和

37、w在當(dāng)前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進(jìn)行到只剩下一個連通分支時為止。例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如圖所示。3、Kruskal（克魯斯卡爾）算法（1）算法思想T的初始狀態(tài) 只有n個頂點而無邊的森林T=(V， )按邊長遞增的順序選擇E中的n-1安全邊(u，v)并加入T，生成MST注意： 安全邊指兩個端點分別是森林T里兩棵樹中的頂點的邊。加入安全邊，可將森林中的兩棵樹連接成一棵更大的樹 因為每一次添加到T中的邊均是當(dāng)前權(quán)值最小的安全邊，MST性質(zhì)也能保證最終的T是一棵最小生成樹 3、Kruskal（克魯斯卡爾）算法MST-Kr

38、uskal (G) /求連通網(wǎng)G的一棵MST T=(V，)； /初始化，T是只含n個頂點不包含邊的森林/依權(quán)值遞增序?qū)(G)中的邊排序，并設(shè)結(jié)果在E0.e-1中 O(Elog(E)sort the edges of E by non-decreasing weight w for(i=0;ie;i+) /e為圖中邊總數(shù)，O(E) 取第i條邊（u,v） if u和v分別屬于T中兩棵不同的樹 T=T(u，v)；/(u，v)是安全邊，將其加入T中 return T；說明有關(guān)說明： 該算法的時間復(fù)雜度為O(ElogE)。 Kruskal算法的時間主要取決于邊數(shù)。它較適合于稀疏圖。 3.7 多機調(diào)度問

39、題設(shè)有 n 個獨立的作業(yè) 1 , 2 , . , n ，由 m 臺相同的機器進(jìn)行加工處理。作業(yè) i 所需的處理時間為 ti。約定： 任何作業(yè)可以在任何一臺機器上加工處理，但未完工前不允許中斷處理。 任何作業(yè)不能拆分成更小的作業(yè)。多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的 n 個作業(yè)在盡可能短的時間內(nèi)由 m 臺機器加工處理完成。3.7 多機調(diào)度問題這個問題是NP完全問題(Non-deterministic Polynomial Complete Problem) ，也即是多項式復(fù)雜程度的非確定性問題 ，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。非確定性問題:無法按部就班直接地計算出來。比如，找大質(zhì)數(shù)的問題。沒有一個公式