第3章貪心算法

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

11+1+1+1+1，共5枚（貪心算法）

5+5+5，共3枚（非貪心算法）4引言總是做出在當前看來最好的選擇并不從整體最優(yōu)考慮局部最優(yōu)選擇。貪心法的基本思路：

——從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。

5引言貪心法存在的問題：

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

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

3.只能求滿足某些約束條件的可行解的范圍。63.1活動安排問題【活動安排問題】就是要在所給的活動集合中選出最大的相容活動子集合。該問題要求高效地安排一系列爭用某一公共資源的活動。73.1活動安排問題設有n個活動的集合E={1,2,…,n}使用同一資源，同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi（si<fi）

。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。即sj≥fi時，活動i與活動j相容。8復雜性分析由于輸入的活動以其完成時間的升序排列，所以算法greedySelector每次總是選擇最早完成時間的相容活動加入集合A中。為未安排活動留下盡可能多的時間。該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的活動。9一個實例例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011s[i]130535688212f[i]456789101112131410說明若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fj，則不選擇活動i，否則選擇活動i加入集合A中。貪心算法并不總能求得問題的整體最優(yōu)解。對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數(shù)學歸納法證明。11貪心算法描述publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;//選擇最早結束活動intj=1;//j表示已安排活動編號intcount=1;//已安排活動數(shù)for(inti=2;i<=n;i++)//i表示待安排活動{if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活動的起始時間和結束時間存儲于數(shù)組s和f中且按結束時間的非減序排列12復雜性分析當輸入的活動已按結束時間的升序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按結束時間升序排列，可以用O(nlogn)的時間重排。133.2貪心算法的基本要素對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質最優(yōu)子結構性質141.貪心選擇性質所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。3.2貪心算法的基本要素152.最優(yōu)子結構性質當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。3.2貪心算法的基本要素160-1背包問題與背包問題0-1背包問題：給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容重量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入----不裝入背包問題:與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結構性質，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。17貪心算法的數(shù)據(jù)選擇策略1、以價值為量度標準按價值從高到低的次序將物品一件件放到背包中。2、以重量作為量度按物品重量的從清到重次序來把物品放入背包。3、采用單位價值為度量標準使物品的裝入次序按pi/wi比值的從大到小來考慮。用貪心策略求解背包問題時，首先要選出最優(yōu)的度量標準。18考慮下列情況的背包問題n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4個可行解是：(x1,x2,x3)∑wixi∑pixi(1/2,1/3,1/4)16.524.25策略1①(1,2/15,0)2028.2策略2②(0,2/3,1)2031策略3③(0,1,1/2)2031.5背包問題19[算法思路]1).將各物體按單位價值由高到低排序；2).取價值最高者放入背包；3).計算背包剩余；4).重復2-3直到背包剩余=0或物體全部裝入背包為止。用貪心算法解背包問題的基本步驟voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//計算每種物品單位價值vi/wiinti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];

//填滿背包}void0-1-Knapsack(intn,floatM,floatv[],floatw[],floatx[])//不一定是最優(yōu)解{Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}}0-1背包問題貪心選擇之所以不能得到最優(yōu)解：因為無法保證最終能將背包裝滿，部分閑置的背包空間使總價值降低了。22思考題在雜貨店比賽中你獲得了第一名，獎品是一車免費雜貨。店中有N種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為C，物品i需占用wi的空間，價值為pi。你的目標是使車中裝載的物品價值最大。當然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。如何選擇量度標準才能找到最優(yōu)解？若N=3,w=[100,10,10],p=[20,15,15],C=105。利用價值貪心準則時所得結果是否是最優(yōu)？23問題:

設一個由N個城市v1,v2,…vn組成的網(wǎng)絡,ci,j為從vi到vj的代價不妨設ci,j

=cj,i,且ci,i=.一推銷員要從某城市出發(fā)經(jīng)過每城市一次且僅一次后返回出發(fā)地，如何選擇路線使代價最小。抽象描述:抽象為一個無向圖G,G中每邊的權值表示這段線路的代價.問題轉化為求一條最佳周游路線:從一點出發(fā),經(jīng)過每點一次且僅一次并返回原點,且該路線的總代價最小.思考題-旅行商問題(TravelingSalesmanProblem)C=費用矩陣24思考題-旅行商問題(貨郎擔問題)在圖中選一條代價最小的邊。為了選擇下一條邊，先要檢查一下候選邊與已選入的邊之間是否滿足以下兩點：

1)不會有三條邊(候選邊及已入選邊)與同一頂點相關聯(lián)。

