貪心算法-課件

將問題的求解過程看作是一系列選擇,每次選擇一個輸入,每次選擇都是當前狀態(tài)下的最好選擇(局部最優(yōu)解).每作一次選擇后,所求問題會簡化為一個規(guī)模更小的子問題.從而通過每一步的最優(yōu)解逐步達到整體的最優(yōu)解。4.1基本思想[算法優(yōu)點]求解速度快,時間復雜性有較低的階.[算法缺點]需證明是最優(yōu)解.[常見應用]背包問題,最小生成樹,最短路徑,作業(yè)調(diào)度等等將問題的求解過程看作是一系列選擇,每次選擇一個輸入,1[適用問題]具備貪心選擇和最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問題貪心選擇性質(zhì)：整體的最優(yōu)解可通過一系列局部最優(yōu)解達到，即貪心選擇到達。貪心算法通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求解的問題化簡為規(guī)模更小的問題對于一個具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終導致問題的最優(yōu)解。通常可以首先證明問題的一個整體最優(yōu)解，是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)：當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。[適用問題]具備貪心選擇和最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問題2A(1)A(2)…A(n-1)A(n)某一問題的n個輸入B1(1)B1(2)…B1(m)該問題的一種解（可行解）是A的一個子集滿足一定的條件約束條件Bk(1)Bk(2)…Bk(m)…目標函數(shù)取極值最優(yōu)解算法設計與分析>

貪心算法A(1)A(2)…A(n-1)A(n)某一問題的n個輸入B134.2.活動安排問題算法設計與分析>

貪心算法活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。[問題陳述]設有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是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。4.2.活動安排問題算法設計與分析>貪心算法活動安排問題4

1234567891011[例]130535688212

4567891011121314is[i]f[i]設待安排的11個活動起止時間按結(jié)束時間的非減序排列最大相容活動子集(1,4,8,11),也可表示為等長n元數(shù)組:(1,0,0,1,0,0,0,1,0,0,1)[算法思路]將n個活動按結(jié)束時間非減序排列,依次考慮活動i,若i與已選擇的活動相容,則添加此活動到相容活動子集.123455活動安排問題貪心算法template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;

//從第二個活動開始檢查是否與前一個相容

for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}算法設計與分析>

貪心算法各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列

活動安排問題貪心算法template<classType6

算法greedySelector的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。算法greedySelector的計算過程如左圖所示。圖7由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。算法greedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。T(n)=O(nlogn)(未排序時)[算法分析]

T(n)=O(n)(排序時)[算法證明]算法達到最優(yōu)解.由于輸入的活動以其完成時間的非減序排列，所以算法greedy8[問題描述]輸入:(x1,x2,...xn),xi=0,貨箱i不裝船;xi=1,貨箱i裝船可行解:滿足約束條件≤c的輸入優(yōu)化函數(shù):

最優(yōu)解:使優(yōu)化函數(shù)達到最大值的一種輸入.4.3最優(yōu)裝載算法設計與分析>

貪心算法[算法思路]將裝船過程劃為多步選擇，每步裝一個貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱.如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。[例]設n=8，[w1，…w8]=[100,200,50,90,150,50,20,80]，c=400。所考察貨箱的次序為: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][問題描述]輸入:(x1,x2,...xn),xi=91、最優(yōu)裝載的貪心算法算法設計與分析>

貪心算法template<classType>voidLoading(intx[],Typew[],Typec,intn){ int*t=newint[n+1]; Sort(w,t,n);//按貨箱重量排序/ for(inti=1;i<=n;i++) x[i]=0; for(inti=1;i<=n&&w[t[i]]<=c;i++) { x[t[i]]=1;c-=w[t[i]];//調(diào)整剩余空間

}}1、最優(yōu)裝載的貪心算法算法設計與分析>貪心算法templ102、貪心選擇性質(zhì) 可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

算法證明:由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。

算法分析:算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。

2、貪心選擇性質(zhì)11[最優(yōu)化描述]

找一個n元向量(x1,…xn)0

xi

1

使得且.其中C,Wi,vi>0,1

i

n4-4

背包問題

(KnapsackProblem)[問題描述]設有n個物體和一個背包,物體i的重量為wi,價值為vi,背包的容量為C.若將物體i的xi部分(1

i

n,0

xi

1)裝入背包,則具有價值為vi

