第3章算法之貪心算法

第三章算法之貪心算法本章主要知識(shí)點(diǎn)（4~6學(xué)時(shí)）：3.1活動(dòng)安排問(wèn)題3.2貪心算法的基本要素3.3最優(yōu)裝載3.4哈夫曼編碼3.5單源最短路徑3.6最小生成樹(shù)3.7多機(jī)調(diào)度問(wèn)題1引言【找零錢(qián)問(wèn)題】希望用數(shù)目最少的硬幣找零假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。假設(shè)需要找67美分，25+25+10+5+1+1，共6枚。假設(shè)提供了數(shù)目不限的面值為11美分、5美分及1美分的硬幣？找零15美分11+1+1+1+1，共5枚（貪心算法）5+5+5，共3枚（非貪心算法）在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。2引言貪心算法：總是做出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心法的基本思路：

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

3引言貪心法存在的問(wèn)題：

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

2.不能用來(lái)求最大或最小解問(wèn)題；

3.只能求滿足某些約束條件的可行解的范圍。43.1活動(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)都要求使用同一資源，如演講會(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)不相交，則稱(chēng)活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。5復(fù)雜性分析由于輸入的活動(dòng)以其完成時(shí)間的升序排列，所以算法greedySelector每次總是選擇最早完成時(shí)間的相容活動(dòng)加入集合A中。為未安排活動(dòng)留下盡可能多的時(shí)間。該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的活動(dòng)。6一個(gè)實(shí)例例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：7說(shuō)明若被檢查的活動(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é)歸納法證明。8貪心算法描述publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;//選擇最早結(jié)束活動(dòng)intj=1;//j表示已安排活動(dòng)編號(hào)intcount=1;//已安排活動(dòng)數(shù)for(inti=2;i<=n;i++)//i表示待安排活動(dòng){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列9復(fù)雜性分析算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的升序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。103.2貪心算法的基本要素對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。111.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。122.最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。130-1背包問(wèn)題與背包問(wèn)題0-1背包問(wèn)題：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問(wèn)題:與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類(lèi)問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。14貪心方法的數(shù)據(jù)選擇策略1、以?xún)r(jià)值為量度標(biāo)準(zhǔn)按價(jià)值從高到低的次序?qū)⑽锲芬患诺奖嘲小?、以容量作為量度按物品重量的從清到重次序來(lái)把物品放入背包。3、采用單位價(jià)值為度量標(biāo)準(zhǔn)使物品的裝入次序按pi/wi比值的從大到小來(lái)考慮。用貪心策略求解背包問(wèn)題時(shí)，首先要選出最優(yōu)的度量標(biāo)準(zhǔn)。15[算法思路]1).將各物體按單位價(jià)值由高到低排序.2).取價(jià)值最高者放入背包.3).計(jì)算背包剩余空間.4).重復(fù)2-3直到背包剩余容量=0或物體全部裝入背包為止。用貪心算法解背包問(wèn)題的基本步驟16考慮下列情況的背包問(wèn)題n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4個(gè)可行解是：背包問(wèn)題17voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//計(jì)算每種物品單位重量的價(jià)值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];//允許放入一個(gè)物品的一部分}18void0-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背包問(wèn)題貪心選擇之所以不能得到最優(yōu)解：因?yàn)闊o(wú)法保證最終能將背包裝滿，部分閑置的背包空間使總價(jià)值降低了。190-1背包問(wèn)題與背包問(wèn)題102030501.￥602.￥1003.￥1204.背包=￥220=￥160=￥180=￥240100201203060101002060

10120306010100208020120——×2030

0-1背包背包物品價(jià)值及重量20思考題-0/1背包問(wèn)題在雜貨店比賽中你獲得了第一名，獎(jiǎng)品是一車(chē)免費(fèi)雜貨。店中有N種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車(chē)子的容量為C，物品i需占用wi的空間，價(jià)值為pi。你的目標(biāo)是使車(chē)中裝載的物品價(jià)值最大。當(dāng)然，所裝貨物不能超過(guò)車(chē)的容量，且同一種物品不得拿走多件。如何選擇量度標(biāo)準(zhǔn)才能找到最優(yōu)解？若N=2,w=[100,10,10],p=[20,15,15],C=105。利用價(jià)值貪心準(zhǔn)則時(shí)所得結(jié)果是否是最優(yōu)？21問(wèn)題:

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

