第4章-貪心算法

第4章貪心算法2024/3/21算法設計與分析2第4章貪心算法學習要點理解貪心算法的概念。掌握貪心算法的基本要素：最優(yōu)子結構性質、貪心選擇性質。理解貪心算法與動態(tài)規(guī)劃算法的差異。通過應用范例學習動態(tài)規(guī)劃算法設計策略：活動安排問題；背包問題；哈夫曼編碼問題；單源最短路勁問題；最小生成樹問題。2024/3/21算法設計與分析3六角三分貪心算法應用舉例——找硬幣假設有四種硬幣，它們的面值分別為五角、一角、五分和一分。現找顧客六角三分錢，請給出硬幣個數最少的找錢方案。二角五分一角五分一分硬幣個數最少的找錢方案2024/3/21算法設計與分析4分析找硬幣問題本身具有最優(yōu)子結構性質，它可以用動態(tài)規(guī)劃算法來解。但顯然貪心算法更簡單，更直接且解題效率更高。該算法利用了問題本身的一些特性，例如硬幣面值的特性。再例：如果有一分、五分和一角三種不同的硬幣，要找給顧客一角五分錢。2024/3/21算法設計與分析5結論顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。2024/3/21算法設計與分析6貪心法的基本思路從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快地求得更好的解。當達到某算法中的某一步不能再繼續(xù)前進時，算法停止。實現該算法的過程：從問題的某一初始解出發(fā)；

while能朝給定總目標前進一步do

求出可行解的一個解元素；由所有解元素組合成問題的一個可行解。該算法存在的問題：1.不能保證求得的最后解是最佳的；2.不能用來求最大或最小解問題；3.只能求滿足某些約束條件的可行解的范圍。2024/3/21算法設計與分析74.1活動安排問題活動安排問題：要求高效地安排一系列爭用某一公共資源的活動。舉例：活動序號1234567891011起始時間130535688212結束時間45678910111213142024/3/21算法設計與分析8問題定義設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。（臨界資源）每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si<fi

