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

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

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

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

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

k有j-i-1種選擇，每種選擇會導致2個完全不同的子問題產(chǎn)生，因此，動態(tài)規(guī)劃算法的計算量比較大?。。∫粋€直觀想法是直接選擇k的值，使得一個子問題為空，從而加快計算速度！這就導致了貪心算法！10.1活動安排問題2023/6/309（用貪心算法）貪心策略：對輸入的活動以其完成時間的非減序排列，算法每次總是選擇具有最早完成時間的相容活動加入最優(yōu)解集中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]456789101112131410.1活動安排問題2023/6/301010.1活動安排問題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表示活動的開始和結束時間，n個輸入活動已經(jīng)按照活動結束時間進行單調遞增順序排序；2）算法②~③目的是尋找Sij中最早結束的第一個活動，即找到與ai兼容的第一個活動am，利用am與Smj的最優(yōu)子集的并集構成Sij的最優(yōu)子集；3）時間復雜度O(n)。10.1活動安排問題2023/6/3012Recursive-Activity-Selector屬于遞歸性貪心算法，它以對自己的遞歸調用的并操作結束，幾乎就是“尾遞歸調用”，因此可以轉化為迭代形式：Greedy-Activity-Selector(s,f){n←length[s];A←{a1}i←1//下標i記錄了最近加入A的活動aiform←2ton//尋找Si,n+1中最早結束的兼容活動doifsm≥fithenA←AU{am}i←mreturnA;}10.1活動安排問題2023/6/3013貪心算法的正確性證明：定理16.1：對于任意非空子問題Sij，設am是Sij中具有最早結束時間的活動，即fm=min{fk

:ak∈Sij

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

:ak∈Sij

}，則：

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

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

10.1活動安排問題2023/6/3015定理16.1：對于任意非空子問題Sij，設am是Sij中具有最早結束時間的活動，即fm=min{fk

:ak∈Sij

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

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

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

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

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

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

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

，則GreedyKnapsack算法對于給定的背包問題實例生成一個最優(yōu)解證明基本思想：把貪心解與任一最優(yōu)解相比較，如果這兩個解不同，就去找開始不同的第一個xi，然后設法用貪心解的xi去代換最優(yōu)解的xi，并證明最優(yōu)解在分量代換之后其總價值保持不變，反復進行下去，直到新產(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，此時可以用貪心法求最優(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ù)這種貪心策略，首先選擇最輕的貨箱，然后選擇次輕的貨箱，如此下去直到所有貨箱均裝上船或者船上不能容納其他任何一個貨箱。計算實例：假設n=8,[w1,w2,…,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,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當且僅當貨箱i被裝載，對重量按間接尋址方式排序newt[n+1];//產(chǎn)生數(shù)組t，用于間接尋址

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

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

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

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

證明:（反證法）即證明從源到u沒有更短的其他路徑。假設存在一條從源到u且長度比dist[u]更短的路，設這條路初次走出S之外到達頂點為x#V-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的最短路徑長度。Svux10.7最小生成樹問題描述：

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

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