xi.目標是找到一個方案,使放入背包的物體總價值最高.約束條件優(yōu)化函數(shù)算法設計與分析>

貪心算法[最優(yōu)化描述]找一個n元向量(x1,…xn)0xi12背包問題實例考慮下列情況的背包問題n=3,M=20,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)其中的4個可行解是：(x1,x2,x3)∑wixi∑vixi①(1/2,1/3,1/4)16.524.25②(1,2/15,0)2028.2③(0,2/3,1)2031④(0,1,1/2)2031.5算法設計與分析>

貪心算法背包問題實例考慮下列情況的背包問題(x1,x2,x3)∑wi13貪心方法的數(shù)據(jù)選擇策略(1)1、用貪心策略求解背包問題時，首先要選出最優(yōu)的度量標準?？梢赃x取目標函數(shù)為量度標準，每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標準下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲?。如上面的實例所示，可將物品按效益量非增次序排序?v1,v2,v3)=(25,24,15)。先裝入物品1重量為18，即x1=1；然后再裝物品2，由于約束條為∑wixi≤M=20，所以物品2只能裝入重量為2的一小部分，即x2=2/15。按上述的數(shù)據(jù)選擇策略，裝入順序是按照物品的效益值從大到小的輸入，由剛才的方法可得這種情況下的總效益值為∑vixi=25+24*2/15=28.2，顯然是一個次優(yōu)解，原因是背包容量消耗過快。算法設計與分析>

貪心算法貪心方法的數(shù)據(jù)選擇策略(1)1、用貪心策略求解背包問題時，首14貪心方法的數(shù)據(jù)選擇策略(2)2、若以容量作為量度，可讓背包容量盡可能慢地被消耗。這就要求按物品重量的非降次序來把物品放入背包，即(w3,w2,w1)=(10,15,18)。先裝入物品3,x3=1,p3x3=15，再裝入重量為10的物品2，∑vixi=15+24*10/15=31。由剛才的方法可得這種情況下的總效益值為31，仍是一個次優(yōu)解，原因是容量在漫漫消耗的過程中，效益值卻沒有迅速的增加。算法設計與分析>

貪心算法貪心方法的數(shù)據(jù)選擇策略(2)2、若以容量作為量度，可讓背包容15貪心方法的數(shù)據(jù)選擇策略(3)3、采用在效益值的增長速率和容量的消耗速率之間取得平衡的量度標準。即每一次裝入的物品應使它占用的每一單位容量獲得當前最大的單位效益。這就需使物品的裝入次序按vi/wi比值的非增次序來考慮。這種策略下的量度是已裝入物品的累計效益值與所用容量之比。(v2/w2,

v3/w3,

v1/w1)=(24/15,15/10,25/18)先裝入重量為15的物品2，在裝入重量為5的物品3，∑pixi=24+15*5/10=31.5。此結(jié)果為最優(yōu)解。算法設計與分析>

貪心算法貪心方法的數(shù)據(jù)選擇策略(3)3、采用在效益值的增長速率和容量16[算法思路]1).將各物體按單位價值由高到低排序.2).取價值最高者放入背包.3).計算背包剩余空間.4).在剩余物體中取價值最高者放入背包.

若背包剩余容量=0或物體全部裝入背包為止[例]n=3,c=20(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10){x1,x2,x3}{0,2/3,1}{0,1,1/2}{...}{1,2/15,0}20202028.23131.5......算法設計與分析>

貪心算法[算法思路]1).將各物體按單位價值由高到低排序.[例]17voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){ Sort(n,v,w,t);//按單位價值排序/ inti; for(i=1;i<=n;i++) x[i]=0; floatc=M;//c為背包剩余空間/ for(i=1;i<=n;i++) {if(w[t[i]]>c) break; x[t[i]]=1; c-=w[t[i]];

} if(i<=n) x[t[i]]=c/w[t[i]];}背包問題的貪心算法算法設計與分析>