。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。即，當si≥fj或sj≥fi時，活動i與活動j相容，問題就是選擇一個由互相兼容的活動組成的最大集合。2024/3/21算法設計與分析9活動安排問題的貪心算法template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){//各活動的起始時間和結束時間存儲在數組s和f中

//且按結束時間的非遞減排序：f1≤f2≤…≤fn排列。

A[1]=true;//用集合A存儲所選擇的活動

intj=1;for(inti=2;i<=n;i++){

//將與j相容的具有最早完成時間的相容活動加入集合Aif(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}2024/3/21算法設計與分析10算法分析設集合a包含已被選擇的活動，初始時為空。所有待選擇的活動按結束時間的非遞減順序排列：變量j指出最近加入a的活動序號。由于按結束時間非遞減順序來考慮各項活動的，所以fj總是a中所有活動的最大結束時間2024/3/21算法設計與分析11A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}首先將活動1加入集合a；初始化j為1；然后從活動2出發(fā)逐一檢查：☆若待選活動i與a中的所有活動兼容，即活動i的si不早于最近加入a中的j活動的fj，則活動i加入a集合，并取代活動j的位置?！罘駝t不選擇該活動。由于輸入活動是以完成時間的非遞減排列，所選擇的下一個活動總是可被合法調度的活動中具有最早結束時間的那個，所以算法是一個“貪心的”選擇，即使得使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。2024/3/21算法設計與分析12結論算法GreedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間就可安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。2024/3/21算法設計與分析13舉例設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011si130535688212fi45678910111213142024/3/21算法設計與分析14時間012345678910111213142131145146147148149148101481114814811圖4-1算法GreedySelector的計算過程2024/3/21算法設計與分析15補充說明貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法GreedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合a的規(guī)模最大。這個結論可以用數學歸納法證明。2024/3/21算法設計與分析16用數學歸納法證明活動安排問題設集合E={1，2，…，n}為所給的活動集合。由于E中活動按結束時間的非減序排列，故活動1有最早完成時間。證明I：活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1。證明II：對集合E中所有與活動1相容的活動進行活動安排求得最優(yōu)解的子問題。2024/3/21算法設計與分析17證明I：活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1。若k=1，則A就是一個以貪心選擇開始的最優(yōu)解。若k>1，則設由于f1≤fk，且A中的活動是相容的，故B中的活動也是相容的。結論：由于B中活動個數與A中活動個數相同，且A是最優(yōu)的，故B也是最優(yōu)的?？偞嬖谝载澬倪x擇開始的最優(yōu)活動方案。貪心選擇性質2024/3/21算法設計與分析18即需證明：若A是原問題的最優(yōu)解，則A’=A-{1}是活動安排問題E’={i∈E:si≥f1}的最優(yōu)解。如果能找到E’的一個最優(yōu)解B’，它包含比A’更多的活動，則將活動1加入到B’中將產生E的一個解B，它包含比A更多的活動。這與A的最優(yōu)性矛盾。結論：每一步所做的貪心選擇問題都將問題簡化為一個更小的與原問題具有相同形式的子問題。證明II：對E中所有與活動1相容的活動進行活動安排求得最優(yōu)解的子問題。最優(yōu)子結構性質2024/3/21算法設計與分析194.2貪心算法的基本要素對于一個具體的問題，如何知道是否可用貪心算法解決此問題，以及能否得到問題的最優(yōu)解？這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有兩個重要的性質：貪心選擇性質和最優(yōu)子結構性質。2024/3/21算法設計與分析201.貪心選擇性質貪心選擇性質：所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，每步所作的選擇依賴于相關子問題的解。貪心算法僅在當前狀態(tài)下作出局部最優(yōu)選擇，再去解作出這個選擇后產生的相應的子問題。2024/3/21算法設計與分析21分析對于一個具體問題，要確定它是否具有貪心選擇的性質，我們必須證明每一步所作的貪心選擇最終能夠導致問題的最優(yōu)解。通?？梢允紫茸C明問題的一個整體最優(yōu)解是從貪心選擇開始的，而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數學歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關鍵在于利用該問題的最優(yōu)子結構性質。2024/3/21算法設計與分析222.最優(yōu)子結構性質當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。2024/3/21算法設計與分析233.貪心算法與動態(tài)規(guī)劃算法的差異貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是兩類算法的一個共同點。但是，對于具有最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解？是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解？2024/3/21算法設計與分析24回顧：0-1背包問題（動態(tài)規(guī)劃）給定n種物品和一個背包。物品i的重量是wi，其價值為vi，背包的容量為c。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？在選擇裝入背包中的物品時，對每種物品i只有兩種選擇：即裝入或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。2024/3/21算法設計與分析25問題的形式化描述此問題的形式化描述為，給定c>0,wi>0,vi>0,1≤i≤n，要求找出一個n元0-1向量(x1,x2,

..

,xn)，其中xi∈{0,1}，使得對wixi求和小于等于c

，并且對vixi求和達到最大。因此，0-1背包問題是一個特殊的整數規(guī)劃問題。2024/3/21算法設計與分析260-1背包問題的子問題遞歸關系設所給0-1背包問題的子問題：m(i,j)是背包容量為j，可選擇物品為i,i+1,…,n時0-1背包問題的最優(yōu)值。由于0-1背包問題的最優(yōu)子結構性質，可以建立計算m(i,j)的遞歸式如下：

2024/3/21算法設計與分析27背包問題與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包。此問題的形式化描述為，給定c>0,wi>0,vi>0,1≤i≤n，要求找出一個n元0-1向量(x1,x2,

..

,xn)，其中0≤xi≤1,1≤i≤n

，使得對wixi求和小于等于c

，并且對vixi求和達到最大。2024/3/21算法設計與分析28貪心算法解背包問題的基本步驟首先計算每種物品單位重量的價值vi/wi；然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過c，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。2024/3/21算法設計與分析29舉例有3種物品，背包的容量為50千克。物品1重10千克，價值60元；物品2重20千克，價值100元；物品3重30千克，價值120元。用貪心算法求背包問題。2024/3/21算法設計與分析30背包貪心策略：物品1，6元/千克；物品2，5元/千克；物品3，4元/千克。有3種物品，背包的容量為50千克。物品1重10千克，價值60元；物品2重20千克，價值100元；物品3重30千克，價值120元。物品1，10kg物品2，20kg物品3，20kg80+100+60=￥2402024/3/21算法設計與分析31具體算法voidKnapsack(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];}該算法前提：所有物品在集合中按其單位重量的價值從小到大排列。2024/3/21算法設計與分析32算法Knapspack的主要計算時間在于將各種物品按其單位重量的價值從小到大排序，算法的時間復雜度O(nlogn)。對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。1951年，哈夫曼和他在MIT信息論的同學需要選擇是完成學期報告還是期末考試。導師RobertM.Fano給他們的學期報告的題目是，尋找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發(fā)現了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的。2024/3/21算法設計與分析332024/3/21算法設計與分析344.4哈夫曼編碼哈夫曼編碼是廣泛地用于數據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法是用字符在文件中出現的頻率表來建立一個用0,1串表示各字符的最優(yōu)表示方式。編碼目標：給出現頻率高的字符較短的編碼，出現頻率較低的字符以較長的編碼，可以大大縮短總碼長。2024/3/21算法設計與分析35舉例一個數據文件包含100000個字符，要用壓縮的方式來存儲它。該文件中各字符出現的頻率如表所示。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100使用變長碼要比使用定長碼好得多。通過給出現頻率高的字符較短的編碼，出現頻率較低的字符以較長的編碼，可以大大縮短總碼長。2024/3/21算法設計與分析361.前綴碼定義：對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質可以使譯碼方法非常簡單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉換為原字符，即可逐個譯出文件中的所有字符。2024/3/21算法設計與分析37舉例給定序列：001011101。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100可唯一地分解為0,0,101,1101，因而其譯碼為aabe。2024/3/21算法設計與分析38問題分析譯碼過程需要方便地取出編碼的前綴，因此需要一個表示前綴碼的合適的數據結構。用二叉樹作為前綴編碼的數據結構。在表示前綴碼的二叉樹中，樹葉代表給定的字符，并將每個字符的前綴碼看作是從樹根到代表該字符的樹葉的一條道路。代碼中每一位的0或1分別作為指示某結點到其左兒子或右兒子的“路標”。2024/3/21算法設計與分析39前綴碼的二叉樹表示