2)不會使入選邊形成回路，除非入選邊的個數(shù)已等于圖中的頂點總數(shù)。在滿足以上兩點的候選邊中，挑選最短的邊作為入選邊。如此做下去，直到得到一個經(jīng)過所有頂點的回路。最后求得的回路是1—2—5—3—4—1，代價是14。實際圖1-1最小代價的回路是1—2—5—4—3一1，代價是10。25輸入:城市的數(shù)目n,代價矩陣c=c(1..n,1..n).輸出:最小代價路線1.tour:=0;//tour紀錄路線/2.cost:=0;//cost紀錄到目前為止的花費/3.v:=N;//N為起點城市,v為當前出發(fā)城市/4.fork:=1toN-1do5.{tour:=tour+(v,w)//(v,w)為從v到其余城市代價中值最小的邊/6.cost:=cost+c(v,w)7v:=w}8tour:=tour+(v,N)9cost:=cost+c(v,N)printtour,cost算法的最壞時間復雜性為O(n2)*該算法不能求的最優(yōu)解.思考題-旅行商問題(貨郎擔問題)263.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為C的輪船。其中集裝箱i的重量為Wi。要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。問題可形式化描述為其中變量xi=0表示不裝入集裝箱i，xi=1表示裝入集裝箱i。273.3最優(yōu)裝載[例]設N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。所考察貨箱的次序為t[1..8]={7,3,6,8,4,1,5,2}。貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載,剩下的裝載能力為10,小于任意貨箱.所以得到解[x1,...x8]=[1,0,1,1,0,1,1,1][算法思路]將裝船過程劃為多步選擇，每步裝一個貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱.如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。283.3最優(yōu)裝載算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產生最優(yōu)解。voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);//按貨箱重量排序O(nlogn)for(inti=1;i<=n;i++)x[i]=0;//O(n)for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}//調整剩余空間}29思考設N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。編程求t[1..8].303.4哈夫曼編碼哈夫曼編碼是用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。哈夫曼編碼壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。313.4哈夫曼編碼例如一個包含100,000個字符的文件，各字符出現(xiàn)頻率不同，如下表所示。abcdef頻率(千次)fc4513121695定長碼000001010011100101變長碼010110011111011100定長編碼需要300,000位按表中變長編碼方案，文件的總碼長為：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000比定長碼方案總碼長少約25%。321.前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質可以使譯碼方法非常簡單。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結點都有2個兒子結點。平均碼長定義為：使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。332.構造哈夫曼編碼哈夫曼提出構造最優(yōu)前綴碼的貪心算法哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結點開始，執(zhí)行|C|－1次的“合并”運算后產生最終所要求的樹T。343.構造哈夫曼樹構造最優(yōu)二叉樹的具體算法如下：與n個權值{w1,w2,...,wn}對應的n個結點構成n棵二叉樹組成的森林F={T1,T2,...,Tn},其中每棵二叉樹Ti(1<=i<=n)都有一個權值為wi的根結點，其左右子樹均為空；在森林F中選出兩棵根結點的權值最小的樹作為一棵新樹的左右子樹，且置新樹的附加根結點的權值為其左右子樹上根結點的權值之和；從F中刪除這兩棵樹，同時把新樹加入F中；重復(2)和(3)，直到F中只含有一棵樹為止。此樹便是哈夫曼樹。3536算法說明huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關于n個字符的哈夫曼算法的計算時間為O(nlogn)

。373.5單源最短路徑(Single-SourceShortest-PathsProblem)給定帶權有向圖G=(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源。單源最短路徑問題：已知圖G＝（V，E），找出從某給定的源結點S∈V到V中的每個結點的最短路徑。383.5單源最短路徑393.5.1Dijkstra算法Dijkstra算法是解單源最短路徑問題的貪心算法?；舅枷耄涸O置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。特殊路徑設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，用數(shù)組D[i]記錄頂點i當前所對應的最短特殊路徑長度。401、Dijkstra算法的基本思想設S為最短距離已確定的頂點集（紅點集）V-S是最短距離尚未確定的頂點集（藍點集）。

①初始化

最初只有源點s的最短距離是已知的(D(s)=0)，故紅點集S={s}。

②重復以下工作，按路徑長度遞增次序產生各頂點最短路徑

在當前藍點集中選擇一個D[i]最小的藍點擴充到紅點集，更新其余藍點集D[]值。

③當藍點集中僅剩下最短距離為∞的藍點，或者所有藍點已擴充到紅點集時，s到所有頂點的最短路徑就求出來了。41一個實例Dijkstra(G，D，s)

//Dijkstra算法O(V2){//初始化操作

S={s}；D[s]=0；

for(alli∈V-S)D[i]=G[s][i]；//O(V)

//擴充紅點集

for(i=1;i<V;i++)

{

D[k]=min{D[i]：alli∈V-S}；

if(D[k]==∞)return；

S=S∪{k}；

for(allj∈V-S)

if(D[j]>D[k]+G[k][j])D[j]=D[k]+G[k][j]；

}}//設置初始的紅點集及最短距離//最多擴充V-1個藍點到紅點集//O(V)