貪心算法voidKnapsack(intn,floatM,fl18算法分析:

排序為主要算法時間,所以T(n)=O(nlogn)

背包問題中的物體不能分拆,只能整個裝入稱為0-1背包問題.算法證明:該算法能得到在最優(yōu)解用貪心算法能得到0-1背包的最優(yōu)解嗎?

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。具體算法可描述如下頁：

算法分析:排序為主要算法時間,所以T(n)=O(nlo19voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){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];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。voidKnapsack(intn,floatM,fl20對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種21思考題0/1背包問題：在雜貨店比賽中你獲得了第一名，獎品是一車免費雜貨。店中有n種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為c，物品i需占用wi

的空間，價值為pi。你的目標是使車中裝載的物品價值最大。當然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。如何選擇量度標準才能找到最優(yōu)解？算法設計與分析>

貪心算法思考題0/1背包問題：在雜貨店比賽中你獲得了第一名，獎品是一22思考題找零錢問題：一個小孩買了價值為33美分的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。使用貪心算法求解最優(yōu)結(jié)果。并證明找零錢問題的貪心算法總能產(chǎn)生具有最少硬幣數(shù)的零錢。算法設計與分析>

貪心算法思考題找零錢問題：一個小孩買了價值為33美分的糖，并將1美元23問題:通訊過程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進制碼.由于英文字母使用頻率不同,若頻率高的字母對應短的編碼,頻率低的字母對應長的編碼,傳輸?shù)臄?shù)據(jù)總量就會降低.要求找到一個編碼方案,使傳輸?shù)臄?shù)據(jù)量最少.

見P109-表4-1

算法設計與分析>

貪心算法1、前綴碼為能正確譯碼,編碼需采用前綴碼,

對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點都有2個兒子結(jié)點。平均碼長定義為：使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。4.4哈夫曼編碼問題:通訊過程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進制碼.由于英文字母使24算法思路：1)以n個字母為結(jié)點構(gòu)成n棵僅含一個點的二叉樹集合,字母的頻率即為結(jié)點的權(quán)．2)每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹:增加一個根結(jié)點將這兩棵樹作為左右子樹.新樹的權(quán)為兩棵子樹的權(quán)之和.3)反復進行步驟2)直到只剩一棵樹為止.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)造哈夫曼編碼25算法設計與分析>貪心算法>哈夫曼編碼算法設計與分析>貪心算法>哈夫曼編碼26

template<classT>BinaryTree<int>HuffmanTree(Tf[],intn){//根據(jù)權(quán)f[1:n]構(gòu)造霍夫曼樹

//創(chuàng)建一個單節(jié)點樹的數(shù)組

Huffman<T>*W=newHuffman<T>[n+1]；

BinaryTree<int>z,zero；

for(inti=1；i<=n；i++){z.MakeTree(i,zero,zero)；

W[i].weight=f[i]；

W[i].tree=z:}

//數(shù)組變成—個最小堆

MinHeap<Huffman<T>>Q(1)；

Q.Initialize(w,n,n)；

//將堆中的樹不斷合并

Huffman<T>x,yfor(i=1;i<n;i++){

Q.DeleteMin(x)；

Q.DeleteMin(y)；

z.MakeTree(0,x.tree,y.tree)；

x.weight+=y.weight；x.tree=z；

Q.Insert(x)；}Q.DeleteMin(x)；//最后的樹

Q.Deactivate()；

delete[]w；

returnx.tree；哈夫曼樹算法算法設計與分析>貪心算法>哈夫曼編碼template<classT>Q.Del27 在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的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)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。 在書上給出的算法huffmanTree中，編碼字符集28最優(yōu)子結(jié)構(gòu):

設T為帶權(quán)w1≤w2≤...≤wt的最優(yōu)樹,若將以帶權(quán)w1和w2的樹葉為兒子的分枝點改為帶權(quán)w1+w2的樹葉,得到一棵新樹T',則T'也是最優(yōu)樹。貪心選擇性

:設T為帶權(quán)w1≤w2≤...≤wt的最優(yōu)樹,a).帶權(quán)w1和w2的樹葉vw1和vw2是兄弟.b).以vw1和vw2為兒子的分枝點,其通路長度最長.算法證明算法分析HuffmanTree初始化優(yōu)先隊列Q需要O(n)DeleteMin和Insert需O(logn).n-1次的合并總共需要O(nlogn)所以n個字符的哈夫曼算法的計算時間為O(nlogn)算法設計與分析>貪心算法>哈夫曼編碼最優(yōu)子結(jié)構(gòu):設T為帶權(quán)w1≤w2≤...≤wt的最294.5單源最短路徑問題:

給定帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是一個非負實數(shù).要計算從V的一點v0(源)到所有其他各頂點的最短路長度.路長指路上各邊權(quán)之和。

算法設計與分析>

貪心算法算法思路(Dijkstra):設最短路長已知的終點集合為S,初始時v0

S,其最短路長為0,然后用貪心選擇逐步擴充S:每次在V-S中,選擇路徑長度值最小的一條最短路徑的終點x加入S.例題構(gòu)造路長最短的最短路徑:設已構(gòu)造i條最短路徑,則下一個加入S的終點u必是V-S中具有最小路徑長度的終點,其長度或者是弧(v0,u),或者是中間只經(jīng)過S中的頂點而最后到達頂點u的路徑.例題4.5單源最短路徑算法設計與分析>貪心算法算法思路(D30 已知一個n結(jié)點的有向圖G=(V,E)和邊的權(quán)函數(shù)c(e)，求由G中某指定結(jié)點v0到其他各個結(jié)點的最短路徑。v0v2v1v3v4v5204550101515201035303路徑長度(1)v0v210(2)v0v2v325(3)v0v2v3v145(4)v0v445算法設計與分析>

貪心算法 已知一個n結(jié)點的有向圖G=(V,E)和邊的權(quán)函數(shù)c(e31產(chǎn)生最短路徑的貪心方法逐條構(gòu)造這些最短路徑，使用迄今已生成的所有路徑長度之和作為一種量度標準。為了使這一量度達到最小，其單獨的每一條路徑都必須具有最小長度。使用這標準時，假定已構(gòu)造了i條最短路徑，則下面要構(gòu)造的路徑應該是下一條最短的最小長度路徑。生成從v0到所有其它結(jié)點的最短路徑的貪心方法就是按照路徑長度的非降次序生成這些路徑。算法設計與分析>

貪心算法產(chǎn)生最短路徑的貪心方法逐條構(gòu)造這些最短路徑，使用迄今已生成的32產(chǎn)生最短路徑的貪心方法設S表示對其已經(jīng)生成了最短路徑的那些結(jié)點(包括v0)的集合。擴張S的過程：對于不在S中的結(jié)點w，設DIST(w)是從v0開始只經(jīng)過S中的結(jié)點而在結(jié)點w結(jié)束的那條最短路徑的長度，則有：如果下一條最短路徑是到結(jié)點u，則這條路徑是從v0處開始而在u處終止，并且只通過那些在S中的結(jié)點。所生成的下一條路徑的終點u必定是所有不在S內(nèi)的結(jié)點中具有最小距離DIST(u)的結(jié)點。算法設計與分析>

貪心算法產(chǎn)生最短路徑的貪心方法設S表示對其已經(jīng)生成了最短路徑的那些結(jié)33產(chǎn)生最短路徑的貪心方法選出了結(jié)點u并生成了從v0到u的最短路徑之后，結(jié)點u就成為S中的一個成員。此時，那些從v0開始，只通過S中的結(jié)點并且在S外的結(jié)點w處結(jié)束的最短路徑可能會減小。如果長度改變了，則它必定是由一條從v0開始，經(jīng)過u然后到w的更短路徑所造成的。其中從v0到u的路徑是一條最短路徑，從u到w的路徑是邊<u,w>，于是這條路徑的長度就是：DIST(u)+c(u,w)算法設計與分析>

貪心算法產(chǎn)生最短路徑的貪心方法選出了結(jié)點u并生成了從v0到u的最短路34算法設計與分析>

貪心算法

算法描述：

(1)用帶權(quán)的鄰接矩陣c來表示帶權(quán)有向圖,c[i][j]表示弧<vi,vj>

上的權(quán)值.若<vi,vj>V,則置c[i][j]為

設S為已知最短路徑的終點的集合,它的初始狀態(tài)為空集.

從源點v到圖上其余各點vi的當前最短路徑長度的初值為：

dist[i]=c[v][i]，vi

V(2)選擇vj,使得dist[j]=Min{dist[i]|vi

V-S}vj就是長度最短的最短路徑的終點。令S=SU{j}//更新S(3)修改從v到集合V-S上任一頂點vk的當前最短路徑長度:

如果dist[j]+c[j][k]<dist[k]則修改dist[K]=dist[j]+c[j][k]//更新dist和prev(4)重復操作(2),(3)共n-1次.算法設計與分析>貪心算法算法描述：35算法設計與分析>

貪心算法>單源最短路徑例題1)v1

v2:102)v1

