分析最優(yōu)解的結(jié)構(gòu)特征課件

主講人：呂敏Email:{lvmin05@}Spring2012，USTC算法基礎(chǔ)2023/6/302第十講貪心算法內(nèi)容提要：理解貪心算法的概念

掌握貪心算法的基本要素理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異通過范例學(xué)習(xí)貪心算法設(shè)計(jì)策略10.1活動(dòng)安排問題2023/6/303當(dāng)一個(gè)問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，可用動(dòng)態(tài)規(guī)劃法求解，但有時(shí)用貪心算法求解會(huì)更加的簡(jiǎn)單有效。顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。10.1活動(dòng)安排問題2023/6/304設(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，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。即當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容.問題：選出最大的相容活動(dòng)子集合。10.1活動(dòng)安排問題2023/6/305（用動(dòng)態(tài)規(guī)劃方法）步驟1：分析最優(yōu)解的結(jié)構(gòu)特征—構(gòu)造子問題空間:Sij={ak∈S:fi≤sk<fk≤sj}

Sij包含了所有與ai和aj相兼容的活動(dòng)，并且與不遲于ai結(jié)束和不早于aj開始的活動(dòng)兼容。此外，虛構(gòu)活動(dòng)a0和an+1，其中f0=0,Sn+1=∞。原問題即為尋找S0,n+1中最大兼容活動(dòng)子集。10.1活動(dòng)安排問題2023/6/306—證明原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。即：若已知問題Sij的最優(yōu)解Aij中包含活動(dòng)ak，則在Sij最優(yōu)解中的針對(duì)Sik的解Aik和針對(duì)Skj的解Akj也必定是最優(yōu)的。（反證法即可！）—證明可以根據(jù)子問題的最優(yōu)解來構(gòu)造出原問題的最優(yōu)解。一個(gè)非空子問題Sij的任意解中必包含了某項(xiàng)活動(dòng)ak，而Sij的任一最優(yōu)解中都包含了其子問題實(shí)例Sik和Skj的最優(yōu)解（根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)?。Ｒ虼?，可以構(gòu)造出Sij的最大兼容子集。10.1活動(dòng)安排問題2023/6/307步驟2：遞歸地定義最優(yōu)解的值設(shè)c[i,j]為Sij中最大兼容子集中的活動(dòng)數(shù)。當(dāng)Sij=φ時(shí)，c[i,j]=0。對(duì)于一個(gè)非空子集Sij，如果ak在Sij的最大兼容子集中被使用，則子問題Sik和Skj的最大兼容子集也被使用。從而：

c[i,j]=c[i,k]+c[k,j]+1由于Sij的最大子集一定使用了i到j(luò)中的某個(gè)值k，通過檢查所有可能的k值，就可以找到最好的一個(gè)。因此，c[i,j]的完整遞歸定義為：10.1活動(dòng)安排問題2023/6/308問題：

k有j-i-1種選擇，每種選擇會(huì)導(dǎo)致2個(gè)完全不同的子問題產(chǎn)生，因此，動(dòng)態(tài)規(guī)劃算法的計(jì)算量比較大?。?！一個(gè)直觀想法是直接選擇k的值，使得一個(gè)子問題為空，從而加快計(jì)算速度！這就導(dǎo)致了貪心算法！10.1活動(dòng)安排問題2023/6/309（用貪心算法）貪心策略：對(duì)輸入的活動(dòng)以其完成時(shí)間的非減序排列，算法每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入最優(yōu)解集中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]456789101112131410.1活動(dòng)安排問題2023/6/301010.1活動(dòng)安排問題2023/6/3011Recursive-Activity-Selector(s,f,i,j){①m←i+1;②whilem<jandsm<fi③dom←m+1④ifm<j⑤thenreturn{am}URecursive-Activity-Selector(s,f,m,j)⑥elsereturnφ}說明：