定長碼變長碼1008614582814a:45b:13c:12d:16e:9f:5000000111110025551430a:45b:13c:12d:16e:9f:51101010100該編碼方案的平均碼長定義為：12024/3/21算法設計與分析402.構造哈夫曼編碼哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用以在作貪心選擇時有效地確定算法當前要合并的兩棵具有最小頻率的樹。一旦兩棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的兩棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q中，再進行新的合并。2024/3/21算法設計與分析41舉例10025551430a:45b:13c:12d:16e:9f:51101010100abcdef頻率(千次)45131216952024/3/21算法設計與分析42哈夫曼算法的執(zhí)行過程示例：a:45b:13c:12d:16e:9f:514a:45b:13c:12d:16e:9f:514a:45b:13c:12d:16e:9f:5252024/3/21算法設計與分析4314a:45b:13c:12d:16e:9f:5253014a:45b:13c:12d:16e:9f:525305510025551430a:45b:13c:12d:16e:9f:5

由于字符集中有6個字符，優(yōu)先隊列的大小初始為6，總共用5次合并得到最終的編碼樹T。每次合并使Q的大小減1，最終得到的樹就是最優(yōu)前綴編碼：哈夫曼編碼樹，每個字符的編碼由樹T的根到該字符的路徑上各邊的標號所組成。2024/3/21算法設計與分析44算法首先用字符集C中每一個字符c的頻率f(c)初始化優(yōu)先隊列Q。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。然后不斷地從優(yōu)先隊列Q中取出具有最小頻率的兩棵樹x和y，將它們合并為一棵新樹z。z的頻率是x和y的頻率之和。新樹z以x為其左兒子，y為其右兒子（也可以y為其左兒子，x為其右兒子。不同的次序將產生不同的編碼方案，但平均碼長是相同的）。經過n-1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。2024/3/21算法設計與分析453.哈夫曼編碼的正確性要證明哈夫曼算法的正確性，就要證明最優(yōu)前綴碼問題具有貪心選擇性質和最優(yōu)子結構性質。(1)貪心選擇性質證明：根據構造過程證明，交換任意一個節(jié)點與葉子節(jié)點不增加平均碼長，說明最優(yōu)。引理：設C為一字母表，其中每個字符c具有頻度f[c]。設x和y為C中具有最低頻度的兩個字符，則存在C的一種最優(yōu)前綴編碼，其中x和y的編碼長度相同但最后一位不同。2024/3/21算法設計與分析46證明：貪心選擇性質設b和c是二叉樹T的最深葉子且為兄弟。不失一般性，可設：由于x和y是C中具有最小頻率的兩個字符，故：xybcT設，二叉樹T表示C的任意一個最優(yōu)前綴碼。需證明，可以對T做適當修改后得到一棵新的二叉樹T’’，使在新樹中，x和y是最深葉子且為兄弟。同時新樹T’’表示的前綴碼也是C的最優(yōu)前綴碼。2024/3/21算法設計與分析47首先在樹T中交換葉子b和x的位置得到樹T’：xybcTbyxcT’bcxyT’’然后在樹T’中交換葉子c和y的位置得到樹T’’。2024/3/21算法設計與分析48由此可知，樹T和T’表示的前綴碼的平均碼長之差為：xybcbyxcTT’樹T’的平均碼長不會長于樹T。2024/3/21算法設計與分析49類似地，可以證明在T’中交換y與c的位置也不增加平均碼長，即：byxcT’bcxyT’’由此可知：2024/3/21算法設計與分析50由于T所表示的前綴碼是最優(yōu)的，故因此：結論：T’’表示的前綴碼也是最優(yōu)前綴碼，且x和y具有最長的碼長，同時僅僅最后一位編碼不同。xybcTbcxyT’’2024/3/21算法設計與分析51引理：設T為表示字母表C上一種最優(yōu)前綴代碼的二叉樹。對C中每個字符定義有頻度f[c]?？紤]T中任意兩個為兄弟葉節(jié)點的字符x和y，并設z為它們的父節(jié)點。那么，若認為z是一個頻度為f[z]=f[x]+f[y]的字符的話，樹T’=T-{x,y}就表示了字母表C’=C-{x,y}∪{z}上的一種最優(yōu)前綴編碼。(2)最優(yōu)子結構性質設去掉x,y后計算各部分代價為B(T’)：