v3:503)v1

v4:304)v1

v5:60算法設計與分析>貪心算法>單源最短路徑例題1)v136算法設計與分析>

貪心算法

voidDijkstra(intn,intv,Typedist[],intprev[],Type**c){bools[maxint]；

for(inti=1;i<=n;i++){dist[i]=c[v][i]；

s[i]=false；

if(dist[i]==maxint)prev[i]=0；

elseprev[i]=v;}dist[v]=0；s[v]=true；

for(inti=1;i<n；i++){inttemp=maxint；

intu=v；

for(intj=1；j<=n；j++)

if((!s[j])&&(dist[j]<temp)){u=j；

temp=dist[j]；}s[u]=true；

for(intj=1；j<=n;j++)；

if((!s[j])＆＆(c[u][j]<maxint)){Typenewdist=dist[u)+c[u][j];if(newdist<dist[j]){dist[]]=newdist；

prev[j]=u;}}}}單源最短路徑問題的Dijkstra算法分析:用帶權(quán)鄰接矩陣表示有n個頂點和e條邊的帶權(quán)有向圖,主循環(huán)體需要O(n)時間,循環(huán)需要執(zhí)行n-1次,所以完成循環(huán)需要O(n2).算法設計與分析>貪心算法voidDijkstra(in37算法設計與分析>

貪心算法>單源最短路徑例題1)v1

v2:102)v1

v3:503)v1

v4:304)v1

v5:60算法設計與分析>貪心算法>單源最短路徑例題1)v138算法實例求下圖中v1到其余各結(jié)點的最短路徑v1v4v2v3v6v7v52030504055257050251070500205030∞∞∞∞025∞∞70∞∞∞0402550∞∞∞∞055∞∞∞∞∞∞01070∞∞∞∞∞050∞∞∞∞∞∞0算法設計與分析>

貪心算法算法實例求下圖中v1到其余各結(jié)點的最短路徑v1v4v2v3v39算法實例迭代選取結(jié)點SDIST(1)(2)(3)(4)(5)(6)(7)置初值--10205030∞∞∞121,20204530∞90∞231,2,402045308590∞341,2,4,302045307090∞451,2,4,3,502045307080140561,2,4,3,5,602045307080130SHORTEST-PATHS執(zhí)行蹤跡算法設計與分析>