=cj,i,且ci,i=.一推銷(xiāo)員要從某城市出發(fā)經(jīng)過(guò)每城市一次且僅一次后返回出發(fā)地問(wèn)如何選擇路線使代價(jià)最小。抽象描述:將城市以及之間的道路抽象為一個(gè)無(wú)向圖G,G中每邊的權(quán)值表示這段線路的代價(jià).問(wèn)題轉(zhuǎn)化為求一條最佳周游路線:從一點(diǎn)出發(fā),經(jīng)過(guò)每點(diǎn)一次且僅一次并返回原點(diǎn),且該路線的總代價(jià)最小.C=思考題-旅行商問(wèn)題(TravelingSalesmanProblem)費(fèi)用矩陣22思考題-旅行商問(wèn)題(貨郎擔(dān)問(wèn)題)首先在圖中選一條代價(jià)最小的邊。為了選擇下一條邊，先要檢查一下候選邊與已選入的邊之間是否滿足以下兩點(diǎn)：1)不會(huì)有三條邊(候選邊及已入選邊)與同一頂點(diǎn)相關(guān)聯(lián)。2)不會(huì)使入選邊形成回路，除非入選邊的個(gè)數(shù)已等于圖中的頂點(diǎn)總數(shù)。在滿足以上兩點(diǎn)的候選邊中，挑選最短的邊作為入選邊。如此做下去，直到得到一個(gè)經(jīng)過(guò)所有頂點(diǎn)的回路。最后求得的回路是1—2—5—3—4—1，代價(jià)是14。實(shí)際圖1—1最小代價(jià)的回路是1—2—5—4—3一1，代價(jià)是10。23輸入:城市的數(shù)目n,代價(jià)矩陣c=c(1..n,1..n).輸出:最小代價(jià)路線1.tour:=0;//tour紀(jì)錄路線/2.cost:=0;//cost紀(jì)錄到目前為止的花費(fèi)/3.v:=N;//N為起點(diǎn)城市,v為當(dāng)前出發(fā)城市/4.fork:=1toN-1do5.{tour:=tour+(v,w)//(v,w)為從v到其余城市代價(jià)中值最小的邊/6.cost:=cost+c(v,w)7v:=w}8tour:=tour+(v,N)9cost:=cost+c(v,N)printtour,cost算法的最壞時(shí)間復(fù)雜性為O(n2)*該算法不能求的最優(yōu)解.思考題-旅行商問(wèn)題(貨郎擔(dān)問(wèn)題)243.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為C的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。問(wèn)題可形式化描述為其中變量xi=0表示不裝入集裝箱i，xi=1表示裝入集裝箱i。253.3最優(yōu)裝載[例]設(shè)N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。所考察貨箱的次序?yàn)閠[1..8]={7,3,6,8,4,1,5,2}。貨箱7,3,6,8,4,1的總重量為390個(gè)單位且已被裝載,剩下的裝載能力為10,小于任意貨箱.所以得到解[x1,...x8]=[1,0,1,1,0,1,1,1][算法思路]將裝船過(guò)程劃為多步選擇，每步裝一個(gè)貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱.如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。263.3最優(yōu)裝載算法描述最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(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]];}//調(diào)整剩余空間}27思考設(shè)N=8,[w1，…w8]=[100,200,50,90,150,50,20,80]，C=400。編程求t[1..8].283.4哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。哈夫曼編碼壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。293.4哈夫曼編碼例如一個(gè)包含100,000個(gè)字符的文件，各字符出現(xiàn)頻率不同，如下表所示。定長(zhǎng)編碼需要300,000位，而按表中變長(zhǎng)編碼方案，文件的總碼長(zhǎng)為：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。比用定長(zhǎng)碼方案總碼長(zhǎng)較少約45%。301.前綴碼對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱(chēng)為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。平均碼長(zhǎng)定義為：使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱(chēng)為給定編碼字符集C的最優(yōu)前綴碼。312.構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱(chēng)為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù)T。算法以|C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。322.構(gòu)造哈夫曼樹(shù)構(gòu)造最優(yōu)二叉樹(shù)的算法是由哈夫曼提出的，所以稱(chēng)之為哈夫曼算法，具體敘述如下：根據(jù)與n個(gè)權(quán)值{w1,w2,...,wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹(shù)的森林F={T1,T2,...,Tn},其中每棵二叉樹(shù)Ti(1<=i<=n)都由一個(gè)權(quán)值為wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空；在森林F中選出兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為一棵新樹(shù)的左右子樹(shù)，且置新樹(shù)的附加根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和；從F中刪除這兩棵樹(shù)，同時(shí)把新樹(shù)加入F中；重復(fù)(2)和(3)，直到F中只含有一棵樹(shù)為止。此樹(shù)便是哈夫曼樹(shù)。3334算法說(shuō)明在書(shū)上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。353.5單源最短路徑(Single-SourceShortest-PathsProblem)給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱(chēng)為源。單源最短路徑問(wèn)題：已知圖G＝（V，E），找出從某給定的源結(jié)點(diǎn)S∈V到V中的每個(gè)結(jié)點(diǎn)的最短路徑。363.5.1Dijkstra算法Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法?；舅枷耄涸O(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。（1）初始時(shí)，S中僅含有源節(jié)點(diǎn)。（2）設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱(chēng)為從源到u的特殊路徑，用數(shù)組D[i]記錄頂點(diǎn)i當(dāng)前所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。（3）Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組D作必要的修改。（4）一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。371、Dijkstra算法的基本思想設(shè)S為最短距離已確定的頂點(diǎn)集（紅點(diǎn)集）V-S是最短距離尚未確定的頂點(diǎn)集（藍(lán)點(diǎn)集）。