//在藍點集找特殊距離最小的頂點k//藍點集中所有點的特殊距離均為∞,表示這些頂點的最短路徑不存在//將藍點k擴充到紅點集//調整剩余藍點的特殊距離//O(V)#defineVEX5//定義結點的個數(shù)#definemaxpoint100doublegraph[][maxpoint]={{0,10,-1,30,100},{-1,0,50,-1,-1},{-1,-1,0,-1,10},{-1,-1,20,0,60},{-1,-1,-1,-1,0}};//鄰接矩陣，-1代表節(jié)點間無邊相連intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定義數(shù)組D用來存放結點特殊距離，P數(shù)組存放父親結點//初始時，紅點集中僅有源結點0R[0]=1;B[0]=0;for(inti=1;i<VEX;i++)//初始化藍點集節(jié)點B[i]=1;//對數(shù)組D、P進行初始化for(i=0;i<VEX;i++){D[i]=graph[0][i];if(D[i]!=-1)P[i]=0;elseP[i]=-1;}for(intk=1;k<VEX;k++)//每次從藍點集中取出具有最短特殊路長度的結點min{for(intmin=0;B[min]==0;)min++;for(intj=min;j<VEX;j++)//求藍點集結點最小下標元素

if(D[j]!=-1&&D[j]<D[min]&&B[j]==1)min=j;cout<<"min="<<min<<"";

//將具有最短特殊路長度的結點min添加到紅點集中

R[min]=1;B[min]=0;

//對數(shù)組D作必要的修改

for(j=1;j<VEX;j++)if(graph[min][j]!=-1&&min!=j)//結點min到j間有路

if(D[j]>D[min]+graph[min][j]||D[j]==-1) {D[j]=D[min]+graph[min][j];//每次迭代求最小值，最后一次即為到源點的最短路徑

P[j]=min; }}463.5.2Dijkstra算法Relax描述d[u]:su的距離p[u]:記錄前一節(jié)點Relax松弛算法Init-single-source(G,s)foreachv∈V[G]do{d[v]=∞p[v]=NIL}d[s]=0,p[s]=NILRelax(u,v,w)ifd[v]>d[u]+w(u,v)then{d[v]=d[u]+w[u,v]p[v]=u}

47算法描述dijkstra(G,w,s)1.Init-single-source(G,s)//O(v)2.S=s3.Q=V[G]-S4.whileQ<>Φdou=min(Q)//用數(shù)組O(V)S=S∪{u}Q=V[G]-S

foreachv∈adj[u]&&v∈Q

//O(E)doRelax(u,v,w)483.5.3Bellman-Ford算法dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負邊Bellman-Ford算法的限制條件：不能包含權值總和為負值回路(負權值回路)，如下圖所示。20117-2(c)493.5.3Bellman-Ford算法dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負邊初始化：將除源點外的所有頂點的最短距離估計值d[v]←+∞,d[s]←0;

迭代求解：反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離；（運行|v|-1次）檢驗負權回路：如果存在負環(huán)，則算法返回false，表明問題無解；否則算法返回true，并且從源點可達的頂點v的最短距離保存在d[v]中。503.5.3Bellman-Ford算法思想dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負邊

Init-single-source(G,s)for

i←1to|V[G]|-1//O(V)

3.doforeachedge(u,v)∈E[G]//O(E)

4.doRELAX(u,v,w)

5.foreachedge(u,v)∈E[G]//O(E)6.doif

d[u]+w(u,v)<d[v]

7.thenreturnFALSE//存在負環(huán)

8.returnTRUE存在負權回路的圖是不能求兩點間最短路徑，因為只要在負權回路上不斷兜圈子，所得的最短路長度可以任意小。51d1

[u]為從源點v到終點u的只經(jīng)過一條邊的最短路徑長度，并有dist1[u]=Edge[v][u]；d2

[u]為從源點v最多經(jīng)過兩條邊到達終點u的最短路徑長度；d3

[u]為從源點v出發(fā)最多經(jīng)過不構成負權值回路的三條邊到達終點u的最短路徑長度；……dn-1[u]為從源點v出發(fā)最多經(jīng)過不構成負權值回路的n-1條邊到達終點u的最短路徑長度；算法的最終目的是計算出dn-1