貪心算法算法實例迭代選取SDIST(1)(2)(3)(4)(5)(640算法設計與分析>

貪心算法>最小生成樹問題陳述:設G(V,E)是一個無向連通帶權(quán)圖。E中每條邊(v,w)的權(quán)為c[v][w],若G的一個子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹各邊權(quán)的總和稱為該生成樹的耗費。在G的所有生成樹中,耗費最小的生成樹稱為G的最小生成樹.抽象描述:輸入:任一連通生成子圖(該子圖的邊集合)

可行解:圖的生成樹,

優(yōu)化函數(shù):生成樹的各邊權(quán)值之和最優(yōu)解:使優(yōu)化函數(shù)達到最小的生成樹.4.6最小生成樹算法設計與分析>貪心算法>最小生成樹問題陳述:設G(V41算法設計與分析>

貪心算法>最小生成樹應用領(lǐng)域與圖模型算法設計與分析>貪心算法>最小生成樹應用領(lǐng)域與圖模型42算法思路:首先置S={1},T=?.若S

V,就作如下的貪心選擇：選取滿足條件i

S,j

V-S,且c[i][j]最小的邊(i,j),將頂點j添加到S中邊(i,j)添加到T中.這個過程一直進行到S=V時為止.T中的所有邊構(gòu)成G的一棵最小生成樹。voidPrim(intn,Type**c){T=?;S={1};while(S!=V){(i,j)=i

S且j

V-S的最小權(quán)邊;T=TU{(i,j)};S=SU{j};}}算法描述

Prim算法設G=(V,E)是一個連通帶權(quán)圖,y={l,2,…,n}。例題算法設計與分析>

貪心算法>最小生成樹算法思路:首先置S={1},T=?.若SV,就作43問題：如何選取滿足條件i

S,j

V-S,且c[i][j]最小的邊(i,j),成了算法難點問題。解決方法：設置兩個數(shù)組closest和lowcost。對于每個j

V-S，closest[j]是j在S中的鄰接頂點，它與j在S中的其他鄰接頂點k相比較有c[j][closet[j]]≤c[j][k]。lowcost[j]的值就是c[j][closest[j]]問題：如何選取滿足條件iS,jV-S,且c[i][j]44圖Prim算法的執(zhí)行過程注：灰色部分表示集合S

每個結(jié)點的上的數(shù)字表示S中的結(jié)點到該結(jié)點的最小消耗，即lowcost

用圖示的邊的連接表示closest圖Prim算法的執(zhí)行過程注：灰色部分表示集合S45圖Prim算法的執(zhí)行過程圖Prim算法的執(zhí)行過程46圖Prim算法的執(zhí)行過程圖Prim算法的執(zhí)行過程47圖Prim算法的執(zhí)行過程圖Prim算法的執(zhí)行過程48圖4-16Prim算法的執(zhí)行過程圖4-16Prim算法的執(zhí)行過程49圖4-16Prim算法的執(zhí)行過程圖4-16Prim算法的執(zhí)行過程50template<classType>voidPrim(intn,Type**c){Typelowcost[maxint];intclosest[maxim];bools[maxint];s[1]=true;for(inti=2;i<=n;i++){lowcost[i]=c[l][i];closest[i]=1;s[i]=false;}for(inti=1;i<n;i++){

Typemin=inf;intj=1;for(intk=2;k<=n;k++)if((lowcost[k]<min)&&(!s[k]))min=lowcost[k];j=k;}cout<<j<<''<<closest[j]<<end};s[j]=true;for(intk=2;k<=n;k++)if((c[j][k]<lowcost[k])&&(!s[k]))lowcost[i]=c[j][k];closest[k]=j;}}}Prim算法算法分析:O(n2).算法設計與分析>

貪心算法>最小生成樹template<classType>T51算法思路:首先將G的n個頂點看成n個孤立的連通分支,將所有的邊按權(quán)從小到大排序,

然后從第一條邊開始,依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個通分支： 當查看到第k條邊(v,w)時,如果端點u和w分別是當前兩個不同的連通分支T1,T2中的頂點時,就用邊(u,w)將TI和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊;

如果端點v和w在當前的同一個連通分支中，就直接再查看第k十1條邊。直到只剩下一個連通分支為止。 此時，這個連通分枝就是G的一顆最小生成樹

Kruskal算法

G=(V,E),V=<1,2,…,n}。例題算法設計與分析>

貪心算法>最小生成樹算法思路:首先將G的n個頂點看成n個孤立的連通分支,將所有52e1(1)e2(6)e8(9)e6(2)e9(4)e5(5)e4(7)e10(8)e11(3)e7(10)e3(11)1)以G中全部點為點作圖2)按權(quán)的大小次序依次添加各邊,若出現(xiàn)回路則忽略此邊.3)加入n-1條邊后就得到最小生成樹.12537求最小生成樹(Kruscal)最優(yōu)解:(e1,e6,e11,e5,e4)e1(1)e2(6)e8(9)e6(2)e9(4)e5(553例題算法設計與分析>

貪心算法>最小生成樹例題算法設計與分析>貪心算法>最小生成樹54優(yōu)先隊列定義：優(yōu)先隊列中元素出隊列的順序由元素的優(yōu)先級決定。從優(yōu)先隊列中刪除元素是根據(jù)優(yōu)先權(quán)高或低的次序，而不是元素進入隊列的次序?？梢岳枚褦?shù)據(jù)結(jié)構(gòu)來高效地實現(xiàn)優(yōu)先隊列。實現(xiàn)：優(yōu)先隊列（priorityqueue）是0個或多個元素的集合，每個元素都有一個優(yōu)先權(quán)或值，對優(yōu)先隊列執(zhí)行的操作有1)查找；2)插入一個新元素；3)刪除。在最小優(yōu)先隊列（minpriorityqueue）中，查找操作用來搜索優(yōu)先權(quán)最小的元素，刪除操作用來刪除該元素；對于最大優(yōu)先隊列（maxpriorityqueue），查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。處理：優(yōu)先權(quán)隊列中的元素可以有相同的優(yōu)先權(quán)，查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進行。優(yōu)先隊列定義：優(yōu)先隊列中元素出隊列的順序由元素的優(yōu)先級決定。55Initialize函數(shù)：使用數(shù)組a中的元素對最大堆進行初始化。DeleteMin(x)：從隊列中刪除具有最小優(yōu)先權(quán)的元素，并將該元素返回至xInsert(x)：將x插入隊列Initialize函數(shù)：使用數(shù)組a中的元56并查集在一些應用問題中，我們需要劃分n個不同的元素成若干組，每一組的元素構(gòu)成一個集合。這種問題的一個解決辦法是，在開始時，讓每個元素自成一個單元素集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并。其間要反復用到查找一個元素在哪一個集合的運算。適合于描述這類問題的抽象數(shù)據(jù)類型稱為并查集