f[x]dT(x)+f[y]dT(y)=(f[x]+f[y])(dT’(z)+1)=f[z]dT’(z)+(f[x]+f[y])

所以根據此式：B(T)=B(T’)+f[x]+f[y]

如果T’代表C’上一種非最優(yōu)前綴代碼，則存在葉節(jié)點z為C’中的字符的樹T’’，將x和y插入T’’中使它們成為z的子結點，可以得到C的一種前綴代碼，使得B(T'')+f[x]+f[y]<B(T)，和T的最優(yōu)性矛盾。2024/3/21算法設計與分析524.5單源最短路徑給定帶權有向圖G=(V,E)，其中每條邊的權是非負實數。給定V中的一個頂點，稱為源?，F在要計算從源到其他所有各頂點的最短路徑長度。這里的路徑長度是指路徑上各邊權之和，這個問題通常稱為單源最短路徑問題。例如：右圖中的有向圖，計算從源頂點1到其他頂點的最短路徑。2024/3/21算法設計與分析53算法基本思想Dijkstra算法是求解單源最短路徑問題的一個貪心算法?；舅枷耄涸O置一個頂點集合S，并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。Dijkstra算法通過分步方法求出最短路徑。每一步產生一個到達新的目的頂點的最短路徑。下一步所能達到的目的頂點通過這樣的貪心準則選?。涸谶€未產生最短路徑的頂點中，選擇路徑長度最短的目的頂點。也就是說，Dijkstra算法按路徑長度順序產生最短路徑。2024/3/21算法設計與分析54實際上，下一條最短路徑總是由已產生的最短路徑再擴充一條最短的邊得到的，且這條路徑所到達的頂點其最短路徑還未產生。例如：右圖。2024/3/21算法設計與分析55Dijkstra算法的執(zhí)行設置一個頂點集合S。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只有經過S中頂點的路稱為從源到u的特殊路徑，并且用數組dist來記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路徑長度的頂點u，將u添加到S中，同時對數組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。2024/3/21算法設計與分析56舉例已知：帶權有向圖V={v1,v2,v3,v4,v5}E={<v1,v2>,<v1,v4>,<v1,v5>,<v2,v3>,<v3,v5>,<v4,v3>,<v4,v5>}設為v1源點，求其到其余頂點的最短路徑。2024/3/21算法設計與分析57初始時，集合S只有源點v1，即加入集合S中的頂點u為v1。從源點v1到其它頂點的最短特殊路徑（中間只有來自于集合S中的頂點）長度分別為：dist[2]=10;dist[3]=maxint;dist[4]=30;dist[5]=100.其中，沒有特殊路徑的頂點v3用maxint表示其最短特殊路徑長度。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301002024/3/21算法設計與分析58集合S為{v1}，其余頂點的最短特殊路徑長度已確定。由于dist[2]的值最小，為10，所以將頂點v2加入集合S中。由于集合S為{v1,v2}，需要修改剩余的三個頂點的最短特殊路徑值。例如，v3的最短特殊路徑為<v1,v2>,<v2,v3>；長度為60。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002024/3/21算法設計與分析59迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}410503090集合S為{v1,v2}，其余頂點的最短特殊路徑長度已確定。其中dist[4]的值最小，為30，所以將頂點v4加入集合S中。由于集合S為{v1,v2,v4}，需要修改剩余的兩個頂點的最短特殊路徑值。例如，v3的最短特殊路徑為<v1,v4>,<v4,v3>；長度為50。2024/3/21算法設計與分析60迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}310503060集合S為{v1,v2,v4}，其余頂點的最短特殊路徑長度已確定。其中dist[3]的值最小，為50，所以將頂點v3加入集合S中。由于集合S為{v1,v2,v4,v3}，需要修改剩余的一個頂點的最短特殊路徑值。例如，v5的最短特殊路徑為<v1,v2>,<v2,v3>,<v3,v5>；長度為60。2024/3/21算法設計與分析61迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060集合S為{v1,v2,v4,v3}，其余頂點的最短特殊路徑長度已確定。由于只剩余一個頂點v5不在集合中，所以應該把它加入集合。此時集合S為{v1,v2,v4,v3,v5}=V，完成。dist值為源點到對應頂點的最短路徑長度。2024/3/21算法設計與分析62第2條路徑是第1條路徑擴充一條邊形成的；第3條路徑則是第2條路徑擴充一條邊；第4條路徑是第1條路徑擴充一條邊；第5條路徑是第3條路徑擴充一條邊。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060按長度順序產生最短路徑時，下一條最短路徑總是由一條已產生的最短路徑加上一條邊形成。2024/3/21算法設計與分析63用Dist[v]記錄任一頂點v到源點的最短路徑，建立一S集合且為空（開始只有源點），用以記錄已找出最短路徑的點。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}5105030602024/3/21算法設計與分析64掃描非S集中Dist[]值最小的節(jié)點Dist[u]，也就是找出下一條最短路徑，把節(jié)點u加入S集中。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}5105030602024/3/21算法設計與分析65更新所有非S集中的Dist[]值，看看是否可通過新加入的u點讓其路徑更短：迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060if(Dist[u]+(u,v)<Dist[v])thenDist[v]=Dist[u]+(u,v);2024/3/21算法設計與分析664.跳轉到2操作，循環(huán)（頂點數-1）次，依次找出所有頂點的最短路徑。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}5105030602024/3/21算法設計與分析67算法的正確性1.貪心選擇性質Dijkstra算法所作的貪心選擇是從V-S中選擇具有最短特殊路徑的頂點u，從而確定從源到u的最短路徑長度dist[u]。為什么從源到u沒有更短的其他路徑呢？