[u]，為源點v到頂點u的最短路徑長度。52遞推公式(求頂點u到源點v的最短路徑)：d1

[u]=Edge[v][u]dk

[u]=min{dk-1

[u],min{dk-1

[j]+Edge[j][u]}},j=0,1,…,n-1,j≠u461230565-2-25-1-1133(c)kdk[0]dk[1]dk[2]dk[3]dk[4]dk[5]dk[6]10655∞∞∞2033554∞301352474013504550135043601350436/3/15/35∞/5/2/0∞/7/5/3∞/4無負環(huán)312056-2-11kdk[0]dk[1]dk[2]dk[3]1065∞2035230332驗證負環(huán)0130有負環(huán)55Dijkstra算法與Bellman算法的區(qū)別Dijkstra算法在求解過程中，源點到集合S內各頂點的最短路徑一旦求出，則之后不變了，修改的僅僅是源點到T集合中各頂點的最短路徑長度。Bellman算法在求解過程中，每次循環(huán)都要修改所有頂點的d[]，也就是說源點到各頂點最短路徑長度一直要到Bellman算法結束才確定下來。563.5.4其他最短路徑問題①單目標最短路徑問題(Single-DestinationShortest-PathsProblem)：找出圖中每一頂點v到某指定頂點u的最短路徑。只需將圖中每條邊反向，就可將這一問題變?yōu)閱卧醋疃搪窂絾栴}，單目標u變?yōu)閱卧袋cu。②單頂點對間最短路徑問題(Single-PairShortest-PathsProblem)：對于某對頂點u和v，找出從u到v的一條最短路徑。顯然，若解決了以u為源點的單源最短路徑問題，則上述問題亦迎刃而解。而且從數(shù)量級來說，兩問題的時間復雜度相同。③所有頂點對間最短路徑問題(All-PairsShortest-PathsProblem)：對圖中每對頂點u和v，找出u到v的最短路徑問題。這一問題可用每個頂點作為源點調用一次單源最短路徑問題算法予以解決。573.6最小生成樹設G=(V,E)是無向連通帶權圖，即一個網(wǎng)絡。E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。網(wǎng)絡的最小生成樹在實際中有廣泛應用。例如，在設計通信網(wǎng)絡時，用圖的頂點表示城市，用邊(v,w)的權c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡的最經(jīng)濟的方案。581、最小生成樹性質用貪心算法設計策略可以設計出構造最小生成樹的有效算法。Prim算法和Kruskal算法2個算法都利用了最小生成樹性質：最小生成樹性質：設G=(V，E)是一個連通網(wǎng)絡，U是頂點集V的一個真子集。若(u，v)是G中所有的一個端點在U(u∈U)里、另一個端點不在U(即v∈V-U)里的邊中，具有最小權值的一條邊，則一定存在G的一棵最小生成樹包括此邊(u，v)。這個性質稱為MST（MinimumSpanningTree）性質。591、最小生成樹性質MST性質的證明：

約定：①集合U中的頂點——紅色頂點②V-U中的頂點——藍色頂點③連接紅點和藍點的邊——紫色邊④權最小的紫邊稱為輕邊(即權重最“輕”的邊)。用反證法證明MST性質601、最小生成樹性質假設G中任何一棵MST都不含輕邊(u，v)。則若T是G的一棵MST，則它不含此輕邊。由于T是包含了G中所有頂點的連通圖，所以T中必有一條從紅點u到藍點v的路徑P，且P上必有一條紫邊(u′

，v′)連接紅點集和藍點集，否則u和v不連通。當把輕邊(u，v)加入樹T時，該輕邊和P必構成了一個回路。刪去紫邊(u′

，v′)后回路亦消除，由此可得另一生成樹T′

。

T′和T的差別僅在于T′用輕邊(u，v)取代了T中權重可能更大的紫邊(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)，這與假設矛盾。

所以，MST性質成立。612、Prim（普里姆）算法設G=(V,E)是連通帶權圖，V={1,2,…,n}。Prim算法構造G的最小生成樹基本思想：初始U={1}只要U是V的真子集，就作如下的貪心選擇：選取滿足條件i∈U，j∈V-U，且c[i][j]最小的邊，將頂點j添加到U中。這個過程一直進行到U=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。622、Prim（普里姆）算法關鍵點思想是：將定點集合分成兩個U，V-U（初始狀態(tài)U中只有一個Uo），再加上一個TE集合來表示最小生成樹邊的集合。632、Prim（普里姆）算法例如，對于右圖中的帶權圖，按Prim算法選取邊的過程如圖所示。642、Prim（普里姆）算法PrimMST(G，T，r)//求圖G的以r為根的MST，結果放在T中{T=φ；U={1};