(給出各個元素之間的聯(lián)系，要求將這些元素分成幾個集合，每個集合中的元素直接或間接有聯(lián)系。在這類問題中主要涉及的是對集合的合并和查找，因此將這種集合稱為并查集。)并查集在一些應用問題中，我們需要劃分n個不同的57并查集的數(shù)學模型

并查集的數(shù)學模型是若干不相交的動態(tài)集合的集合S＝{A,B,C,...}，它支持以下的運算：

(1)INITIAL(A,x)：構(gòu)造一個取名為A的集合，它只包含一個元素x；

(2)MERGE(A,B)：將集合A和B合并，其結(jié)果取名為A或B；

(3)FIND(x)：找出元素x的所在集合，并返回該集合的名字。并查集的數(shù)學模型

并查集的數(shù)學模型是若干不相交的動態(tài)集合的58template<classType>boolKruskal(intn,inte,EdgeNode<Type>E[],EdgeNode<Type>t[])MinHeap<EdgeNode<Type>>H(1);H.Initialize(E,e,e);UnionFindU(n);ihtk=0;while(e&&k<n-1){EdgeNode<int>x;x.u=2;x.v=1;x.weight=5;H.DeleteMin(x);

e--;inta=U.Find(x.u);intb=U.Eind(x.v);if(a!=b){t[k++]=x;U.Union(a,b);H.Deactivate()renturn(k==n-1)Kruska算法算法設計與分析>

貪心算法>最小生成樹template<classType>e59A=Φ（選出的邊）E={(h,g,1),(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}（原圖中的邊）初始狀態(tài)森林由9棵樹組成A={(h,g)}E={(g,f,2),(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}接受邊(h,g)UNION(g,h)森林由8棵樹組成（a）（b）A=Φ（選出的邊）E={(h,g,1),(g,f,2),(60圖Kruskal算法的執(zhí)行過程E={(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}（c）E={(c,i,2),(a,b,4),(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}（d）接受邊(c,i)UNION(c,i)森林由6棵樹組成接受邊(g,f)UNION(g,f)森林由7棵樹組成圖Kruskal算法的執(zhí)行過程E={(c,i,2),(61圖Kruskal算法的執(zhí)行過程E={(c,f,4),(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}接受邊(a,b)UNION(a,b)森林由5棵樹組成圖Kruskal算法的執(zhí)行過程E={(c,f,4),(62圖Kruskal算法的執(zhí)行過程E={(g,I,6),(c,d,7),(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}E={(a,h,8),(b,c,8),(d,e,9),(e,f,10),(b,h,11),(d,f,14)}接受邊(c,f)UNION(c,f)森林由4棵樹組成選取邊（g,I,6）但因為g和i在一個連通子圖中，即U.Find(g)和U.Find(i)相同，所以拒絕邊(g,i)

接受邊(c,d)UNION(c,d)

森林由3棵樹組成圖Kruskal算法的執(zhí)行過程E={(g,I,6),(63圖Kruskal算法的執(zhí)行過程(續(xù))拒絕邊(h,i)

接受邊(a,h)UNION(a,h)

森林由2棵樹組成拒絕邊(b,c)

接受邊(d,e)UNION(d,e)

森林由1棵樹組成圖Kruskal算法的執(zhí)行過程(續(xù))拒絕邊(h64圖Kruskal算法的執(zhí)行過程(續(xù))圖Kruskal算法的執(zhí)行過程(續(xù))65正確性證明1、需要證明以下兩點：

1)只要存在生成樹，Kruskal算法總能產(chǎn)生一棵生成樹；2)產(chǎn)生的生成樹具有最小耗費。2、證明1： 令G為任意加權(quán)無向圖（即G是一個無向網(wǎng)絡）。從12.11.3節(jié)可知當且僅當一個無向圖連通時它有生成樹。而且在Kruskal算法中被拒絕（丟棄）的邊是那些會產(chǎn)生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖，因此如果G在開始時是連通的，則T與E中的邊總能形成一個連通圖。也就是若G開始時是連通的，算法不會終止于E=和|T|<n-1。正確性證明1、需要證明以下兩點：663、證明2： 現(xiàn)在來證明所建立的生成樹T具有最小耗費。由于G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令U為這樣的一棵最小生成樹，T與U都剛好有n-1條邊。如果T=U,則T就具有最小耗費，那么不必再證明下去。因此假設T≠U，令k(k>0)為在T中而不在U中的邊的個數(shù)，當然k也是在U中而不在T中的邊的數(shù)目。 通過把U變換為T來證明U與T具有相同的耗費，這種轉(zhuǎn)化可在k步內(nèi)完成。每一步使在T而不在U中的邊的數(shù)目剛好減1。而且U的耗費不會因為轉(zhuǎn)化而改變。經(jīng)過k步的轉(zhuǎn)化得到的U將與原來的U具有相同的耗費，且轉(zhuǎn)化后U中的邊就是T中的邊。由此可知，T具有最小耗費。3、證明2：67算法分析:當圖的邊數(shù)為e時，將其組成優(yōu)先隊列需要時間O(e)。

while循環(huán)中,DeleteMin需要O(loge)時間因此關(guān)于優(yōu)先隊列所作運算需時間O(eloge)。實現(xiàn)UnionFind所需的時間為O(eloge)。所以Kruska的時間是O(eloge),適合求邊數(shù)較少的最小生成樹。反之，用Prim算法算法分析:當圖的邊數(shù)為e時，將其組成優(yōu)先隊列需要時間O(e)68

[最小代價通訊網(wǎng)絡]在N城市之間架設通訊線路,要求造價最低.城市之間所有可能的通訊連接視作一個無向圖G,G中每邊的權(quán)值表示建成這段線路的代價.問題轉(zhuǎn)化為求一棵最小生成樹.問題描述:輸入:任一連通圖G(該圖的邊集合)

可行解:圖G的生成樹優(yōu)化函數(shù):生成樹的各邊權(quán)值之和最優(yōu)解:使優(yōu)化函數(shù)達到最小值的生成樹.最優(yōu)化問題(optimizationproblem):問題可描述為有n個輸入(x1,x2,...xn),一組約束條件和一個優(yōu)化(目標)函數(shù)。滿足約束條件的輸入稱為可行解,它是輸入的一個子集.使優(yōu)化函數(shù)取得極值的可行解稱為最優(yōu)解.算法設計與分析>

貪心算法例1[最小代價通訊網(wǎng)絡]在N城市之間架設通訊線路,要求造價69*旅行商問題(貨郎擔問題)問題:

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

=cj,i,且ci,i=

.一推銷員要從某城市出發(fā)經(jīng)過每城市一次且僅一次后返回出發(fā)地問如何選擇路線使代價最小。5143173422算法設計與分析>

貪心算法抽象描述:將城市以及之間的道路抽象為一個無向圖G,G中每邊的權(quán)值表示這段線路的代價.問題轉(zhuǎn)化為求一條最佳周游路線:從一點出發(fā),經(jīng)過每點一次且僅一次并返回原點,且該路線的總代價最小.v1v5v2v4v3C=*旅行商問題(貨郎擔問題)5143173422算法設計與分析70輸入:城市的數(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到其余城市代價中值最小的邊/