如果存在一條從源到u且長度比dist[u]更短的路，設這條路初次走出S之外到達的頂點為x∈V-S，然后徘徊于S內外若干次，最后離開S到達u。在這條路徑上，分別記d(v,x)，d(x,u)和d(v,u)為頂點v到頂點x，頂點x到頂點u和頂點v到頂點u的路徑長，那么，有dist[x]≤d(v,x)d(v,x)+d(x,u)=d(v,u)<dist[u]利用邊權的非負性，可知d(x,u)≥0從而推得dist[x]≤dist[u]，產生矛盾。證明dist[u]是源到頂點u的最短路徑長度。2024/3/21算法設計與分析682.最優(yōu)子結構性質證明最優(yōu)子結構性質，即算法中確定的dist[u]確實是當前從源到頂點u的最短特殊路徑長度。

為此，只要考察算法在添加u到S中后，dist[u]的值所起的變化就行了。不論算法中dist[u]的值是否有變化，它總是關于當前頂點集S到頂點u的最短特殊路徑長度。2024/3/21算法設計與分析694.6最小生成樹設G=(V,E)是無向帶權連通圖，即一個網絡。E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。2024/3/21算法設計與分析70應用網絡的最小生成樹在實際中有廣泛應用。例如，在設計通信網絡時，用圖的頂點表示城市，用邊(v,w)的權c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網絡的最經濟的方案。2024/3/21算法設計與分析71貪心法求解準則將貪心策略用于求解無向連通圖的最小代價生成樹時，核心問題是需要確定貪心準則。根據最優(yōu)量度標準，算法的每一步從圖中選擇一條符合準則的邊，共選擇n-1條邊，構成無向連通圖的一棵生成樹。貪心法求解的關鍵：該量度標準必須足夠好。它應當保證依據此準則選出n-1條邊構成原圖的一棵生成樹，必定是最小代價生成樹。2024/3/21算法設計與分析72算法步驟分析設G=(V,E)是帶權的連通圖，T=(V,S)是圖G的最小代價生成樹。ESetTypeSpanningTree(ESetTypeE,intn){//G=(V,E)為無向圖，E是圖G的邊集，n是圖中結點數

ESetTypeTE=?;//TE為生成樹上邊的集合

intu,v,k=0;ETypee；//e=(u,v)為一條邊

while(k<n-1&&E中尚有未檢查的邊){//選擇生成樹的n-1條邊

e=select(E);

//按最優(yōu)量度標準選擇一條邊

if(TE∪e不包含回路)//判定可行性

{TE=TE∪e;k++;}//在生成樹邊集TE中添加一條邊

}returnS;}……UV-U2024/3/21算法設計與分析73普里姆（Prim）算法

