第6章-貪心法教材

第5章貪心法3/21/2024

學(xué)習(xí)要點：理解貪心算法的概念掌握貪心算法的基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì) （2）貪心選擇性質(zhì)理解貪心算法的一般方法通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計策略。 （1）背包問題;

（2）最優(yōu)歸并模式;

（3）最小代價生成樹;2章節(jié)內(nèi)容

6.1一般方法

6.2背包問題

6.4最優(yōu)歸并模式

6.5最小代價生成樹6.1貪心法的一般方法貪心法的基本思想求解最優(yōu)化問題的算法包含一系列步驟每一步都有一組選擇作出在當(dāng)關(guān)看來最好的選擇希望通過作出局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇貪心算法不一定總產(chǎn)生優(yōu)化解貪心法是否產(chǎn)生優(yōu)化解，需要嚴(yán)格證明貪心算法產(chǎn)生優(yōu)化解的條件貪心選擇性：若一個優(yōu)化問題的全局優(yōu)化解可以通過局部優(yōu)化選擇得到，則該問題稱為具有貪心選擇性。優(yōu)化子結(jié)構(gòu)：若一個優(yōu)化問題的優(yōu)化解包含它的優(yōu)化解，則稱其具有優(yōu)化子結(jié)構(gòu)。貪心算法正確性證明方法證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu)證明算法所求解的問題具有貪心選擇性證明算法確實按照貪心選擇性進行局部優(yōu)化選擇可行解

——問題給定某些約束條件，滿足約束條件的問題解，即稱為可行解。最優(yōu)解

——問題給出目標(biāo)函數(shù)衡量可行解的好壞，使目標(biāo)函數(shù)取最大（或最?。┲档目尚薪夥Q為最優(yōu)解。 貪心法求解最優(yōu)化問題。貪心法通過分步?jīng)Q策的方法求解問題，每一步?jīng)Q策產(chǎn)生的一個分量。貪心法每一步上用作決策依據(jù)的選n-元組解（x0,x1,…,xn-1）擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)。在選擇解分量的過程中，添加新的解分量xk后，形成的部分解（x0,x1,…,xk)不違反可行解約束條件。每一次貪心選擇都將所求問題簡化為規(guī)模更小的子問題。貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇，僅依賴以前的選擇，但不依賴于以后的選擇。對于一個貪心算法，必須證明該算法的每一步上作出的選擇，都必然最終導(dǎo)致問題的一個整體最優(yōu)解。

貪心算法不能保證對所有問題都得到整體最優(yōu)解。

對許多問題，如：一般背包問題、最佳合并模式問題、單源最短路徑問題，最小生成樹問題等，貪心算法確實能產(chǎn)生整體最優(yōu)解。

一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。 能用貪心算法求解的問題一般具有兩個性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。1、貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。 這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。2、最優(yōu)子結(jié)構(gòu)性質(zhì)

