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

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