第六章貪心法.ppt

第六章貪心法,貪心法的學(xué)習(xí)提綱,一般方法適合求解的問題基本思想(求解問題的過程)算法控制流程算法的正確性證明應(yīng)用舉例背包問題帶時限的作業(yè)排序問題,貪心算法的直觀含義,例1.如：找硬幣0.15元，要求硬幣數(shù)最少。找硬幣方法就是一種貪心算法.（1）面值；5分、2分、1分：（2）面值：11分、5分、1分：從此例可以看出：1，貪心法未必總能求得問題的最優(yōu)解；2，貪心算法總是作出在當(dāng)前看來是最好的選擇.也就是說貪心算法不從整體最優(yōu)上加以考慮,它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心算法不是對所有問題都能得到整體最優(yōu)解,但對范圍相當(dāng)廣的許多問題它都能產(chǎn)生最優(yōu)解。如單源最短路徑問題，最小生成樹問題等。而且,在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解！,3個5分(最優(yōu)),1個11分4個1分(次優(yōu)),6.1一般方法,貪心方法適合的問題是最優(yōu)化問題。最優(yōu)化問題：有n個輸入，而它的解就由這n個輸入的滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解。顯然，可行解一般來說是不唯一的，為了衡量可行解的好壞，問題還給出某個值函數(shù)，稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。,目標(biāo)函數(shù)：,約束條件（函數(shù)）：,其中：,可行解：,如找硬幣問題可描述如下：,最優(yōu)化問題的解可表示成一個n元組X=（x1,x2xn），其中每個分量取自某個值集S，所有允許的n-元組組成一個侯選解集。,6.1一般方法,貪心方法適合的問題是最優(yōu)化問題。最優(yōu)化問題：有n個輸入，而它的解就由這n個輸入的滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解。顯然，可行解一般來說是不唯一的，為了衡量可行解的好壞，問題還給出某個值函數(shù)，稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。,最優(yōu)化問題的解是一個n元組,貪心法是通過分步?jīng)Q策的方法來解決問題的。貪心法在求解問題的每一步上作出某種決策，產(chǎn)生n-元組的一個分量，貪心法要求根據(jù)題意，選定一種最優(yōu)量度標(biāo)準，作為選擇當(dāng)前分量的依據(jù)，這種在貪心法每一步上用做決策依據(jù)的選擇準則被稱為最優(yōu)量度標(biāo)準（貪心準則，也稱貪心選擇性質(zhì)）。,6.1一般方法,貪心法的基本思想:是依據(jù)題意選取一種量度標(biāo)準，然后按照這種量度標(biāo)準對這n個輸入進行排序，并按序一次輸入一個量，作為n-元組的一個分量，如果這個輸入量的加入不滿足約束條件,則不把此輸入加入到部分解向量中.,貪心法求解問題的過程:選取最優(yōu)量度標(biāo)準依最優(yōu)量度標(biāo)準對n個輸入排序初始狀態(tài)下,解向量solution=中;按序一次取一個輸入量，作為n-元組的一個分量，若加入該分量滿足給定的約束條件，則加入，否則，不加入，繼續(xù)檢測下一個分量.,貪心方法的抽象化控制,算法6.1貪心法的控制流程SolutionTypeGreedy(STypea，intn)SolutionTypesolutions=/將解向量solution初始化為空for(inti=0;i0.如果這些物品重量的和大于M,要求所有選中要裝入背包的物品總重量不得超過M,而裝入背包物品獲得的總效益最大.即,0xil，pi0，wi0，0in-1,滿足約束條件的任一集合(x0，xn-1)是一個可行解(即能裝下)，使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。,背包問題描述：,約束條件：,例6.1n3，M=20，P(25，24，15)，W=(18，15，10)假設(shè)物品可分，故有可行解無數(shù)個，其中的四個可行解是：(x0，x1，x2)wixipixi(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在這四個可行解中，第個解的效益值最大。但這個解是否是背包問題的最優(yōu)解，尚無法確定，但有一點是可以肯定的，即對于一般背包問題，其最優(yōu)解顯然必須裝滿背包。,6.3背包問題,貪心法求解背包問題選擇量度標(biāo)準計算在此量度標(biāo)準下的”最優(yōu)解”(1)選目標(biāo)函數(shù)作為量度標(biāo)準,即”效益”優(yōu)先,使每裝入一件物品就使背包獲得最大可能的效益值增量.按物品收益從大到小排序0,1,2解為:(x0,x1,x2)=(1,2/15,0)收益:25+24*2/15=28.2,6.3背包問題,非最優(yōu)解,原因:只考慮當(dāng)前收益最大,而背包可用容量消耗過快.,M=20,P(25,24,15)W=(18，15，10),貪心法求解背包問題選擇量度標(biāo)準計算在此量度標(biāo)準下的”最優(yōu)解”(2)選重量作為量度,使背包容量盡可能慢地被消耗.,6.3背包問題,按物品重量從小到大排序:2,1,0;解為:(x0,x1,x2)=(0,2/3,1)收益:15+24*2/3=31,非最優(yōu)解,原因:雖然容量消耗慢，但效益沒有很快的增加.,M=20,P(25,24,15)W=(18，15，10),貪心法求解背包問題選擇量度標(biāo)準計算在此量度標(biāo)準下的”最優(yōu)解”(3)選利潤/重量為量度使每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益。,6.3背包問題,M=20,P(25,24,15)W=(18，15，10),按物品的pi/wi重量從大到小排序:1,2,0;解為:(x0,x1,x2)=(0,1,1/2)收益:24+15/2=31.5,可見，可以pi/wi作為背包問題的最優(yōu)量度標(biāo)準.,最優(yōu)解,算法6.2以pi/wi為最優(yōu)量度標(biāo)準的背包問題的貪心算法voidGreedyKnapsack(float*p,float*w,floatM,intn,float*x)/前置條件：wi已按pi/wi的非增次序排列floatu=M;/u為背包剩余載重量，初始時為mfor(inti=0;iu)break;xi=1.0;u=uwi;if(ipixi。不失一般性，可以假定wiyi=M。（2）設(shè)k是使得ykxk的最小下標(biāo)?？梢酝频脃kj分別得證明：,若kM，從而ykj，(1,1,1,.,1,xj,0,0),jK,反證法：,所以,必有ykxk，有wiyiM，是不可能的。,(3)把yk增加到xk,那末必須從(yk+1，yn-1)中減去同樣多的量，使得所用的總?cè)萘咳允荕。這導(dǎo)致一個新的解Z=(z0，zn-1)，其中，zi=xi，0ik，并且,因此，對于Z有,變換,Z不比Y差,重復(fù)上面的討論,把Y轉(zhuǎn)換成X,從而證明了X也是最優(yōu)解.證畢。,對于0/1背包問題，使用貪心法，并不一定能求得最優(yōu)解，因此，貪心法不能用來求解0/1背包問題例，n3，M=25，P(32，24，15)，W(16，15，10).P/W=(2,1.6,1.5)X=(0)p=32,CU=M-W(0)=9不能放下任何物品，顯然X=(0)不是最優(yōu)解。最優(yōu)解是(1,2)，利潤為39。,6.3背包問題,6.3帶有限期的作業(yè)排序,在一單機無其他資源約束的處理系統(tǒng)中，運行n個作業(yè)，假設(shè)每個作業(yè)運行1個單位時間，且每個作業(yè)i都有一個截止期限di0(它是整數(shù))，若作業(yè)i能在它的期限截止前被完成，則可獲得pi0的效益。要求找到作業(yè)的子集X及X的一個排列，使得按調(diào)度作業(yè)運行，X中的作業(yè)都能如期完成，且獲收益最大?？尚薪猓鹤蛹疿中的作業(yè)都能如期完成，則X為可行解?？尚薪獾氖找妫嚎尚薪釾中所有作業(yè)的收益之和，即。最優(yōu)解：具有最大收益的可行解就是最優(yōu)解。,6.3.1問題描述,例6.2n=4,(p0,p1,p2,p3)(100,10,15,20)、(d0,d1,d2,d3)=(2,1,2,1)可行解和它們的效益值如下：可行解處理順序效益值(0)1100(1)110(2)115(3)120(0，1)1，0110(0，2)0，2或2，0115(0，3)3，0120(1，2)1，225解是最優(yōu)的,所允許的處理次序是:先處理作業(yè)3,再處理作業(yè)0.,3,0,6.3帶有限期的作業(yè)排序,6.3.2貪心法求解,(1),把目標(biāo)函數(shù)作為量度.使用這一量度,下一個要計入的作業(yè)將是使得在滿足所產(chǎn)生的X是一個可行解的限制條件下讓得到最大增加的作業(yè).(2),按pi的非增次序來考慮這些作業(yè);如例6.2，按pi的非增次序?qū)ψ鳂I(yè)進行排序（0，3，2，1）開始時:X，,X0，p0=100作業(yè)0有最大效益X0，3p0+p3=120作業(yè)3有第二大效益作業(yè)2,1都被舍棄,6.3帶有限期的作業(yè)排序,算法6.3帶時限作業(yè)排序算法,voidGreedyJob(int*d，int*X，n)/作業(yè)按p0p1pn-1的次序輸入，它們的期限值d(i)1，0in-1，n1。X是在它們的截止期限前完成的作業(yè)的集合/X0for(inti=1;i=j+1每個作業(yè)執(zhí)行一個單位時間排列位置為j的作業(yè)aj應(yīng)在j+1時刻執(zhí)行完畢,(2)判斷X子集是否可行?只需判斷它的一個特殊排列是否可行即可;這個特殊的排列就是X中作業(yè)按時限的非降次序的排列,算法6-3的核心步驟是:判定集合Xi中的作業(yè)是否能在截止期限前完成,這一操作步驟也就是所謂的可行性判定.,某一作業(yè)子集X是否是可行解，只需找到一種X的排列a,如果X中的作業(yè)能按a的次序執(zhí)行而不超期，則X為可行解.,6.3帶有限期的作業(yè)排序,6.3.4可行性判定-(2)如何變?yōu)橛行惴?,定理6-3X=(x0,x1,xk)是k個作業(yè)的集合,a=(a0,a1,a2ak)是X的一種特定排列,它使得da0j+1(r+1jk)b,djr+1;,6.3帶有限期的作業(yè)排序,6.3.5作業(yè)排序算法,【程序6-4】帶時限的作業(yè)排序程序intJS(int*d,int*x,intn)/設(shè)p0p1pn1intk=0;x0=0;for(intj=1;j=0,6.3帶有限期的作業(yè)排序,6.3.5作業(yè)排序算法,n-1/O(n),k+1,k-r,每次迭代的總時間為O(k),若s是k的終值,即s是最后所得解的作業(yè)數(shù).則JS所需的總時間是O(sn).由于s=0可將b分成b個時間片，每個時間片一個單位;為了實現(xiàn)算法方便，引入了虛擬時間片-1,0,它不同用于時間分配作業(yè)排序過程:(1),設(shè)作業(yè)已按收益的非增次序排列(2),作業(yè)i的時限是di,為它分配的時間片是r-1,r,其中，r是使0r,就可將作業(yè)I在位置r+1處插入,從而得到一個按期限的非降次序排列的含有k+1個作業(yè)的可行解。以上過程可反復(fù)進行到對第n個作業(yè)處理完畢,所得到的貪心解是一個最優(yōu)解。這一處理過程可用算法6.3來描述.算法中引進了一個虛構(gòu)的作業(yè)0,它放在X(0),且D(X(0)0.引入這一虛構(gòu)作業(yè)是為了便于將作業(yè)插入位置1。,6.3帶有限期的作業(yè)排序,1.貪心選擇性質(zhì),所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。,6.2貪心法的基本要素,當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì).問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。,2.最優(yōu)子結(jié)構(gòu)性質(zhì),6.2貪心法的基本要素,3.貪心法與動態(tài)規(guī)劃法的異同,共同點:都可用來求解最優(yōu)化問題;且要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì).差異:貪心法是自頂向下的決策方法,而動態(tài)規(guī)劃法使用自底向上的決策方法.對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?當(dāng)具有最優(yōu)子結(jié)構(gòu)特性的最優(yōu)化問題找不到最優(yōu)量度標(biāo)準時，可以選用動態(tài)規(guī)劃方法.,定理6.2算法6.3所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。,證明:設(shè)X=(x0,x1,xk)是某個帶時限作業(yè)排序問題實例的貪心法求得的解，若X不是最優(yōu)解，假設(shè)另有Y=(y0,y1,yr)是最優(yōu)解.(1)假設(shè)XY,必有且(2)存在排列a,b使X,Y可行(3)將a,b中的相同作業(yè)移到相同位置(4)對于不同作業(yè)用X中的相同位置上的作業(yè)替換Y的作業(yè)假定IX,因此,至少存在著這樣的兩個作業(yè)a和b,使且,bY且.由貪心方法可以得出,對于在Y中又不在X中的所有作業(yè)b,都有papb.這是因為若pbpa,則貪心方法會先于作業(yè)a考慮作業(yè)b并且把b計入到X中去.,t,a,b,papb,6.3帶有限期的作業(yè)排序,證明:設(shè)X=(x0,x1xk)是某個帶時限作業(yè)排序問題實例的貪心算法求得的解，如果X不是最優(yōu)解，另有Y=(y0,y1,yr)是最優(yōu)解.設(shè)XY,則必有因為若則Y不是可行解;否則，若Y是可行解，那么貪心算法定會將屬于Y但不屬于X的其他作業(yè)繼續(xù)加入X,若則不是最優(yōu)解。因為和是問題的兩個可行解，設(shè)分別是X和Y的可行的作業(yè)排列,也就是說,按的次序調(diào)度作業(yè)執(zhí)行，X和Y中的作業(yè)都不會超期.將中相同的作業(yè)移到相同的位置,并且不影響兩個排列的可行解性質(zhì).若存在作業(yè)x,使得,x在序列中的位置先于在中的位置可將a序列中的x和z交換位置，這樣不會引起任何作業(yè)超期.,定理6.2程序6-3的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。,6.3.3算法正確性-(1)該算法能否找到最優(yōu)解?,因為,則必存在兩個作業(yè)a和b,使得假定作業(yè)a是使得的一個收益最大的作業(yè)，那么，由貪心法可知，對任意作業(yè)b,都有papb,否則，作業(yè)b將被程序6-3加入X中，假定b是其中一作業(yè)，它在中的位置與a在中的位置相同，現(xiàn)用a取代序列中的b,得到一個新序列，很顯然新序列仍然是可行的且新序列的收益不低于Y,可以重復(fù)這樣的替換,最終要么將Y轉(zhuǎn)換成X,要么，證明Y不是可行解.,定理6.2程序6-3的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。,用X中的作業(yè)a替換Y中的作業(yè)b,得到新的作業(yè)集X。,6.3.3算法正確性-(1)該算法能否找到最優(yōu)解?,下面對程序6-3的if語句進一步細化。if(Xi的所有作業(yè)都能在它們的截止期限前完成)XXi(1)檢驗X作業(yè)子集是否可行?檢驗X的所有可能的排列，假定X中有k個作業(yè)，這就需要檢查k!個排列。事實上，對于X