一個問題的最優(yōu)解包含其子問題的最優(yōu)解，則稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。程序6-1貪心法算法框架SolutionTypeGreedy(STypea[],intn){ SolutionTypesolution=?；//初始時，解向量不包含任何分量

for(inti=0;i<n;i++){ STypex=Select(a); //問題的解用n元組(x0,x1,...,xn-1)表示

//遵循最優(yōu)度量標(biāo)準(zhǔn)選擇一個分量x if(Feasiable(solution,x))//判斷加入新分量x后部分解是否可行

solution=Union(solution,x);//形成新的部分解

} returnsolution; //返回生成的最優(yōu)解}

給定n種物品和一個容量為M的背包。物品i的重量是wi，其價值為pi。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?物品不能分割：在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品——0/1背包問題物品是可分割的。選擇物品i裝入背包時，可以選擇物品i的一部分xi（0≤xi≤1）裝入，而不一定要全部裝入背包——

一般背包問題，簡稱背包問題.6.2背包問題

這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似。但一般背包問題可以用貪心算法求解；而0-1背包問題卻不能用貪心算法求解，而只能得到它的近似解。

事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品時所導(dǎo)致的最終方案，然后再作出最好選擇。由此導(dǎo)出許多互相重疊的子問題，這正是該問題可用動態(tài)規(guī)劃算法求解的重要特征。實際上，動態(tài)規(guī)劃算法的確可以有效求解0-1背包問題。

一般背包問題用貪心選擇可保證背包剛好能裝滿。而對于0-1背包問題，貪心選擇無法保證最終能將背包裝滿。部分閑置的背包空間使每公斤背包空間的價值降低了，因此不能得到最優(yōu)解。貪心法求解背包問題

背包問題的解可表示成一個n-元組:X=(x0,x1,...xn-1),0≤xi≤1,0≤i<n.xi為第i件物品裝入背包中的那部分?？尚薪獾募s束條件:最優(yōu)解的目標(biāo)函數(shù): (見P104

例6-1表6-1)用貪心法求解,找出最優(yōu)量度標(biāo)準(zhǔn)是至關(guān)重要的.選擇最優(yōu)量度標(biāo)準(zhǔn)標(biāo)準(zhǔn)1選取目標(biāo)函數(shù)(總價值)作為量度標(biāo)準(zhǔn),每次取價值最大的物品裝包,不考慮重量.得到近似解,而不是最優(yōu)解.原因:只考慮當(dāng)前最大收益,背包載重消耗太快.標(biāo)準(zhǔn)2選取重量作為量度標(biāo)準(zhǔn),每次取重量最小的物體裝包,不考慮收益.得到近似解,而不是最優(yōu)解.標(biāo)準(zhǔn)3選取單位重量價值最大的物品裝包,即每次選pi/wi最大的物品裝包.標(biāo)準(zhǔn)最合理,得到最優(yōu)解.(正確性有待證明)

基本步驟: 1、首先計算每種物品單位重量的價值Pi/Wi并按非增次序進行排序；

2、然后依貪心選擇策略，選擇單位重量價值最高的物品裝入背包。依此策略一直地進行下去，將盡可能多的物品全部裝入背包，直到將背包裝滿。

3、若裝入某件物品時，不能全部裝下，而背包內(nèi)的物品總重量仍未達(dá)到W，則根據(jù)背包的剩余載重，選擇單位重量價值次高的物品并盡可能多地裝入背包。

具體算法可描述如下頁：

背包問題的貪心算法程序6-2背包問題的貪心算法（最優(yōu)度量標(biāo)準(zhǔn)：單位重量價值pi/wi最大）voidGreedyKnapsack(float*x) {//前置條件：w[i]已按p[i]/w[i]的非增次序排序

floatu=m; //將背包剩余載重量u初始化為mfor(inti=0;i<n;i++)x[i]=0; //對解向量x初始化

for(i=0;i<n;i++) { //按最優(yōu)量度標(biāo)準(zhǔn)選擇解分量xi if(w[i]>u)break; //若當(dāng)前物品i已無法全部裝下，則跳出

x[i]=1.0; //否則，整個裝入當(dāng)前物品i u=u-w[i]; } //同時背包剩余載重減w[i]if(i<n)x[i]=u/w[i]; //背包剩余空間只夠放下當(dāng)前物品i的x[i]部分}數(shù)組w存放物品的重量，數(shù)組p存放物品的價值，數(shù)組x存放背包問題的最優(yōu)解。m為背包載重量，u為背包剩余載重量。如果不計按p[i]/w[i]的非增次序排列w[i]的時間，程序6-2的時間復(fù)雜度為O(n)。算法Greedyknapsack的主要計算時間在于將各種物品按單位重量價值p[i]/w[i]從大到小排序，為O(nlogn)。因此，算法的計算時間上界為O(nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。最優(yōu)解證明定理6-1：如果p0/w0≥p1/w1≥...≥pn-1/wn-1,則程序6-2求得的背包問題的解是最優(yōu)解。證明：設(shè)X=(x0,x1,...,xn-1),0≤xi≤1,0≤i<n是貪心背包算法的解。則由貪心背包算法可知，解的形式一定為 X=(1,...,1,xj,0,...,0),0≤xj<1

如果X不是最優(yōu)解，另有可行解Y=(y0,y1,...,yk,...,yn-1)是最優(yōu)解，則應(yīng)有：

設(shè)k是使得yk≠xk的最小下標(biāo)，必有yk<xk(見P106)。

假定以xk替換Y中的yk，得到新的解Z=(z0,...,zk-1,zk,zk+1,...,zn-1)?？芍禾鎿Q前后X、Y、Z的前k個分量相等zi=yi=xi=1，0≤i≤k-1，但替換后zk=xk。為保證Z是可行解，應(yīng)有： 。因此假設(shè)不成立，證得貪心背包算法的解X即為最優(yōu)解?。ㄖ貜?fù)這樣的替換過程，最終可得到一個與X完全相等的解。）課堂練習(xí)題：找換硬幣考慮用最少的硬幣數(shù)來找n分錢的問題，假設(shè)每個硬幣的值都是整數(shù)。1）請給出一個貪心算法，使得所換硬幣包括1角的，5分的，2角5分的和1分的？2）假設(shè)可換的硬幣的單位是c的冪，也就是c0,c1,...,ck,其中整數(shù)c>1,k≥1。證明貪心算法總可以產(chǎn)生一個最優(yōu)解。3）對任意給定的硬幣單位集合，用貪心法來求解，是否總能保證得到最優(yōu)解（即：硬幣數(shù)最少的最優(yōu)硬幣組合方案）

？所給集合應(yīng)當(dāng)包括1分，以保證對任意n值均有解。2）假設(shè)可換的硬幣的單位是c的冪，也就是c0,c1,...,ck,其中整數(shù)c>1,k≥1。證明貪心算法總可以產(chǎn)生一個最優(yōu)解。證明：（反證）令（nk,nk-1,...,n1,n0）是貪心算法的解，其中的解分量依次對應(yīng)值為ck,ck-1,...,c1,c0的硬幣個數(shù)。假設(shè)該貪心算法的解（nk,nk-1,...,n1,n0）不是最優(yōu)解，另有（bk,bk-1,...,b1,b0)為最優(yōu)解。則必有：證明（續(xù)）：從左至右依次比較貪心法的解(nk,nk-1,...,n1,n0)和最優(yōu)解(bk,bk-1,...,b1,b0)。設(shè)t是使得nt≠bt的最小下標(biāo).由于貪心法中nt是值為ct的硬幣可取的最大個數(shù)，所以必有nt>bt。所以有（1）式可得硬幣的總價值相同：得：與假設(shè)中（2）式矛盾。因此假設(shè)不成立，即：貪心法求得的解必定是最優(yōu)解。證明（續(xù)）：又因為下標(biāo)從k到t+1的解分量是相等的，所以可得：3）對任意給定的硬幣單位集合，用貪心法來求解，是否總能保證得到最優(yōu)解（即：硬幣數(shù)最少的最優(yōu)硬幣組合方案）

？所給集合應(yīng)當(dāng)包括1分，以保證對任意n值均有解。不能。例如：硬幣單位集合為（4,3,1），n=10。貪心法求得的解為（2,0,2），總共需要4枚硬幣。而最優(yōu)解為（1,2,0），總共需要3枚硬幣。6.4最優(yōu)歸并模式例6-4：將5個長度分別為(20,30,30,10,5)的有序文件(F1,F2,F3,F4,F5)兩兩合并成一個有序文件。兩路合并外排序：通過反復(fù)執(zhí)行將兩個有序子序列合并成一個有序文件的操作，將n個長度不等的有序子文件合并成一個有序文件。整個合并過程中需要讀/寫記錄數(shù)最少的合并方案為最佳合并模式。每一種合并模式可以用合并樹描述：例6-4的兩路合并樹：95801550303020105F1F2F3F4F5(a)一種合并模式95356015201053030F1F5F4F2F3(b)最佳合并模式圖(a)對應(yīng)的兩路合并模式，帶權(quán)外路徑長度：(20+30)*3+(30+10+5)*2=240圖(b)對應(yīng)的兩路合并模式，帶權(quán)外路徑長度：(5+10)*3+(20+30+30)*2=205擴充二叉樹：除葉子結(jié)點外，其余結(jié)點都必須有2個孩子。擴充二叉樹的帶權(quán)外路徑長度：WPL=其中：m是葉子結(jié)點的個數(shù)，wk是第k個葉子結(jié)點的權(quán)，lk是從根到該葉子結(jié)點的路徑長度。兩路合并最佳模式問題的貪心算法：（最優(yōu)度量標(biāo)準(zhǔn)——帶權(quán)外路徑長度最?。┰O(shè)（w0,w1,...,wn-1)是n個有序文件的長度，以每個文件的長度作為根結(jié)點的權(quán)值，構(gòu)造n個只有根的二叉樹；選擇兩棵根結(jié)點權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和；重復(fù)此過程，直到合并為一棵二叉樹為止。生成的兩路合并樹正是代表兩路合并最佳模式的二叉合并樹。具體實現(xiàn)見下頁：程序6-6類BTNode<T>為二叉合并樹結(jié)點；優(yōu)先權(quán)隊列pq中的元素為HNode類的對象，包含兩個數(shù)據(jù)成員：指針ptr（指向二叉樹的根）和weight（存放該根的權(quán)值）；Append向優(yōu)先權(quán)隊列中添加新元素;Serve從優(yōu)先權(quán)隊列中取出具有最高優(yōu)先權(quán)（即權(quán)值最?。┑脑?。程序6-6兩路合并最佳模式的貪心算法PrioQueue<HNode<T>>pq(2*n-1); BTNode<T>*p; HNode<T>a,b;for(inti=0;i<n;i++){ //構(gòu)造n棵只有根的二叉樹

p=newBTNode<T>(w[i])； //新建一個二叉樹結(jié)點

a.ptr=p;a.weight=w[i]; //合并樹對象a包含指向根(p)的指針和根(p)的權(quán)值

pq.Append(a); //將合并樹對象a中指向根的指針和根的權(quán)值加入隊列pq}for(i=1;i<n;i++){ //兩兩合并n-1次，將n棵樹合并成一棵樹

pq.Serve(a); pq.Serve(b);//從pq中取出優(yōu)先權(quán)最高(權(quán)值最小)的兩棵樹

a.weight=a.weight+b.weight;

p=newBTNode<T>(a.weight,a.ptr,b.ptr);//合并這兩棵樹，構(gòu)造一棵新二叉樹

a.ptr=p; //對象a中的指針重新指向新二叉樹的根

pq.Append(a); //將合并樹對象a中指向新根的指針和根的權(quán)值加入隊列pq}pq.Serve(a); //取出生成的最佳合并樹returna.ptr; //a.ptr指向最佳合并樹的根算法正確性證明

定理6-4：設(shè)有n個權(quán)值W={w0,w1,...,wn-1}作為外結(jié)點的權(quán)值，構(gòu)造兩路合并樹的貪心算法將生成一棵具有最小帶權(quán)外路徑長度的二叉樹。證明：（歸納法）若：k=n時,由權(quán)值w0≤w1≤…≤wn-1按貪心算法生成的兩路合并樹為Tn

。假設(shè)Tn不是最優(yōu)的，而另一棵兩路合并樹Tn’是最優(yōu)的，即：cost(Tn’)<cost(Tn)。對樹Tn’作調(diào)整： 將離根最遠(yuǎn)的內(nèi)結(jié)點p的兩個孩子wi和wj，與權(quán)值最小的兩個外結(jié)點w0和w1交換，得到另一棵二叉合并樹Tn’’。必有cost(Tn’’)≤cost(Tn’)。對Tn’’和Tn，都用權(quán)值為w0+w1的外結(jié)點取代它們的根p。（見圖6-8）得到有n-1個外結(jié)點的兩路合并樹Tn-1’’和Tn-1。根據(jù)歸納法假設(shè)：cost(Tn-1)≤cost(Tn-1’’)。 又因為： cost(Tn)=cost(Tn-1)+w0+w1

和cost(Tn’’)=cost(Tn-1’’)+w0+w1，

因此

cost(Tn)≤cost(Tn’’)。與假設(shè)矛盾，貪心法生成的兩路合并樹必是最佳兩路合并樹！假設(shè)：外結(jié)點數(shù)目k<n時,算法能生成有k個外結(jié)點的最佳兩路合并樹。證明k=n時貪心算法生成的兩路合并樹為最佳兩路合并樹：課堂練習(xí)題畫出W={9,15,17,19,20,23,25,30}的三路最佳合并樹。由于n=8（權(quán)值的個數(shù)）,

k=3（三路合并），n-1=7不是k-1=2的整數(shù)倍時需補充（k-1)-(n-1)%(k-1)=1個零權(quán)值（虛結(jié)點）。1582472561723301920915256.5最小代價生成樹