1）數(shù)組s和f表示活動(dòng)的開始和結(jié)束時(shí)間，n個(gè)輸入活動(dòng)已經(jīng)按照活動(dòng)結(jié)束時(shí)間進(jìn)行單調(diào)遞增順序排序；2）算法②~③目的是尋找Sij中最早結(jié)束的第一個(gè)活動(dòng)，即找到與ai兼容的第一個(gè)活動(dòng)am，利用am與Smj的最優(yōu)子集的并集構(gòu)成Sij的最優(yōu)子集；3）時(shí)間復(fù)雜度O(n)。10.1活動(dòng)安排問題2023/6/3012Recursive-Activity-Selector屬于遞歸性貪心算法，它以對(duì)自己的遞歸調(diào)用的并操作結(jié)束，幾乎就是“尾遞歸調(diào)用”，因此可以轉(zhuǎn)化為迭代形式：Greedy-Activity-Selector(s,f){n←length[s];A←{a1}i←1//下標(biāo)i記錄了最近加入A的活動(dòng)aiform←2ton//尋找Si,n+1中最早結(jié)束的兼容活動(dòng)doifsm≥fithenA←AU{am}i←mreturnA;}10.1活動(dòng)安排問題2023/6/3013貪心算法的正確性證明：定理16.1：對(duì)于任意非空子問題Sij，設(shè)am是Sij中具有最早結(jié)束時(shí)間的活動(dòng)，即fm=min{fk

:ak∈Sij

}，則：1）活動(dòng)am在Sij的某最大兼容活動(dòng)子集中被使用；2）子問題Sim為空，所以選擇am將使子問題Smj為唯一可能非空的子問題。10.1活動(dòng)安排問題2023/6/3014定理16.1：對(duì)于任意非空子問題Sij，設(shè)am是Sij中具有最早結(jié)束時(shí)間的活動(dòng)，即fm=min{fk

:ak∈Sij

}，則：

1）活動(dòng)am在Sij的某最大兼容活動(dòng)子集中被使用；2）子問題Sim為空，所以選擇am將使子問題Smj為唯一可能非空的子問題。證明：

先證第2部分。假設(shè)Sim非空，因此有活動(dòng)ak滿足fi≤sk<fk≤sm<fm。ak同時(shí)也在Sij中，且具有比am更早的結(jié)束時(shí)間，這與am的選擇相矛盾，故Sim為空。

10.1活動(dòng)安排問題2023/6/3015定理16.1：對(duì)于任意非空子問題Sij，設(shè)am是Sij中具有最早結(jié)束時(shí)間的活動(dòng)，即fm=min{fk

:ak∈Sij

}，則：1）活動(dòng)am在Sij的某最大兼容活動(dòng)子集中被使用；2）子問題Sim為空，所以選擇am將使子問題Smj為唯一可能非空的子問題。證明：再證第1部分。設(shè)Aij為Sij的最大兼容活動(dòng)子集，且將Aij中的活動(dòng)按結(jié)束時(shí)間單調(diào)遞增排序。設(shè)ak為Aij的第一個(gè)活動(dòng)。如果ak=am，則得到結(jié)論，即am在Sij的某個(gè)最大兼容子集中被使用。如果ak≠am，則構(gòu)造子集Bij=Aij

–{ak}U{am}。因?yàn)樵诨顒?dòng)Aij中，ak是第一個(gè)結(jié)束的活動(dòng)，而fm≤fk，所以Bij中的活動(dòng)是不相交的，即Bij中活動(dòng)是兼容的。同時(shí)，Bij中活動(dòng)個(gè)數(shù)與Aij中活動(dòng)個(gè)數(shù)一致，因此Bij是包含am的Sij的最大兼容活動(dòng)集合。作業(yè)16.1-116.1-310.2貪心算法的基本要素2023/6/3017基本思想：從問題的某一個(gè)初始解出發(fā)，通過一系列的貪心選擇——當(dāng)前狀態(tài)下的局部最優(yōu)選擇，逐步逼近給定的目標(biāo)，盡可能快地求得更好的解。在貪心算法(greedymethod)中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)按某個(gè)評(píng)價(jià)函數(shù)最優(yōu)的決策，該最優(yōu)評(píng)價(jià)函數(shù)稱為貪心準(zhǔn)則(greedycriterion)貪心算法的正確性，就是要證明按貪心準(zhǔn)則求得的解是全局最優(yōu)解。10.2貪心算法的基本要素2023/6/3018基本步驟：決定問題的最優(yōu)子結(jié)構(gòu)；設(shè)計(jì)出一個(gè)遞歸解；證明在遞歸的任一階段，最優(yōu)選擇之一總是貪心選擇,那么，做貪心選擇總是安全的。證明通過做貪心選擇，所有子問題（除一個(gè)以外）都為空。設(shè)計(jì)出一個(gè)實(shí)現(xiàn)貪心策略的遞歸算法。將遞歸算法轉(zhuǎn)換成迭代算法。10.2貪心算法的基本要素2023/6/3019對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。一、貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。