克魯斯卡爾（Kruskal）算法Kruskal算法的貪心準則：按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v)。這種做法使得算法在構造生成樹的過程中，當前子圖不一定是連通的。Prim算法的貪心準則：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價的邊e=(u,v)。2024/3/21算法設計與分析74Prim算法的基本步驟在圖G=(V,E)（V表示頂點集合，E表示邊集合）中，從集合V中任取一個頂點（例如取頂點v1）放入集合U中，這時U={v1}，生成樹邊集合T(E)為空。尋找與S中頂點相鄰（另一頂點在V-U中）權值最小的邊的另一頂點v2，并使v2加入S。即U={v1,v2}，同時將該邊加入集合T(E)中。重復2，直到U=V為止。這時T(E)中有n-1條邊，T=(U,T(E))就是一棵最小生成樹。2024/3/21算法設計與分析75prim算法V1V6V5V4V3V26513566425算法思想：

設N=(V,E)是連通網，TE

是

N

上

最小生成樹中邊的集合。

初始令

U={u0},(u0

V),TE={}。

在所有

u

U,v

V-U的邊

(u,v)

E

中，

找一條代價最小的邊

(u0,v0)。

將

(u0,v0)并入集合

TE，同時

v0

并入

U。

重復上述操作直至

U=V

為止，則

T=(V,TE)為

N

的最小生

成樹。

V1V3V6V4V2V52024/3/21算法設計與分析76Prim算法舉例2024/3/21算法設計與分析77Kruskal算法V1V6V5V4V3V26513566425算法思想：

設連通網N=(V,E)，令最小生成樹初始狀態(tài)為只有

n

個頂點而無邊的非連通圖

T=(V,{})，每個頂點自成一個連通分量。

在E中選取代價最小的邊，若該邊依附

的頂點落在

T

中不同的連通分量上（即：

不能形成環(huán)），則將此邊加入到

T

中；否

則，舍去此邊，選取下一條代價最小的邊。

依此類推，直至

T

中所有頂點都在同一

連通分量上為止。

V1V6V5V4V3V212345NT2024/3/21算法設計與分析78Kruskal算法舉