設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。 若極小連通子圖G’包括圖G中的所有頂點，并有盡可能少的邊，則稱G’為G的生成樹。 生成樹上各邊的權(quán)值代表相應(yīng)的代價。樹中各條邊的代價總和是生成樹的代價。 圖的生成樹不唯一，采用不同的遍歷方法，從不同的結(jié)點出發(fā)可得到不同的生成樹。在G的所有生成樹中，代價最小的生成樹稱為G的最小生成樹。 網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如：在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。定理6-5：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的一個真子集。如果(u,v)

E是所有u

U，v

V-U的邊中權(quán)值c[u][v]最小者，那么一定存在G的一棵最小代價生成樹T=(V,S),以(u,v)為其中一條邊。這一性質(zhì)也稱為MST性質(zhì)。

一般情況下，用貪心法得到的是近似最優(yōu)解，而不能保證得到最優(yōu)解。但用貪心法計算最小生成樹，卻可以設(shè)計出保證得到最優(yōu)解的構(gòu)造最小生成樹的有效算法。

本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：程序6-7貪心法求帶權(quán)無向圖的最小代價生成樹的粗略算法ESetTypeSpanningTree(ESetTypeE,intn){ //G=(V,E)為無向圖，E是圖G的邊集，n是圖中結(jié)點數(shù)

ESetTypeS=?； //S為生成樹上邊的集合

intu,v,k=0; ETypee;

//e為一條邊

while(k<n-1&&E中尚有未檢查的邊){ e=select(E); //按最優(yōu)度量標(biāo)準(zhǔn)選擇一條邊

if(S∪e不包含回路){ //判斷可行性

S=S∪e; //在生成樹邊集S中添加一條邊

k++; } //k為生成樹邊集S中邊的條數(shù)

} returnS;}最簡單的最優(yōu)度量標(biāo)準(zhǔn)：選擇使得迄今為止已入選S中的邊代價之和增量最小的邊。若所有的邊都考察完畢后，S集合中的邊數(shù)k仍然小于n-1，就表明原圖G不是連通圖。Kruskal在1956年提出的最小代價生成樹算法。這種算法對邊數(shù)較少的帶權(quán)圖有較高效率。它的基本思想是：Kruskal算法將圖G中的邊按其權(quán)值由小到大排序。然后作如下的貪心選擇：在E中選取一條權(quán)值最小的邊e=(u,v)，并將其從E中刪除；若在S中加入邊(u,v)后不形成回路，則將該邊加入生成樹S中(這要求u、v分屬于兩棵不同的子樹）；若在S中加入邊(u,v)后會形成回路，則舍棄該邊，以后也不再考慮。如此依次進行，直到選夠（n-1）條邊即得到最小生成樹。1、首先將G的n個頂點看成n個孤立的連通分支。2、將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當(dāng)查看到第k條邊(u,v)時，如果端點u和v分別是當(dāng)前2個不同的連通分支T1和T2中的頂點時，就用邊(u,v)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點u和v在當(dāng)前的同一個連通分支中，就直接再查看第k+1條邊。3、這個過程一直進行到只剩下一個連通分支時為止，此時便是G的一棵最小代價生成樹。設(shè)G=(V,E)是一個連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的一棵最小生成樹F=(U,S)的Kruskal算法的基本步驟是：(S為正在構(gòu)造的生成樹邊集)例如：對于下圖中的連通帶權(quán)圖各邊按權(quán)值排序為：d13=1d46=2d25=3d36=4d14=

5d34=5d23=5d12=6d35=6d56=6按Kruskal算法選邊的過程如下圖所示：d13=1d46=2d25=3d36=4d14=5d34=5d23=5d12=6d35=6d56=6關(guān)于集合的一些基本運算可用于實現(xiàn)Kruskal算法：

對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind（每一個子集用樹根的標(biāo)號唯一標(biāo)識，參見P112-6.3節(jié)）所支持的基本運算。按權(quán)的遞增順序查看邊，等價于用最小堆實現(xiàn)一個優(yōu)先權(quán)隊列。程序6-9Kruskal算法voidKruskal(PrioQueue<eNode<T>>&pq){ //優(yōu)先權(quán)隊列pq中保存無向圖邊的集合。

while(k<n-1&&!pq.IsEmpty()){ pq.Serve(x); //用Serve函數(shù)從pq中取出最小代價的邊x u=s.Find(x.u); v=s.Find(x.v);

//分別找邊x的兩個結(jié)點x.u和x.v所在的并查集的樹根

if(u!=v){ //若結(jié)點u和v不在同一樹中

s.Union(u,v); //合并u、v所在的兩棵并查集樹

k++; //邊x加入生成樹后邊數(shù)加1 cout<<“(“<<x.u<<“,”<<x.v<<“,”<<x.w<<“)”; } } //輸出生成樹上一條邊x if(k<n-1)throwNonConnected;//若邊數(shù)少于n-1，則原圖非連通}程序6-9按邊加入的順序輸出，可輸出以下邊集：(1,3,1)(4,6,2)(2,5,3)(3,6,4)(2,3,5)d13=1d46=2d25=3d36=4d14=5d34=5d23=5d12=6d35=6d56=6邊的權(quán)值（當(dāng)圖的邊數(shù)為e，結(jié)點數(shù)為n時）算法執(zhí)行前，建立優(yōu)先權(quán)隊列的時間為：O(eloge)；

Kruskal算法：

while循環(huán)最多執(zhí)行e次；循環(huán)體中：Serve運算（取最小代價邊）的時間為：O(loge)；改進的Find運算（找結(jié)點并查集的根）時間為：O(logn)；Union運算（合并兩棵并查集樹）時間為：O(1)。一般有e≥n，所以所需的計算時間復(fù)雜度為：O(eloge)。Kruskal算法時間復(fù)雜度 Prim在1957年提出的最小代價生成樹算法，這種算法特別適用于邊數(shù)相對較多，即比較接近于完全圖的圖。 此算法是按逐個將頂點連通的步驟進行的，它只需采用一個頂點集合。這個集合開始時是空集，以后將已連通的頂點陸續(xù)加入到集合中去，到全部頂點都加入到集合中了，就得到所需的生成樹。Prim算法設(shè)G=(V,E)是一個連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的一棵最小生成樹F=(U,S)的Prim算法的基本步驟是：(U為正在構(gòu)造的生成樹點集)1、首先從圖的任一頂點起進行，將它加入集合U中。如：置U={1}；2、然后作如下的貪心選擇：每次從與集合U相關(guān)聯(lián)的邊中（即一個端點在集合中而另一個端點在集合外的各條邊中），選出權(quán)值c[i][j]最小的一條作為生成樹的一條邊，此時滿足條件i

U，j

V-U，并將集合外的結(jié)點j加入集合中，表示該點也被所選出的邊連通了。3、這個過程一直進行到U=V時為止，這時全部頂點都加入到集合U中。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。例如，對于下圖(a)中的帶權(quán)圖，從頂點1開始按Prim算法選邊的過程如下圖(b)所示。

在Prim算法中，采用鄰接表存儲圖，用輔助數(shù)組mark[]標(biāo)志某個結(jié)點是否已被選入生成樹。要有效地找出滿足條件i

U,j

V-U，且權(quán)c[i][j]最小的邊(i,j)，實現(xiàn)起來較簡單的辦法是：設(shè)置2個一維數(shù)組lowcost[]和nearest[]。 對所有尚未包含在生成樹上的結(jié)點j，lowcost[j]始終是結(jié)點j與樹中結(jié)點相鄰的邊中權(quán)值最小者，而nearest[j]是此邊在生成樹上的那個端點。 在Prim算法的執(zhí)行過程中:

先找出V-U集合（即不屬于點集U）中使lowcost值最小的頂點j，然后根據(jù)數(shù)組nearest選取邊(j,nearest[j］)，將j添加到U中，最后對nearest[]和lowcost[]數(shù)組作必要的更新修改。

程序6-8Prim算法的實現(xiàn)見下頁：lowcost[k]=0;nearest[k]=k;mark[k]=true; //源點k加入生成樹for(i=1;i<n;i++){ //加入n-1條邊(頂點)

for(p=a[k];p;p=p->nextArc){ //修改lowcost和nearest的值

intj=p->adjVex; if((!mark[j])&&(lowcost[j]>p->w)){ lowcost[j]=p->w;nearest[j]=k; } } Tmin=INFTY; //常量INFTY的值大于所有邊的權(quán)值

for(intj=0;j<n;j++) //尋找下一條最小權(quán)值的邊

if((!mark[j])&&(lowcost[j]<min)){ min=lowcost[j];k=j; } mark[k]=true; //將結(jié)點k加到生成樹上}程序6-8按（鄰接表和mark[]、lowcost[]、nearest[]數(shù)組中）結(jié)點的編號順序輸出，可輸出以下邊集：（1,1,0)(3,2,5)(1,3,1)(6,4,2)(2,5,3)(3,6,4)從小到大的結(jié)點編號jnearest[j]:結(jié)點j接入到生成樹中的另一端接入結(jié)點lowcost[j]:邊的權(quán)值Prim算法時間復(fù)雜度很明顯，程序6-8實現(xiàn)的Prim算法所需的時間復(fù)雜度為O(n2)。比較Prim算法和Kruskal算法Prim算法：保證S所代表的子圖是一棵樹的前提下，選擇一條最小代價的邊e=(u,v);Kruskal算法：構(gòu)造生成樹的過程中,邊集S代表的子圖不一定是連通的;按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v);Prim算法：由于Prim算法中每次選取的邊兩端總是一個已連通頂點和一個未連通頂點，故這個邊選取后一定能將該未連通點連通而又保證不會形成回路。因此每選擇一條邊后，無須再判斷邊集S∪e是否包含回路。Kruskal算法：為了確保最終得到生成樹，每選擇一條邊時，都需要判定邊集S∪e是否包含回路。算法正確性證明定理6-5是Prim算法和Kruskal算法的理論基礎(chǔ)，可由反證法得證（見P123圖6-12）！無論Prim算法還是Kruskal算法，每一步選擇的邊均符合定理6-5，因此必定存在一棵最小代價生成樹包含每一步上已經(jīng)形成的生成樹和新添加的邊，因此定理6-6成立。定理6-5：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的一個真子集。如果(u,v)

E是所有u

U，v

V-U的邊中權(quán)值c[u][v]最小者，那么一定存在G的一棵最小代價生成樹T=(V,S),以(u,v)為其中一條邊。這一性質(zhì)也稱為MST性質(zhì)。定理6-6：Prim算法和Kruskal算法都將產(chǎn)生一個帶權(quán)無向連通圖的最小代價生成樹。思考題：最大間隔聚類按個體間的距離，對一組個體進行分類或組成相關(guān)的群體，使同一組內(nèi)的個體是“接近的”而不同組的個體是“遠(yuǎn)離的”——聚類。一般認(rèn)為彼此距離較大的個體互相是不相似的。距離的含義：物理距離兩個物種的距離（進化進程中開始分支的年數(shù)）兩幅圖像的距離（亮度值至少相差某個閥值的對應(yīng)像素的個數(shù)）問題描述：給定集合U,其n個個體標(biāo)記為p1,p2,...,pn，對于每對個體pi和pj有一個數(shù)值距離d(pi,pj)。（U的）k聚類——對于給定的參數(shù)k，尋求將U中的個體劃分成k組非空集合C1,C2,...,Ck。（一個k聚類的）間隔——處在不同聚類中的任何一對點之間的最小距離。最大間隔聚類：具有最大可能間隔的k聚類。一個集合有指數(shù)多個不同的k聚類，如何有效地找出有最大間隔的聚類？提示：應(yīng)試圖將鄰近的點盡可能快的一起帶入同一個聚類中。采用Kruskal最小生成樹算法，按照距離d(pi,pj)增加的順序在點對之間依次加邊。一旦得到了k個連通分支我們就停止這個過程。單鏈聚類提示：應(yīng)試圖將鄰近的點盡可能快的一起帶入同一個聚類中。采用Kruskal最小生成樹算法，按照距離d(pi,pj)增加的順序在點對之間依次加邊。一旦得到了k個連通分支我們就停止這個過程。換句話說：我們運行Kruskal算法，但是就在它加最后的k-1條邊之前停止。等價于：取整棵最小生成樹T（好像Kruskal算法已經(jīng)把它生成了），刪除k-1條最貴的邊（我們從來沒有真正把它們加上）。聚類1聚類3聚類2如圖所示：一個具有k=3個聚類的單連接聚類的例子。聚類通過按距離增加的次序在點之間加邊而構(gòu)成。由刪除最小生成樹T的k-1條最貴的邊所構(gòu)成的連通分支C1,C2,...,Ck組成一個最大間隔的k聚類。證明：若C表示聚類C1,C2,...,Ck，設(shè)C的間隔正好是最小生成樹中第k-1條最貴的邊的長度d*(這就是Kruskal算法在我們停止的時刻將要添加的下一條邊的長度）?，F(xiàn)在考慮某個其他的k聚類C’，它把U劃分成非空的集合C1’,C2’,...,Ck’。我們必須證明C’的間隔至多是d*！如何證明？證明（續(xù)）：因為C和C’是不同的聚類，因此一定存在C中的某個集合Cr不是C’中的任何一個集合。

因此存在點pi,pj∈Cr，分屬于C’中不同的聚類——比如pi

∈Cs’且pj∈Ct’≠Cs’。由于pi與pj屬于聚類C中的同一個連通分支Cr，因此pi與pj之間一定存在一條路徑P，該路徑上的所有邊均已在Kruskal算法停止前添加過。因此特別的，路徑P上的每條邊的長度至多是d*。證明（續(xù)）：聚類Crpipp’pj聚類Cs’聚類Ct’令p’是在(從pi到pj的)路徑P上第一個不屬于Cs’的結(jié)點，令p是路徑P上緊接在p’之前的結(jié)點。由前面的論證可知：d(p,p’)≤d*。但是p和p’分屬于聚類C’中的不同集合，因此C’的間隔至多是d(p,p’)≤d*。得證：任何其他聚類的間隔不比由單鏈算法找到聚類的間隔更大！單源最短路徑問題：給定帶權(quán)有向圖G=(V,E)，求從某個給定的源點v0

V到其余各頂點的最短路徑。6.6迪杰斯特拉算法（補充）

024170535010353031520101520源點終點最短路徑路徑長度01（0,2,3,1）452（0,2）103（0,2,3）254（0,2,3,1,4）555－∞(a)帶權(quán)的有向圖G(b)圖G頂點0的單源最短路徑圖9-17單源最短路徑迪杰斯特拉算法按從源點到其他各頂點的最短路徑長度的從小到大的次序逐一產(chǎn)生最短路徑。

把V分成兩組：

（1）S：存放已求得最短路徑的頂點的集合

（2）T=V-S：尚未確定最短路徑的頂點集合

將T中頂點按最短路徑非遞減的次序加入到S中。迪杰斯特拉（Dijkstra）算法思想：

這個過程中，總保持：

從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度。而且每個頂點對應(yīng)一個距離值：

S中頂點對應(yīng)的距離值，是從V0到此頂點的最短路徑長度；

T中頂點對應(yīng)的距離值，是從V0到此頂點的只包括S中頂點作中間頂點的當(dāng)前最短路徑長度。單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑1002417053501035303152010152050∞∞70單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520105025∞70單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞60單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞55單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞55單源最短路徑圖例求上圖中源點0到其他各頂點的最短路徑024170535010353031520101520104525∞55迪杰斯特拉算法求單源最短路徑步驟：首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有頂點之間的最短路徑都已求得為止。初始狀態(tài)下集合S中只有源點v0，即：

S={v0}，T={其余頂點}。T中頂點vi對應(yīng)的當(dāng)前最短路徑長度： 若存在<v0,vi>，為<v0,vi>弧上的權(quán)值w(v0,vi)

若不存在<v0,vi>

，為∞從T中選取一個當(dāng)前最短路徑長度最小的頂點vk加入S。對T中剩余頂點vi的當(dāng)前最短路徑長度進行修改： 若加進vk作中間頂點，從v0到vi的距離值比不加vk的路徑要短，則修改此距離值。重復(fù)上述步驟，按照當(dāng)前最短路徑長度的非減次序產(chǎn)生下一條最短路徑，并將該路徑的終點t

T加入S中，并更新T中剩余頂點的當(dāng)前最短路徑長度。直到S＝V時（即從源點v0到其他所有結(jié)點之間的最短路徑都已求得為止），算法結(jié)束。選擇數(shù)據(jù)結(jié)構(gòu)

一維數(shù)組d

d[i]中存放從源點v0到vi的當(dāng)前最短路徑長度，該路徑上除頂點vi自身外，其余頂點都屬于S，并且是所有這些路徑中的最短者。

一維整型數(shù)組path

path[i]給出從v0到頂點vi的最短路徑上，位于頂點vi前面的那個頂點。

例如：從v0到v1的最短路徑為（v0,v2,v3,v1）

則有path[1]=3，path[3]=2，path[2]=0一維布爾數(shù)組s

若s[i]為true，表示頂點vi在S中；否則表示vi在V-S中。

Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-1

初始狀態(tài)S={v0}，T={其余頂點}。024170535010353031520101520源點v0到自身的路徑長度為0，路徑上0前面的頂點不存在因此為-1。初始狀態(tài)下T中頂點vi對應(yīng)的當(dāng)前最短路徑長度d[i]和該路徑上i前面的結(jié)點path[i]值為：若存在<v0,vi>，則d[i]為<v0,vi>弧上的權(quán)值w(v0,vi)，且path[i]=0；若不存在<v0,vi>

，則d[i]為∞，且path[i]=-1。50，010，0∞，-170，0∞，-10第一條最短路徑是T=V-{v0}集合中所有頂點的當(dāng)前最短路徑中最短者：

求第一條最短路徑Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1024170535010353031520101520選擇頂點v2加入集合S，則d[2]為源點v0到頂點v2的最短路徑，path[2]為該最短路徑上頂點v2前面的那個頂點v0

。02024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1頂點vk加入S后，對所有T=V-S集合中的剩余頂點vi，按公式修正從源點v0到該頂點的當(dāng)前最短路徑長度：更新d[]和path[]若d[i]值被更新，則path[i]值也隨之更新為k。02重復(fù)下面步驟：（1）按照非減次序選擇下一條最短路徑的終點（T=V-S中具有最短的當(dāng)前最短路徑長度的頂點vk），滿足：（2）vk加入S集合中后，修正T中剩余頂點vi的當(dāng)前最短路徑長度d[i]和path[i]值：若d[i]更新，則path[i]也相應(yīng)的更新為k直到S＝V時算法結(jié)束。024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1選擇頂點v3加入S。則d[3]為源點v0到頂點v3的最短路徑，path[3]為最短路徑上頂點v3前面的那個頂點。023024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1023024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-10231將頂點v1加入S。則d[1]為源點v0到頂點v1的最短路徑，path[1]為最短路徑上頂點v1前面的那個頂點。024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1{0,2,3,1}0，-145，310，025，255，1∞，-10231024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1{0,2,3,1}0，-145，310，025，255，1∞，-10231選擇頂點v4加入S。則d[4]為源點v0到頂點v4的最短路徑，path[4]為最短路徑上頂點v4前面的那個頂點。4024170535010353031520101520Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1{0,2}0，-150，010，025，270，0∞，-1{0,2,3}0，-145，310，025，260，3∞，-1{0,2,3,1}0，-145，310，025，255，1∞，-1{0,2,3,1,4}0，-145，310，025，255，1∞，-1021435算法的C++程序?qū)崿F(xiàn)（1）s[i]=false（2）（3）path[i]:

若<v0,vi>E，則path[i]=v0；否則，path[i]=-1。

初始化Sd[0]path[0]d[1]path[1]d[2]path[2]d[3]path[3]d[4]path[4]d[5]path[5]{0}0，-150，010，0∞，-170，0∞，-1template<classT>voidExtMGraph<T>::

Dijkstra(intv,T*d,int*path){ inti,k,w; if(v<0||v>n-1)cout<<“OutOfBounds”;return; bool*s=newbool[n];//初始化s、d、pathfor(i=0;i<n;i++) { s[i]=false;

d[i]=a[v][i];if(i!=v&&d[i]<INFTY)path[i]=v;