while(U!=V)//O(V){(i,j)=i∈U，j∈V-U，且c[i][j]最小的邊//O(V)

T=T∪(i，j)//輕邊(i，j)加入T

U=U∪

{j};//節(jié)點j加入U，變?yōu)榧t點

}

}/course_ware/data_structure/web/flashhtml/prim.htm652、Prim（普里姆）算法若候選輕邊集中的輕邊不止一條，可任選其中的一條擴充到T中。若一個藍點與多個紅點有邊相接，選權最小的邊做紫邊。連通網(wǎng)的最小生成樹不一定是惟一的，但它們的權相等。用這個辦法實現(xiàn)的Prim算法所需的計算時間為O(V2)，與圖中邊數(shù)無關，該算法適合于稠密圖。

662、Prim（普里姆）算法如何有效地找出滿足條件i∈U,j∈V-U，且權c[i][j]最小的邊(i,j)？較簡單的辦法是設置2個數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-U中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，將j添加到U中，并對closest和lowcost作必要的修改。673、Kruskal（克魯斯卡爾）算法Kruskal算法構造最小生成樹的基本思想：(1)新建圖G，G中擁有原圖中相同的節(jié)點，但沒有邊(2)將原圖中所有的邊按權值從小到大排序(3）從權值最小的邊開始，如果這條邊連接的兩個節(jié)點于圖G中不在同一個連通分量中，則添加這條邊到圖G中(4)重復(3)，直至圖G中所有的節(jié)點都在同一個連通分量中683、Kruskal（克魯斯卡爾）算法例如，對前面的連通帶權圖，按Kruskal算法順序得到的最小生成樹上的邊如圖所示。693、Kruskal（克魯斯卡爾）算法（1）算法思想

①T的初始狀態(tài)

只有n個頂點而無邊的森林T=(V，￠)

②按邊長遞增的順序選擇E中的n-1安全邊(u，v)并加入T，生成MST

注意：

安全邊指兩個端點分別是森林T里兩棵樹中的頂點的邊。加入安全邊，可將森林中的兩棵樹連接成一棵更大的樹

因為每一次添加到T中的邊均是當前權值最小的安全邊，MST性質也能保證最終的T是一棵最小生成樹703、Kruskal（克魯斯卡爾）算法MST-Kruskal(G)//求連通網(wǎng)G的一棵MST{T=(V，￠)；//初始化，T是只含n個頂點不包含邊的森林//依權值遞增序對E(G)中的邊排序，并設結果在E[0..e-1]中O(Elog(E)

sorttheedgesofEbynon-decreasingweightw

for(i=0;i<e;i++)//e為圖中邊總數(shù)，O(E){

取第i條邊（u,v）

ifu和v分別屬于T中兩棵不同的樹

T=T∪{(u，v)}；//(u，v)是安全邊，將其加入T中

}

returnT；}71說明有關說明：該算法的時間復雜度為O(ElogE)。

Kruskal算法的時間主要取決于邊數(shù)。它較適合于稀疏圖。723.7多機調度問題設有n個獨立的作業(yè){1,2,..,n}，由m臺相同的機器進行加工處理。作業(yè)i所需的處理時間為ti。約定：任何作業(yè)可以在任何一臺機器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的作業(yè)。多機調度問題要求給出一種作業(yè)調度方案，使所給的n個作業(yè)在盡可能短的時間內由m臺機器加工處理完成。733.7多機調度問題這個問題是NP完全問題(Non-deterministicPolynomialCompleteProblem)，也即是多項式復雜程度的非確定性問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設計出較好的近似算法。非確定性問題:無法按部就班直接地計算出來。找大質數(shù)的問題。沒有一個公式，一套公式，就可以一步步推算出來，下一個質數(shù)應該是多少呢？大的合數(shù)分解質因數(shù)的問題，有沒有一個公式，把合數(shù)代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。743.7多機調度問題采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。按此策略，當n≤m時(作業(yè)數(shù)<=機器數(shù))，只要將機器i的[0,ti]時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。當n>m時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序將作業(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。75一個實例例如，設7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產生的作業(yè)調度如下圖所示，所需的總加工時間為17。作業(yè)編號數(shù)據(jù)輸入：首先輸入2個正整數(shù)n和m，分別表示有n個作業(yè)和m臺相同的機器。然后輸入n個正整數(shù)，第i個數(shù)表示作業(yè)i所需的處理時間。#def