對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解，否則得到的是近優(yōu)解。10.2貪心算法的基本要素2023/6/3020二、最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。但是，需要注意的是，并非所有具有最優(yōu)子結(jié)構(gòu)性質(zhì)的問題都可以采用貪心策略來得到最優(yōu)解。10.2貪心算法的基本要素2023/6/30210-1背包問題給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?小數(shù)背包問題與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。在選擇裝入背包的物品時(shí)，對(duì)每種物品i

只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i

。10.2貪心算法的基本要素2023/6/3022例：若n=3，w=(10,20,30),v=(60,100,120),c=50，則對(duì)于0-1背包問題，可行解為：(x1,x2,x3)=(0,1,1)=220(x1,x2,x3)=(1,1,0)=160(x1,x2,x3)=(1,0,1)=180最優(yōu)解為：選擇物品2和物品3，總價(jià)值為220對(duì)于小數(shù)背包問題，按照物品價(jià)值率最大的貪心選擇策略，其解為(10,20,20)，總價(jià)值為240。對(duì)于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。10.2貪心算法的基本要素2023/6/3023貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，但是，兩者存在著巨大的差別。10.3小數(shù)背包問題2023/6/3024問題描述：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?這里，在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包。例子：n=3,c=20,v=(25,24,15),w=(18,15,10)，列舉4個(gè)可行解：10.3小數(shù)背包問題2023/6/3025貪心策略設(shè)計(jì)：策略1：按價(jià)值最大貪心，是目標(biāo)函數(shù)增長(zhǎng)最快。按價(jià)值排序從高到低選擇物品②解(次最優(yōu))策略2：按重量最小貪心，使背包增長(zhǎng)最慢。按重量排序從小到大選擇物品③解(次最優(yōu)解)策略3：按價(jià)值率最大貪心，使單位重量?jī)r(jià)值增長(zhǎng)最快。按價(jià)值率排序從大到小選擇物品④解(最優(yōu))10.3小數(shù)背包問題2023/6/3026算法：GreedyKnapsack(n,M,v[],w[],x[]){//按價(jià)值率最大貪心選擇Sort(n,v,w);//使得v1/w1≥v2/w2≥…≥vn/wnfori=1tondox[i]=0;c=M;fori=1tondo{if(w[i]>c)break;

x[i]=1;c-=w[i];}if(i≤n)x[i]=c/w[i];//使物品i是選擇的最后一項(xiàng)}時(shí)間復(fù)雜度:T(n)=O(nlgn)10.3小數(shù)背包問題2023/6/3027貪心選擇的最優(yōu)性證明定理：如果v1/w1≥v2/w2≥…≥vn/wn