①初始化

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

②重復(fù)以下工作，按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)最短路徑

在當(dāng)前藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn)來(lái)擴(kuò)充紅點(diǎn)集，以保證算法按路徑長(zhǎng)度遞增的次序產(chǎn)生各頂點(diǎn)的最短路徑。

當(dāng)藍(lán)點(diǎn)集中僅剩下最短距離為∞的藍(lán)點(diǎn)，或者所有藍(lán)點(diǎn)已擴(kuò)充到紅點(diǎn)集時(shí)，s到所有頂點(diǎn)的最短路徑就求出來(lái)了。38一個(gè)實(shí)例39Dijkstra(G，D，s)

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

S={s}；D[s]=0；//設(shè)置初始的紅點(diǎn)集及最短距離

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

//擴(kuò)充紅點(diǎn)集

for(i=1;i<V;i++)//最多擴(kuò)充V-1個(gè)藍(lán)點(diǎn)到紅點(diǎn)集

//O(V)

{

D[k]=min{D[i]：alli∈V-S}；//在藍(lán)點(diǎn)集找特殊距離最小的//頂點(diǎn)kif(D[k]==∞)return；//藍(lán)點(diǎn)集中所有點(diǎn)的特殊距離均為//∞,表示這些頂點(diǎn)的最短路徑不存在

S=S∪{k}；//將藍(lán)點(diǎn)k擴(kuò)充到紅點(diǎn)集

for(allj∈V-S)//調(diào)整剩余藍(lán)點(diǎn)的特殊距離//O(V)

if(D[j]>D[k]+G[k][j])D[j]=D[k]+G[k][j]；}}40#defineVEX5//定義結(jié)點(diǎn)的個(gè)數(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é)點(diǎn)間無(wú)邊相連intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定義數(shù)組D用來(lái)存放結(jié)點(diǎn)特殊距離，P數(shù)組存放父親結(jié)點(diǎn)41//初始時(shí)，紅點(diǎn)集中僅有源結(jié)點(diǎn)0R[0]=1;B[0]=0;for(inti=1;i<VEX;i++)//初始化藍(lán)點(diǎn)集節(jié)點(diǎn)B[i]=1;//對(duì)數(shù)組D、P進(jìn)行初始化for(i=0;i<VEX;i++){D[i]=graph[0][i];if(D[i]!=-1)P[i]=0;elseP[i]=-1;}42for(intk=1;k<VEX;k++)//每次從藍(lán)點(diǎn)集中取出具有最短特殊路長(zhǎng)度的結(jié)點(diǎn)min{for(intmin=0;B[min]==0;)min++;for(intj=min;j<VEX;j++)//求藍(lán)點(diǎn)集結(jié)點(diǎn)最小下標(biāo)元素

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

//將具有最短特殊路長(zhǎng)度的結(jié)點(diǎn)min添加到紅點(diǎn)集中 R[min]=1;B[min]=0;

//對(duì)數(shù)組D作必要的修改for(j=1;j<VEX;j++)if(graph[min][j]!=-1&&min!=j)//結(jié)點(diǎn)min到j(luò)間有路

