算法分析與設(shè)計(jì)貪心法.ppt

第三章 貪心方法,什么是貪心方法 背包問(wèn)題 帶有期限的作業(yè)排序 最優(yōu)歸并模式 最小生成樹(shù) 單源點(diǎn)最短路徑,3.1 什么是貪心方法,某一問(wèn)題的n個(gè)輸入,該問(wèn)題的一種解（可行解）,是A的一 個(gè)子集,滿(mǎn)足一定 的條件,約束條件,目標(biāo)函數(shù),取極值,最優(yōu)解,3.1 什么是貪心方法,根據(jù)題意，選取一種量度標(biāo)準(zhǔn)，然后按量度標(biāo)準(zhǔn)對(duì)n個(gè)輸入排序，按順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法就是貪心方法。,量度標(biāo)準(zhǔn),量度標(biāo)準(zhǔn)意義下的部分最優(yōu)解,原問(wèn)題的 n 個(gè)輸入,排序后的 n 個(gè)輸入,A(j),貪心方法的抽象化控制,Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution,x) then solutionUNION(solution,x) endif repeat return (solution) End GREEDY,按某種最優(yōu)量度標(biāo)準(zhǔn)從A中選擇一個(gè)輸入賦給x，并從A中除去,判斷x是否可以包含在解向量中,將x與解向量合并并修改目標(biāo)函數(shù),3.2 背包問(wèn)題,問(wèn)題描述 已知有n種物品和一個(gè)可容納M重量的背包，每種物品i的重量為wi，假定將物品i的某一部分xi放入背包就會(huì)得到pixi的效益(0xi1, pi0) ，采用怎樣的裝包方法才會(huì)使裝入背包物品的總效益為最大呢？ 問(wèn)題的形式描述 極大化 pixi 約束條件 wi xi M 0xi1, pi0, wi0, 1in,1in,1in,目標(biāo)函數(shù),背包問(wèn)題實(shí)例,考慮下列情況的背包問(wèn)題 n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10) 其中的4個(gè)可行解是：,貪心方法的數(shù)據(jù)選擇策略(1),用貪心策略求解背包問(wèn)題時(shí)，首先要選出最優(yōu)的度量標(biāo)準(zhǔn)?？梢赃x取目標(biāo)函數(shù)為量度標(biāo)準(zhǔn)，每裝入一件物品就使背包獲得最大可能的效益值增量。在這種量度標(biāo)準(zhǔn)下的貪心方法就是按效益值的非增次序?qū)⑽锲芬患诺奖嘲小?如上面的實(shí)例所示，可將物品按效益量非增次序排序： (p1,p2,p3)=(25,24,15)。先裝入物品1重量為18，即x1=1；然后再裝物品2，由于約束條為wi xi M=20，所以物品2只能裝入重量為2的一小部分，即x2=2/15。,貪心方法的數(shù)據(jù)選擇策略(2),按上述的數(shù)據(jù)選擇策略，裝入順序是按照物品的效益值從大到小的輸入，由剛才的方法可得這種情況下的總效益值為pixi = 25+24*2/15=28.2，顯然是一個(gè)次優(yōu)解，原因是背包容量消耗過(guò)快。 2. 若以容量作為量度，可讓背包容量盡可能慢地被消耗。這就要求按物品重量的非降次序來(lái)把物品放入背包，即(w3,w2,w1)=(10,15,18)。,貪心方法的數(shù)據(jù)選擇策略(2),先裝入物品3, x3=1, p3x3 =15，再裝入重量為10的物品2， pixi =15+24*10/15=31。 由剛才的方法可得這種情況下的總效益值為31，仍是一個(gè)次優(yōu)解，原因是容量在慢慢消耗的過(guò)程中，效益值卻沒(méi)有迅速的增加。,貪心方法的數(shù)據(jù)選擇策略(3),3. 采用在效益值的增長(zhǎng)速率和容量的消耗速率之間取得平衡的量度標(biāo)準(zhǔn)。即每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益。這就需使物品的裝入次序按pi/wi比值的非增次序來(lái)考慮。 這種策略下的量度是已裝入物品的累計(jì)效益值與所用容量之比。(p2/w2 , p3/w3 , p1/w1 )=(24/15,15/10,25/18)。先裝入重量為15的物品2，在裝入重量為5的物品3， pixi =24+15*5/10=31.5。此結(jié)果為最優(yōu)解。,背包問(wèn)題的貪心算法,Procedure GREEDY-KNAPSACK(P,W,M,X,n) real P(1:n),W(1:n),X(1:n),M,cu; integer i,n; X0;cuM for i1 to n do if W(i) cu then exit endif X(i)1;cucu-W(i) repeat if in then X(i)cu/W(i) endif End GREEDY-KNAPSACK,將解向量X初始化為0 Cu為背包的剩余容量,只放物品i 的一部分,預(yù)先將物品按pi/wi比值的非增次序排序,最優(yōu)解的證明,基本思想 把這個(gè)貪心解與任一最優(yōu)解相比較，如果這兩個(gè)解不同，就去找開(kāi)始不同的第一個(gè)xi，然后設(shè)法用貪心解的這個(gè)xi去代換最優(yōu)解的那個(gè)xi ，并證明最優(yōu)解在分量代換前后的總效益值無(wú)任何變化。反復(fù)進(jìn)行這種代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣，從而證明了貪心解就是最優(yōu)解。,最優(yōu)解的證明,定理3.1 如果p1/w1 p2/w2 pn/wn，則算法GREEDY-KNAPSACK對(duì)于給定的背包問(wèn)題實(shí)例生成一個(gè)最優(yōu)解。 證明：設(shè)X=(x1,xn )是GREEDY-KNAPSACK算法所生成的解。如果所有的xi 等于1，顯然這個(gè)解就是最優(yōu)解。否則，設(shè)j是使xj !=1的最小下標(biāo)。 由算法可知，對(duì)于1ij , xj =1; 對(duì)于jin , xj =0 ; 對(duì)于i=j ，0xj1。,最優(yōu)解的證明,假設(shè)X不是最優(yōu)解，則必定存在一個(gè)最優(yōu)解Y= (y1,yn)，使得piyi pixi 。假定wiyi =M，設(shè)k是使得 yk!=xk的最小下標(biāo)，則可以推出結(jié)論ykxk，則有wiyi M，這與Y是可行解矛盾。若yk=xk，與假設(shè)yk!=xk 矛盾，故只有ykxk成立。,若kj，若ykxk =0 ，則wiyi M,這與Y是可行解矛盾。因此，結(jié)論ykxk成立。 現(xiàn)在，假定把 yk 增加到 xk，那么必須從(yk+1,yn) 中減去同樣多的量，使得所用的總?cè)萘咳詾镸。這導(dǎo)致一個(gè)新的解Z = (z1,zn)，其中，zi= xi,1ik，并且wi ( yi-zi )= wk ( zk-yk) 。 因此，對(duì)于Z有 pizi=piyi +(zk-yk)pk-(yi-zi)pi = piyi +(zk-yk)wk pk /wk -(yi-zi)wipi/wi piyi +(zk-yk)wk -(yi-zi)wipk/wk = piyi,1in,1in,kin,1in,kin,1in,kin,1in,kin,所以pizi piyi 成立,最優(yōu)解的證明,若pizi piyi ，則Y不可能是最優(yōu)解。 若pizi =piyi ，同時(shí)Z=X，則X就是最優(yōu)解； 若pizi =piyi ， 但Z!=X，則重復(fù)上面的討論，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明了X也是最優(yōu)解。證畢。,課后思考題,找零錢(qián)問(wèn)題：一個(gè)小孩買(mǎi)了價(jià)值為33美分的糖，并將1美元的錢(qián)交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。使用貪心算法求解最優(yōu)結(jié)果。并證明找零錢(qián)問(wèn)題的貪心算法是否總能產(chǎn)生具有最少硬幣數(shù)的零錢(qián)。 考慮假設(shè)售貨員只有數(shù)目有限的25美分，10美分，5美分和1美分的硬幣，給出一種找零錢(qián)的貪心算法。,3.3 帶有限期的作業(yè)排序,問(wèn)題描述 假定只能在一臺(tái)機(jī)器上處理n個(gè)作業(yè)，每個(gè)作業(yè)均可在單位時(shí)間內(nèi)完成；又假定每個(gè)作業(yè)i都有一個(gè)截止期限di0(是整數(shù))，當(dāng)且僅當(dāng)作業(yè)i在它的期限截止之前被完成時(shí)，則獲得pj0的效益。 這個(gè)問(wèn)題的一個(gè)可行解是這n個(gè)作業(yè)的一個(gè)子集合J，J中的每個(gè)作業(yè)都能在各自的截止期限之前完成，可行解的效益值是J中這些作業(yè)的效益之和pj 。具有最大效益值的可行解就是最優(yōu)解。,帶有限期的作業(yè)排序?qū)嵗?例3.2 n=4，(p1,p2,p3,p4) = (100,10,15,20) 和(d1,d2,d3,d4)=(2,1,2,1)，這個(gè)問(wèn)題可能的可行解和他們的效益值為：,帶限期的作業(yè)排序算法,為了得到最優(yōu)解，應(yīng)制定如何選擇下一個(gè)作業(yè)的量度標(biāo)準(zhǔn)，利用貪心策略，使得所選擇的下一個(gè)作業(yè)在這種量度下達(dá)到最優(yōu)。 可把目標(biāo)函數(shù)pj作為量度，則下一個(gè)要計(jì)入的作業(yè)將是使得在滿(mǎn)足所產(chǎn)生的J是一個(gè)可行解的限制條件下使pj得到最大增加的作業(yè)，這一方法只要將各作業(yè)按效益pi降序來(lái)排列就可以了。,例3.2,求解 (p1，p2，p3，p4)(100,10,15,20) (d1，d2，d3，d4)(2,1,2,1) 首先令J=； 作業(yè)1具有當(dāng)前的最大效益值，且1是可行解，所以作業(yè)1計(jì)入J； 在剩下的作業(yè)中，作業(yè)4具有最大效益值，且1,4也是可行解，故作業(yè)4計(jì)入J，即J=1,4； 考慮1,3,4和1,2,4均不能構(gòu)成新的可行解，作業(yè)3和2將被舍棄。 故最后的J=1,4，最終效益值120（問(wèn)題的最優(yōu)解）,帶限期的作業(yè)排序算法,作業(yè)按p1 p2 pn的次序輸入： Procedure GREEDY_JOB(D,J,n) J1 for i2 to n do if Ji的所有作業(yè)都能在他們的截止期限前完成 then JJi endif repeat End GREEDY_JOB,定理3.2,對(duì)于作業(yè)排序問(wèn)題，用GREEDY_JOB算法所描述的貪心方法總是得到一個(gè)最優(yōu)解 證明如下:,定理3.2 證明,證明： 設(shè)J是由貪心方法所選擇的作業(yè)的集合；設(shè)I是一個(gè)最優(yōu)解的作業(yè)集合。則 IJ，否則J也是最優(yōu)解。 易知：I不是J的真子集，否則I就不是最優(yōu)解；J也不是I的真子集，這是由貪心法的工作方式所決定的。因此，存在作業(yè)a和b，使得a屬于J但不屬于I；b屬于I但不屬于J。 設(shè)a是使得a屬于J但不屬于I的一個(gè)具有最高效益的作業(yè)，對(duì)于在I中又不在J中的所有作業(yè)b，都有PaPb。這是因?yàn)槿鬚aPb，則貪心法會(huì)先于作業(yè)a考慮作業(yè)b并且把b計(jì)入到J中。,定理3.2 證明（續(xù)）,設(shè)SJ是J的可行調(diào)度表；SI是I的可行調(diào)度表。 對(duì)于每一個(gè)I和J的共同作業(yè)i，做以下調(diào)整：（tt，則可在SI中作類(lèi)似的調(diào)整。 用這種方法，就使得J和I中共有的所有作業(yè)在相同的時(shí)間被調(diào)度。,定理3.2 證明（續(xù)）,設(shè)作業(yè)a是使得a屬于J但不屬于I的一個(gè)具有最高效益的作業(yè)。,由于PaPb,顯然，轉(zhuǎn)換后I的效益值沒(méi)有減少。 重復(fù)應(yīng)用上述轉(zhuǎn)換，使I在不減少效益值的情況下轉(zhuǎn)換成J，因此，J也必定是最優(yōu)解。 證畢。,如何判斷J的可行性,方法一： 檢驗(yàn)J中作業(yè)所有可能的排列，對(duì)于任一種次序排列的作業(yè)排列，判斷這些作業(yè)是否能夠在其期限前完成，也即若J中有k個(gè)作業(yè)，則將要檢查k!個(gè)序列 方法二： 檢查J中作業(yè)的一個(gè)特定序列就可判斷J的可行性：對(duì)于所給出的一個(gè)排列i1i2ik,由于作業(yè)ij完成的最早時(shí)間是j，因此只要判斷出排列中的每個(gè)作業(yè)dijj，就可得知是一個(gè)允許的調(diào)度序列，從而J是一個(gè)可行解。反之，如果排列中有一個(gè)dijj,則將是一個(gè)行不通的調(diào)度序列，因?yàn)橹辽僮鳂I(yè)ij不能在其期限之前完成。 這一檢查過(guò)程可以只通過(guò)檢驗(yàn)J中作業(yè)的一種特殊的排列：按照作業(yè)期限的非降次序排列的作業(yè)序列即可完成。,可行解的確定,定理3.3: 設(shè)J是k個(gè)作業(yè)的集合，=i1,i2,ik是J中作業(yè)的一種排列，它使得di1di2dik。J是一個(gè)可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序而又不違反任何一個(gè)期限的情況來(lái)處理。,定理3.2 證明,證明： （充分性）若J中的作業(yè)可以按照的次序而又不違反任何一個(gè)期限的情況來(lái)處理，則J就是一個(gè)可行解。 （必要性）由于J可行，則必存在一種調(diào)度序列=r1r2rk，drjj，1j k。 假設(shè) ，則a是使得ra ia的最小下標(biāo)。,ra,rb= ia,ia,=i1,i2,ik , di1di2dik,=r1r2rk, drjj，1j k,rb = ia,ra,ia,連續(xù)使用這一方法，就可將轉(zhuǎn)換成且不違反任何一個(gè)期限。 定理得證。,帶限期序作業(yè)排序的處理,首先將作業(yè)1存入數(shù)組J中，然后處理作業(yè)2到作業(yè)n 假設(shè)已處理了i-1個(gè)作業(yè)，其中有k個(gè)作業(yè)存入了J(1),J(2)J(k)中，并且D(j(1)D(j(2)D(J(k)，現(xiàn)在開(kāi)始處理作業(yè)i 判斷Ji是否可行，只需找出按期限的非降次序插入作業(yè)i的位置，插入后有D(J(r) r。 找作業(yè)i可能的插入位置：將D(J(k),D(j(k-1),D(J(1)逐個(gè)與D(i)比較，直到找到位置r，它使得D(i)D(J(r),且D(i) r，則說(shuō)明r+1k共k-r個(gè)作業(yè)可以向后延遲一個(gè)單位時(shí)間來(lái)處理，可將這些作業(yè)向后移動(dòng)一個(gè)位置，然后把作業(yè)i插入到r+1位置，就可得解。,帶限期序作業(yè)排序的貪心算法,procedure JS(D,J,n,k) integer D(0:n),J(0:n),i,k,n,r D(0)J(0)0; k1;J(1)1; for i2 to n do rk; while D(J(r)D(i) and D(J(r) r do rr -1; repeat if D(J(r)D(i) and D(i)r then for ik to r+1 by 1 do J(i+1)J(i) repeat J(r+1)i ; kk+1； endif repeat End JS,找到插入位置,檢查插入的可能性,插入值,對(duì)于帶限期序作業(yè)排序的貪心算法JS有兩個(gè)賴(lài)以測(cè)量其復(fù)雜度的參數(shù)，即作業(yè)數(shù) n 和包含在解中的作業(yè)數(shù) s 。內(nèi)層的while循環(huán)至多循環(huán)k次，插入作業(yè) i 要執(zhí)行時(shí)間為O(k-r)，外層for循環(huán)共執(zhí)行(n-1)次。 如果s是k的終值，即s是最后所得解的作業(yè)數(shù)，則JS算法所需要的總時(shí)間為O(sn)。由于s n，所以JS算法的時(shí)間復(fù)雜度為O(n2)。,帶限期序作業(yè)排序的貪心算法,一種更快的作業(yè)排序算法,通過(guò)使用不相交集合的UNION與FIND算法以及使用一個(gè)不同的方法來(lái)確定部分解的可行性，可以將該問(wèn)題的計(jì)算時(shí)間由O(n2)降到接近于O(n)。 規(guī)則是：若還沒(méi)有給作業(yè)i分配處理時(shí)間，則分配給它時(shí)間片a-1,a,其中a應(yīng)盡量取大且時(shí)間片a-1,a是空的。若正被考慮的新作業(yè)不存在這樣的a，這個(gè)作業(yè)就不能計(jì)入解中。,一種更快的作業(yè)排序算法(續(xù)),例：設(shè)n=5,(p1,p5)=(20,15,10,5,1)和（d1,d5)=(2,2,1,3,3),作業(yè)排序的一個(gè)更快算法,procedure FJS(D,n,b,J,k) /假定p1p2pn , b=minn,maxD(i) Integer b,D(n),J(n),F(0:b),P(0:b) for i=0 to n do F(i)=i; P(i)=-1 repeat k=0 for i=1 to n do j=FIND(min(n,D(i) if F(j)0 then k=k+1;J(k)=i L=FIND(F(j)-1); call UNION(L, j) F(j)=F(L) endif repeat end FJS,查看實(shí)例,課后思考題,0/1背包問(wèn)題：在雜貨店比賽中你獲得了第一名，獎(jiǎng)品是一車(chē)免費(fèi)雜貨。店中有n 種不同的貨物。規(guī)定從每種貨物中最多只能拿一件，車(chē)子的容量為c，物品i 需占用wi 的空間，價(jià)值為pi。你的目標(biāo)是使車(chē)中裝載的物品價(jià)值最大。當(dāng)然，所裝貨物不能超過(guò)車(chē)的容量，且同一種物品不得拿走多件。如何選擇量度標(biāo)準(zhǔn)才能找到最優(yōu)解？ 若n=2, w=100,10,10,p=20,15,15,c=105。證明利用價(jià)值貪心準(zhǔn)則時(shí)，所得結(jié)果是否是最優(yōu)解？,3.4 最優(yōu)歸并模式,第二章中學(xué)習(xí)了如何用分治法將兩個(gè)分別包含n個(gè)和m個(gè)記錄的已分類(lèi)文件在O(n+m)時(shí)間內(nèi)歸并成一個(gè)包含(n+m)個(gè)記錄的分類(lèi)文件。下面是兩種將4個(gè)文件進(jìn)行歸并的方法。不同的配對(duì)法要求不同的計(jì)算時(shí)間。,什么是歸并模式,給出n個(gè)文件，則由許多種把這些文件成對(duì)地歸并成一個(gè)單一分類(lèi)文件的方法。 不同的配對(duì)方法要求不同的計(jì)算時(shí)間 問(wèn)題的關(guān)鍵是：確定一個(gè)把n個(gè)已分類(lèi)文件歸并在一起的最優(yōu)方法（即需要最少的比較的方法）,X1，X2和X3是各自有30個(gè)記錄、20個(gè)記錄和10個(gè)記錄的三個(gè)已分類(lèi)文件。 歸并X1和X2需要50次記錄移動(dòng)，再與X3歸并則還要60次移動(dòng)，其所需要的記錄移動(dòng)次數(shù)總量為110。 如果首先歸并X2和X3，需要30次移動(dòng)，然后再歸并X1，需要60次移動(dòng)，則所要移動(dòng)記錄的總量為90。 因此，第二個(gè)歸并模式比第一個(gè)要好。,例3.5,最優(yōu)歸并模式的實(shí)現(xiàn),由于歸并一個(gè)具有n個(gè)記錄的文件和一個(gè)具有m個(gè)記錄的文件可能需要m+n次記錄移動(dòng)，因此對(duì)于量度標(biāo)準(zhǔn)的一種很明顯的選擇是：每一步都?xì)w并尺寸比較小的兩個(gè)文件。 例如有五個(gè)文件長(zhǎng)度分別是(F1, F2, ,F5)=(20,30,10,5,30),二元?dú)w并樹(shù),二路歸并模式,上面所描述的歸并模式稱(chēng)為二路歸并模式。二路歸并模式可以用二元?dú)w并樹(shù)來(lái)表示。 二元?dú)w并樹(shù)中葉結(jié)點(diǎn)被畫(huà)成方塊，表示五個(gè)已知的文件。這些結(jié)點(diǎn)稱(chēng)為外部結(jié)點(diǎn)。 剩下的結(jié)點(diǎn)被畫(huà)成圓圈，稱(chēng)為內(nèi)部結(jié)點(diǎn)。每個(gè)內(nèi)部結(jié)點(diǎn)恰好有兩個(gè)兒子，表示它是將兩個(gè)兒子所表示的文件歸并在一起而得到的文件。 每個(gè)結(jié)點(diǎn)中的數(shù)字都是那個(gè)結(jié)點(diǎn)所表示文件的長(zhǎng)度（即記錄數(shù)）。,最優(yōu)歸并模式的實(shí)現(xiàn),帶權(quán)外部路徑長(zhǎng)度 如果di表示從根到代表文件Fi的外部節(jié)點(diǎn)的距離，qi表示Fi的長(zhǎng)度，則這棵二元?dú)w并樹(shù)的記錄移動(dòng)總量是： diqi 這個(gè)和數(shù)叫做這棵樹(shù)的帶權(quán)外部路徑長(zhǎng)度 一個(gè)最優(yōu)二路歸并模式與一棵具有最小外部路徑的二元樹(shù)相對(duì)應(yīng)。,i=1,n,二元?dú)w并樹(shù)算法,二元?dú)w并樹(shù)算法把n個(gè)樹(shù)的表L作為輸入。樹(shù)中的每一個(gè)結(jié)點(diǎn)有三個(gè)信息段(LCHILD,RCHILD,WEIGHT)。 起初，L中的每一棵樹(shù)正好有一個(gè)結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)是一個(gè)外部結(jié)點(diǎn)，而且其LCHILD和RCHILD信息段為0，而WEIGHT是要?dú)w并的n個(gè)文件之一的長(zhǎng)度。 算法運(yùn)行期間，對(duì)于L中的任何一棵具有根結(jié)點(diǎn)T的樹(shù)， WEIGHT(T)表示要?dú)w并的文件的長(zhǎng)度。 WEIGHT(T)=樹(shù)T中外部結(jié)點(diǎn)的長(zhǎng)度和。,二元?dú)w并樹(shù)算法,procedure TREE(L,n) for i1 to n-1 do call GETNODE(T) LCHILD(T)LEAST(L) RCHILD(T)LEAST(L) WEIGHT(T)WEIGHT(LCHILD(T) +WEIGHT(RCHILD(T) call INSERT(L,T) repeat return (LEAST(L) End TREE,每個(gè)節(jié)點(diǎn)有三個(gè)信息：LCHILD,RCHILD,WEIGHT,構(gòu)造一個(gè)新結(jié)點(diǎn),找出L中一棵具有最小WEIGHT的樹(shù)，并刪除,把根為T(mén)的樹(shù)插入到表L中,二元?dú)w并樹(shù)算法的實(shí)例,例：L最初有6個(gè)文件，長(zhǎng)度分別為： 2 , 3 , 5 , 7 , 9 , 13。,2,3,5,5,10,13,23,7,9,16,39,二元?dú)w并樹(shù)算法的計(jì)算時(shí)間,時(shí)間分析： 1) 循環(huán)體：n-1次 2) L以有序序列表示 LEAST(L): (1) INSERT(L,T): (n) 總時(shí)間： (n2) 3) L以min-堆表示 LEAST(L): (logn) INSERT(L,T): (logn) 總時(shí)間： (nlogn),最優(yōu)解證明,定理3.4 若L是最初包含n（1）個(gè)單個(gè)結(jié)點(diǎn)的樹(shù)，這些樹(shù)有WEIGHT值為(q1,q2,qn)，則算法TREE對(duì)于具有這些長(zhǎng)度的n個(gè)文件生成一棵最優(yōu)的二元?dú)w并樹(shù)。,最優(yōu)解的證明,證明：用歸納法證明 當(dāng)n=1時(shí)，返回一棵沒(méi)有內(nèi)部結(jié)點(diǎn)的樹(shù)。定理得證。 假定算法對(duì)所有的(q1,q2,qm)，1mn,生成一棵最優(yōu)二元?dú)w并樹(shù)。 對(duì)于n,假定q1q2qn,則q1和q2將是在for循環(huán)的第一次迭代中首先選出的具有最小WEIGHT值的兩棵樹(shù)。如圖所示，T是由這樣的兩棵樹(shù)構(gòu)成的子樹(shù)：,最優(yōu)解的證明, 設(shè)T是一棵對(duì)于(q1,q2,qn)的最優(yōu)二元?dú)w并樹(shù)。 設(shè)P是T中距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。 若P的兩棵子樹(shù)不是q1和q2，則用q1和q2代換P當(dāng)前的子樹(shù)而不會(huì)增加T的帶權(quán)外部路徑長(zhǎng)度。 故，T應(yīng)是最優(yōu)歸并樹(shù)中的子樹(shù)。 在T中用一個(gè)權(quán)值為q1q2的外部結(jié)點(diǎn)代換T，得到的是一棵關(guān)于(q1q2,qn)最優(yōu)歸并樹(shù)T”。 而由歸納假設(shè)，在用權(quán)值為q1q2的外部結(jié)點(diǎn)代換了T之后，過(guò)程TREE將針對(duì)(q1q2,qn)得到一棵最優(yōu)歸并樹(shù)。 將T帶入該樹(shù)，根據(jù)以上討論，將得到關(guān)于(q1,q2,qn)的最優(yōu)歸并樹(shù)。故，TREE生成一棵關(guān)于(q1,q2,qn)的最優(yōu)歸并樹(shù)。,3.5 最小生成樹(shù),1. 問(wèn)題的描述 生成樹(shù)：設(shè)G=(V,E)是一個(gè)無(wú)向連通圖。如果G的生 成子圖T=(V,E)是一棵樹(shù)，則稱(chēng)T是G的一棵 生成樹(shù)(spanning tree) 2. 最小生成樹(shù): 貪心策略 度量標(biāo)準(zhǔn)：選擇能使迄今為止所計(jì)入的邊的成本和有最小 增加的那條邊。 Prim算法 Kruskal算法,Prim算法,策略： 使得迄今所選擇的邊的集合A構(gòu)成一棵樹(shù)；對(duì)將要計(jì)入到A中的下一條邊(u,v)，應(yīng)是E中一條當(dāng)前不在A中且使得A(u,v)也是一棵樹(shù)的最小成本邊。,Prim算法,Kruskal算法,策略： （連通）圖的邊按成本的非降次序排列，下一條計(jì)入生成樹(shù)T中的邊是還沒(méi)有計(jì)入的邊中具有最小成本、且和T中現(xiàn)有的邊不會(huì)構(gòu)成環(huán)路的邊。,Kruskal算法,3.6 單源點(diǎn)最短路徑,什么是單源點(diǎn)最短路徑 已知一個(gè)n 結(jié)點(diǎn)的有向圖G=(V,E)和邊的權(quán)函數(shù)c(e)，求由G中某指定結(jié)點(diǎn)v0到其他各個(gè)結(jié)點(diǎn)的最短路徑。,v0,v2,v1,v3,v4,v5,20,45,50,10,15,15,20,10,35,30,3,貪心策略求解,1) 度量標(biāo)準(zhǔn) 量度的選擇：迄今已生成的所有路徑長(zhǎng)度之和為使之達(dá)到最小，其中任意一條路徑都應(yīng)具有最小長(zhǎng)度： 假定已經(jīng)構(gòu)造了i條最短路徑，則下一條要構(gòu)造的路徑應(yīng)是下一條最短的路徑。 處理規(guī)則：按照路徑長(zhǎng)度的非降次序依次生成從結(jié)點(diǎn)v0到其它各結(jié)點(diǎn)的最短路徑。 例： v0v2 v0v2v3 v0v2v3v1 v0v4,貪心策略求解,2) 貪心算法 設(shè)S是已經(jīng)對(duì)其生成了最短路徑的結(jié)點(diǎn)集合（包括v0)。 對(duì)于當(dāng)前不在S中的結(jié)點(diǎn)w，記DIST(w)是從v0開(kāi)始，只經(jīng)過(guò)S中的結(jié)點(diǎn)而在w結(jié)束的那條最短路徑的長(zhǎng)度。 則有，,貪心策略求解, 如果下一條最短路徑是到結(jié)點(diǎn)u，則這條路徑是從結(jié)點(diǎn)v0出發(fā)在u處終止，且只經(jīng)過(guò)那些在S中的結(jié)點(diǎn),即由v0至u的這條最短路徑上的所有中間結(jié)點(diǎn)都是S中的結(jié)點(diǎn): 設(shè)w是這條路徑上的任意中間結(jié)點(diǎn)，則從v0到u的路徑也包含了一條從v0到w的路徑，且其長(zhǎng)度小于從v0到u的路徑長(zhǎng)度。 v0,s1,s2,w,sm-1,u 均在S中 根據(jù)生成規(guī)則：最短路徑是按照路徑長(zhǎng)度的非降次序生成的，因此從v0到w的最短路徑應(yīng)該已經(jīng)生成。從而w也應(yīng)該在S中。 故,不存在不在S中