，則GreedyKnapsack算法對(duì)于給定的背包問題實(shí)例生成一個(gè)最優(yōu)解證明基本思想：把貪心解與任一最優(yōu)解相比較，如果這兩個(gè)解不同，就去找開始不同的第一個(gè)xi，然后設(shè)法用貪心解的xi去代換最優(yōu)解的xi，并證明最優(yōu)解在分量代換之后其總價(jià)值保持不變，反復(fù)進(jìn)行下去，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解是最優(yōu)解。10.3小數(shù)背包問題2023/6/302810.3小數(shù)背包問題2023/6/302910.3小數(shù)背包問題2023/6/3030特殊的0-1背包問題：如果w1≤w2≤…≤wn,v1≥v2≥…≥vn,則v1/w1≥v2/w2≥…≥vn/wn，此時(shí)可以用貪心法求最優(yōu)解。0-1-Knapsack(v[],w[],n,c){//輸出x[1…n]fori=1tondox[i]=0;value=0.0;fori=1tondo{if(w[i]<c){x[i]=1;c-=w[i];value+=v[i];}elsebreak;}returnvalue;}10.4最優(yōu)裝載2023/6/3031問題的描述:輪船載重為c，集裝箱重量為wi(i=1,2,…,n)，在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上船。形式化定義：10.4最優(yōu)裝載2023/6/3032貪心策略：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪心策略，首先選擇最輕的貨箱，然后選擇次輕的貨箱，如此下去直到所有貨箱均裝上船或者船上不能容納其他任何一個(gè)貨箱。計(jì)算實(shí)例：假設(shè)n=8,[w1,w2,…,w8]=[100,200,50,90,150,50,20,80],c=400。利用貪心算法時(shí)，所考察貨箱的順序?yàn)?,3,6,8,4,1,5,2。貨箱7,3,6,8,4,1的總重量為390個(gè)單位且已被裝載，剩下的裝載能力為10個(gè)單位，小于剩下的任何一個(gè)貨箱。在這種貪心解決算法中得到[x1,x2,…,x8]=[1,0,1,1,0,1,1,1]，且∑xi=610.4最優(yōu)裝載2023/6/3033算法描述：ContainerLoading(x[],w[],c,n){//x[i]=1當(dāng)且僅當(dāng)貨箱i被裝載，對(duì)重量按間接尋址方式排序newt[n+1];//產(chǎn)生數(shù)組t，用于間接尋址

IndirectSort(w,t,n);//此時(shí)，w[t[i]]≤w[t[i+1]],1≤i<nfori=1tondo//初始化xx[i]=0;for(i=1;i≤n&&w[t[i]]≤c;i++){//按重量次序選擇物品

x[t[i]]=1;c=c-w[t[i]];//c為剩余容量}deletet[];}時(shí)間復(fù)雜度：O(nlgn)10.4最優(yōu)裝載2023/6/3034貪心性質(zhì)證明：不失一般性，假設(shè)貨箱都排好序，即wi≤wi+1(1≤i≤n)。令x=[x1,…,xn]為用貪心算法獲得的解，y=[y1,…,yn]為一個(gè)最優(yōu)解，分若干步可以將y轉(zhuǎn)化為x，轉(zhuǎn)換過程中每一步都產(chǎn)生一個(gè)可行的新y，且∑yi（1≤i≤n）的值不變（即仍為最優(yōu)解），從而證明了x為最優(yōu)解。10.5找錢問題2023/6/3035問題定義：使用2角5分，1角，5分和1分四種面值的硬幣時(shí)（各種硬幣數(shù)量不限），設(shè)計(jì)一個(gè)找A分錢的貪心算法，并證明算法能產(chǎn)生一個(gè)最優(yōu)解。設(shè)貨幣種類P={p1,p2,p3,p4}，di和xi分別是pi的貨幣單位和選擇數(shù)量，問題的形式描述為：10.5找錢問題2023/6/303610.5找錢問題2023/6/3037最優(yōu)子結(jié)構(gòu)性質(zhì)證明：10.5找錢問題2023/6/3038貪心選擇性質(zhì)證明：10.5找錢問題2023/6/3039

思考：如果硬幣面值改為1分、5分和1角1分，要找給顧客的是1角5分，是否可以用貪心算法？10.6單源最短路徑2023/6/3040問題描述:給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。如：計(jì)算頂點(diǎn)1（源）到所有其他頂點(diǎn)之間的最短路徑。10.6單源最短路徑2023/6/3041迪杰斯特拉(Dijkstra)算法：

基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。步驟：初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u(貪心策略)，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。直到S包含了所有V中頂點(diǎn)，此時(shí)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。10.6單源最短路徑2023/6/3042例如，對(duì)右圖中的有向圖，應(yīng)用迪杰斯特拉算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列如下表所示。迭代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}51050306010.6單源最短路徑2023/6/3043算法描述：10.6單源最短路徑2023/6/3044算法的運(yùn)算時(shí)間：對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O(n)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時(shí)間。算法的其余部分所需要時(shí)間不超過O(n2)。10.6單源最短路徑2023/6/3045貪心策略為：從V-S中選擇具有最短特殊路徑的頂點(diǎn)u，

從而確定從源到u的最短路徑長(zhǎng)度dist[u]。貪心選擇性質(zhì)證明：

證明:（反證法）即證明從源到u沒有更短的其他路徑。假設(shè)存在一條從源到u且長(zhǎng)度比dist[u]更短的路，設(shè)這條路初次走出S之外到達(dá)頂點(diǎn)為x#V-S，然后徘徊于S內(nèi)外若干次，最后離開達(dá)到u，如上圖所示。在這條路徑上，分別記d(v,x)，d(x,u)和d(v,u)為頂點(diǎn)v到頂點(diǎn)x，頂點(diǎn)x到頂點(diǎn)u和頂點(diǎn)v到頂點(diǎn)u的路長(zhǎng)，那么

dist[x]<=d(v,x)d(v,x)+d(x,u)=d(v,u)<dist[u]利用邊權(quán)的非負(fù)性，可知d(x,u)>=0，從而推得dist[x]<dist[u]。此為矛盾。這就證明了dist[u]是從源到頂點(diǎn)u的最短路徑長(zhǎng)度。Svux10.7最小生成樹問題描述：

設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。2023/6/3046應(yīng)用實(shí)例：通信線路設(shè)計(jì)、電子線路設(shè)計(jì)等網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。2023/6/304710.7最小生成樹最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。常用的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它