if(D[j]>D[min]+graph[min][j]||D[j]==-1) {D[j]=D[min]+graph[min][j];//每次迭代求最小值，最后一次即為到源點(diǎn)的最短路徑P[j]=min; }}433.5.2Dijkstra算法Relax描述d[u]:su的距離p[u]:記錄前一節(jié)點(diǎn)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}

44算法描述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}

foreachv∈adj[u]&&v∈Q

//O(E)doRelax(u,v,w)45算法基本思想463.5.3Bellman-Ford算法思想dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負(fù)邊初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值d[v]←+∞,d[s]←0;

迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）檢驗(yàn)負(fù)權(quán)回路：如果存在負(fù)邊，則算法返回false，表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在d[v]中。473.5.3Bellman-Ford算法思想dijkstra算法的前提是所有邊是正的Bellman-Ford算法允許負(fù)邊Init-single-source(G,s)for

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

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

4.do

RELAX(u,v,w)

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

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

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

8.returnTRUE存在負(fù)權(quán)回路的圖是不能求兩點(diǎn)間最短路徑，因?yàn)橹灰谪?fù)權(quán)回路上不斷兜圈子，所得的最短路長(zhǎng)度可以任意小。483.5.4其他最短路徑問(wèn)題①單目標(biāo)最短路徑問(wèn)題(Single-DestinationShortest-PathsProblem)：找出圖中每一頂點(diǎn)v到某指定頂點(diǎn)u的最短路徑。只需將圖中每條邊反向，就可將這一問(wèn)題變?yōu)閱卧醋疃搪窂絾?wèn)題，單目標(biāo)u變?yōu)閱卧袋c(diǎn)u。②單頂點(diǎn)對(duì)間最短路徑問(wèn)題(Single-PairShortest-PathsProblem)：對(duì)于某對(duì)頂點(diǎn)u和v，找出從u到v的一條最短路徑。顯然，若解決了以u(píng)為源點(diǎn)的單源最短路徑問(wèn)題，則上述問(wèn)題亦迎刃而解。而且從數(shù)量級(jí)來(lái)說(shuō)，兩問(wèn)題的時(shí)間復(fù)雜度相同。③所有頂點(diǎn)對(duì)間最短路徑問(wèn)題(All-PairsShortest-PathsProblem)：對(duì)圖中每對(duì)頂點(diǎn)u和v，找出u到v的最短路徑問(wèn)題。這一問(wèn)題可用每個(gè)頂點(diǎn)作為源點(diǎn)調(diào)用一次單源最短路徑問(wèn)題算法予以解決。493.6最小生成樹(shù)設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G’為G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。501、最小生成樹(shù)性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。Prim算法和Kruskal算法2個(gè)算法都利用了最小生成樹(shù)性質(zhì)：最小生成樹(shù)性質(zhì)：設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集。若(u，v)是G中所有的一個(gè)端點(diǎn)在U(u∈U)里、另一個(gè)端點(diǎn)不在U(即v∈V-U)里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹(shù)包括此邊(u，v)。這個(gè)性質(zhì)稱(chēng)為MST（MinimumSpanningTree）性質(zhì)。511、最小生成樹(shù)性質(zhì)MST性質(zhì)的證明：

約定：①集合U中的頂點(diǎn)——紅色頂點(diǎn)②V-U中的頂點(diǎn)——藍(lán)色頂點(diǎn)③連接紅點(diǎn)和藍(lán)點(diǎn)的邊——紫色邊④權(quán)最小的紫邊稱(chēng)為輕邊(即權(quán)重最“輕”的邊)。用反證法證明MST性質(zhì)521、最小生成樹(shù)性質(zhì)假設(shè)G中任何一棵MST都不含輕邊(u，v)。則若T是G的一棵MST，則它不含此輕邊。由于T是包含了G中所有頂點(diǎn)的連通圖，所以T中必有一條從紅點(diǎn)u到藍(lán)點(diǎn)v的路徑P，且P上必有一條紫邊(u′，v′)連接紅點(diǎn)集和藍(lán)點(diǎn)集，否則u和v不連通。當(dāng)把輕邊(u，v)加入樹(shù)T時(shí)，該輕邊和P必構(gòu)成了一個(gè)回路。刪去紫邊(u′，v′)后回路亦消除，由此可得另一生成樹(shù)T′。

T′和T的差別僅在于T′用輕邊(u，v)取代了T中權(quán)重可能更大的紫邊(u′，v′)。因?yàn)閣(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ì)成立。532、Prim（普里姆）算法設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹(shù)的Prim算法的基本思想是：首先置U={1}，然后，只要U是V的真子集，就作如下的貪心選擇：選取滿足條件i∈U，j∈V-U，且c[i][j]最小的邊，將頂點(diǎn)j添加到U中。這個(gè)過(guò)程一直進(jìn)行到U=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如圖所示。542、Prim（普里姆）算法PrimMST(G，T，r)//求圖G的以r為根的MST，結(jié)果放在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é)點(diǎn)j加入U(xiǎn)，變?yōu)榧t點(diǎn)

}

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

562、Prim（普里姆）算法如何有效地找出滿足條件i∈U,j∈V-U，且權(quán)c[i][j]最小的邊(i,j)？較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。在Prim算法執(zhí)行過(guò)程中，先找出V-U中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，將j添加到U中，并對(duì)closest和lowcost作必要的修改。573、Kruskal（克魯斯卡爾）算法Kruskal算法構(gòu)造最小生成樹(shù)的基本思想：(1)將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。(2)將所有的邊按權(quán)從小到大排序。(3)從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹(shù)上的邊如圖所示。583、Kruskal（克魯斯卡爾）算法（1）算法思想

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

只有n個(gè)頂點(diǎn)而無(wú)邊的森林T=(V，￠)

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

注意：

安全邊指兩個(gè)端點(diǎn)分別是森林T里兩棵樹(shù)中的頂點(diǎn)的邊。加入安全邊，可將森林中的兩棵樹(shù)連接成一棵更大的樹(shù)

因?yàn)槊恳淮翁砑拥絋中的邊均是當(dāng)前權(quán)值最小的安全邊，MST性質(zhì)也能保證最終的T是一棵最小生成樹(shù)593、Kruskal（克魯斯卡爾）算法MST-Kruskal(G)//求連通網(wǎng)G的一棵MST{T=(V，￠)；//初始化，T是只含n個(gè)頂點(diǎn)不包含邊的森林//依權(quán)值遞增序?qū)(G)中的邊排序，并設(shè)結(jié)果在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中兩棵不同的樹(shù)

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

}

returnT；}60說(shuō)明有關(guān)說(shuō)明：該算法的時(shí)間復(fù)雜度為O(ElogE)。

Kruskal算法的時(shí)間主要取決于邊數(shù)。它較適合于稀疏圖。613.7多機(jī)調(diào)度問(wèn)題設(shè)有n個(gè)獨(dú)立的作業(yè){1,2,..,n}，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti。約定：任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的作業(yè)。多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。623.7多機(jī)調(diào)度問(wèn)題這個(gè)問(wèn)題是NP完全問(wèn)題(Non-deterministicPolynomialCompleteProblem)，也即是多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題，到目前為止還沒(méi)有有效的解法。對(duì)于這一類(lèi)問(wèn)題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。非確定性問(wèn)題:無(wú)法按部就班直接地計(jì)算出來(lái)。比如，找大質(zhì)數(shù)的問(wèn)題。沒(méi)有一個(gè)公式，一套公式，就可以一步步推算出來(lái)，下一個(gè)質(zhì)數(shù)應(yīng)該是多少呢？再比如，大的合數(shù)分解質(zhì)因數(shù)的問(wèn)題，有沒(méi)有一個(gè)公式，把合數(shù)代進(jìn)去，就直接可以算出，它的因子各自是多少？也沒(méi)有這樣的公式。633.7多機(jī)調(diào)度問(wèn)題采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。按此策略，當(dāng)n≤m時(shí)(作業(yè)數(shù)<=機(jī)器數(shù))，只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時(shí)間。當(dāng)n>m時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為O(nlogn)。64一個(gè)實(shí)例例如，設(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)度如下圖所示，所需的總加工時(shí)間為17。作業(yè)編號(hào)65數(shù)據(jù)輸入：首先輸入2個(gè)正整數(shù)n和m，分別表示有n個(gè)作業(yè)和m臺(tái)相同的機(jī)器。然后輸入n個(gè)正整數(shù)，第i個(gè)數(shù)表示作業(yè)i所需的處理時(shí)間。#defineN10//作業(yè)數(shù)#defineM3//機(jī)器數(shù)staticinttime[N]={2,8,18,32,50,72,98,128,182,200}；ints[M]={0,0,0};//S數(shù)組存儲(chǔ)每