算法設(shè)計與分析王佳04貪心算法

1、第六章 貪心算法,主要內(nèi)容,6.1 一般方法,6.2 背包問題,6.3 帶時限的作業(yè)排序,6.4 最佳歸并模式,6.5 最小生成樹,6.7 多機(jī)調(diào)度問題,6.6單源點最短路徑,引言,找零錢問題 貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似,最優(yōu)化問題（optimization pro

2、blems）是指這樣一類問題，問題給定某些約束條件（constraint），滿足這些約束條件的問題解稱為可行解（feasible solution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數(shù)值函數(shù)，稱為目標(biāo)函數(shù)（objective function），使目標(biāo)函數(shù)取最大（或最小）值的可行解稱為最優(yōu)解（optimal solution,貪心法是通過分步?jīng)Q策（stepwise decision）的方法來求解問題的。 貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)（optimization criterion）。 在根據(jù)最優(yōu)量度標(biāo)準(zhǔn)選擇分量的過程中，還需要使用一

3、個可行解判定函數(shù)。 貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當(dāng)前看似最佳選擇，必須進(jìn)一步證明該算法最終導(dǎo)致問題的一個整體最優(yōu)解,Greedy算法的基本思想 求解最優(yōu)化問題的算法包含一系列步驟 每一步都有一組選擇 作出在當(dāng)前看來最好的選擇 希望通過作出局部優(yōu)化選擇達(dá)到全局優(yōu)化選擇 Greedy算法不一定總產(chǎn)生優(yōu)化解 Greedy算法是否產(chǎn)生優(yōu)化解，需嚴(yán)格證明 Greedy算法產(chǎn)生優(yōu)化解的條件 Greedy-choice-property Optimal substructure,Greedy算法的基本概念,Greedy選擇性,Greedy選擇性 若一個優(yōu)化問題的全局優(yōu)化解可以通過 局

4、部優(yōu)化選擇得到，則該問題稱為具有 Greedy選擇性. 一個問題是否具有Greedy選擇性需證明,若一個優(yōu)化問題的優(yōu)化解包含它的 子問題的優(yōu)化解，則稱其具有優(yōu)化 子結(jié)構(gòu),優(yōu)化子結(jié)構(gòu),與動態(tài)規(guī)劃方法的比較,動態(tài)規(guī)劃方法可用的條件 優(yōu)化子結(jié)構(gòu) 子問題重疊性 子問題空間小 Greedy方法可用的條件 優(yōu)化子結(jié)構(gòu) Greedy選擇性 可用Greedy方法時，動態(tài)規(guī)劃方法可能不適用 可用動態(tài)規(guī)劃方法時，Greedy方法可能不適用,證明算法所求解的問題具有優(yōu)化子結(jié)構(gòu) 證明算法所求解的問題具有Greedy選擇性 證明算法確實按照Greedy選擇性進(jìn)行局部優(yōu)化選擇,Greedy算法正確性證明方法,程序61】貪

5、心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;in;i+) SType x=Select(a); if (Feasiable(solution,x) solution=Union(solution,x); return solution;,6.2 背包問題,6.2.1 問題描述,已知一個載重為M的背包和n件物品，第i件物品的重量為 wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi0，pi0，0in。所謂背包問題是指求一種最佳裝載方案，使得收益最大。所以，背包問題是現(xiàn)實世界一個常見的

6、最優(yōu)化問題。 兩類背包問題:如果每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為 0/1背包問題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問題或簡稱背包問題,6.2.2 貪心法求解,背包問題 背包問題的解可以表示成一個n-元組：X=(x0,x1,xn1)，0 xi1，0in，每個xi是第i件物品裝入背包中的部分。 判定可行解的約束條件是,背包問題的最優(yōu)解必須使下列目標(biāo)函數(shù)取最大值,例61 設(shè)有載重能力M=20的背包，3件物品的重量為:（w0,w1,w2）=(18,15,10)，物品裝入背包的收益為：（p0,p1,p2）=(25,24,15,2. 貪心策略求

7、解 度量標(biāo)準(zhǔn)的選擇：三種不同的選擇 1）以目標(biāo)函數(shù)作為度量 即，每裝入一件物品，就使背包獲得最大可能的效益增量。 該度量標(biāo)準(zhǔn)下的處理規(guī)則是： 按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包：如果該物品的一部分不滿足獲得最大效益增量的度量標(biāo)準(zhǔn)，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。 如：若M=2,背包外還剩兩件物品i,j，且有(pi 4，wi4) 和(pj 3，wj2)，則下一步應(yīng)選擇j而非i放入背包： pi/2 = 2 pj 3,實例分析（例3.1) p1p2 p3 首先將物品1放入背包，此時x11，背包獲

8、得p125的效益增量，同時背包容量減少w118個單位，剩余空間M=2。 其次考慮物品2和3。就M=2而言有，只能選擇物品2或3的一部分裝入背包。 物品2： 若 x22/15， 則 p2 x216/53.1 物品3： 若 x32/10， 則 p3 x33 為使背包的效益有最大的增量，應(yīng)選擇物品2的2/15裝包，即 x22/15 最后，背包裝滿， M=0，物品3不裝包，即x30 。 背包最終可以獲得效益值 x1 p1 x2 p2x3 p3 28.2 (次優(yōu)解,非問題的最優(yōu)解,2）以容量作為度量標(biāo)準(zhǔn) 以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉

9、了，從而不能裝入“更多”的物品。 改進(jìn)：讓背包容量盡可能慢地消耗，從而可以盡量裝入“較多”的物品。 即，新的標(biāo)準(zhǔn)是：以容量作為度量 該度量標(biāo)準(zhǔn)下的處理規(guī)則： 按物品重量的非降次序?qū)⑽锲费b入到背包； 如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包,實例分析（例3.1) w3w2 w1 首先將物品3放入背包，此時x31，背包容量減少w310個單位，還剩余空間M=10。同時，背包獲得p315的效益增量。 其次考慮物品2。就M=10而言有，也只能選擇物品2的一部分裝入背包。下一步將放入物品2的10/15裝包，即 x210/152/3 最后，背包裝滿M=0，物品1將不能裝入背包，故 x10 。 背包

10、最終可以獲得效益值 x1 p1 x2 p2x3 p3 31 (次優(yōu)解,非問題的最優(yōu)解) 存在的問題：效益值沒有得到“最大程度”的增加,3）最優(yōu)的度量標(biāo)準(zhǔn) 影響背包效益值得因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前最大的單位效益。 在這種策略下的量度是：已裝入的物品的累計效益值與所用容量之比。 故，新的量度標(biāo)準(zhǔn)是：每次裝入要使累計效益值與所用容量的比值有最多的增加（首次裝入）和最小的減?。ㄆ浜蟮难b入）。 此時，將按照物品的單位效益值：pi/wi 比值的非

11、增次序考慮,實例分析（例3.1) p1/w1p3/w3 p2/w2 首先，將物品2放入背包，此時x21，背包容量減少w215 個單位，還剩余空間M=5。同時，背包獲得p224的 效益增量。 其次，在剩下的物品1和3中，應(yīng)選擇物品3,且就M=5而言有， 只能放入物品3的一部分到背包中 。即 x35/101/2 最后，背包裝滿M=0，物品1將不能裝入背包，故x10 。 最終可以獲得的背包效益值 x1 p1 x2 p2x3 p3 31.5 (最優(yōu)解,3. 背包問題的貪心求解算法,算法4.2 背包問題的貪心算法 procedure GREEDYKNAPSACK(P,W,M,X,n) /P(1:n)和W

12、(1:n)分別含有按P(i)/W(i)P(i1)/W(i1)排序的n 件物品的效益值和重量。M是背包的容量大小，而X(1:n)是解 向量/ real P(1:n), W(1:n), X(1:n), M, cu; integer I,n X0 /將解向量初始化為0/ cuM /cu是背包的剩余容量/ for i1 to n do if W(i) cu then exit endif X(i) 1 cu cu-W(i) repeat if in then X(i) cu/W(i) endif end GREEDY-KNAPSACK,4. 最優(yōu)解的證明,即證明：由第三種策略所得到的貪心解是問題的最優(yōu)

13、解。 最優(yōu)解的含義：在滿足約束條件的情況下，使目標(biāo)函數(shù)取極（大或小）值的可行解。 貪心解是可行解，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值,證明的基本思想： 將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 如果這兩個解相同，則顯然貪心解就是最優(yōu)解。 如果這兩個解不同，就設(shè)法去找兩者開始不同的第一個分量位置i，然后設(shè)法用貪心解的這個xi去替換最優(yōu)解對應(yīng)的分量 ，并證明最優(yōu)解在分量代換前后總的效益值沒有任何變化(且不違反約束條件)。 然后比較二者。若還不同，則反復(fù)進(jìn)行代換，直到代換后產(chǎn)生的“最優(yōu)解”與貪心解完全一樣。 在上述代換中，最優(yōu)解的效益值沒有任何損失，從而證明貪心解的 效益值與代換前后最優(yōu)解的效

14、益值相同。即，貪心解如同最優(yōu)解一 樣可取得目標(biāo)函數(shù)的最大/最小值。 從而得證：該貪心解即是問題的最優(yōu)解,定理6.1 如果p1/w1 p2/w2 pn/wn,則算法GREEDY-KNAPSACK對于給定的背包問題實例生成一個最優(yōu)解。 證明： 設(shè)X=(x1, x2, , xn)是GREEDY-KNAPSACK所生成的貪心解。 如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則， 設(shè)j是使xi1的最小下標(biāo)。由算法的執(zhí)行過程可知， xi=1 1ij, 0 xj 1 xi=0 jin,假設(shè)Y是問題的最優(yōu)解：Y=(y1, y2, , yn) 且有： 若X Y，則X就是最優(yōu)解。否則， X和Y至少在1個分

15、量上存在不同。 設(shè)k是使得yk xk的最小下標(biāo)，則有yk xk?？煞忠韵虑闆r說明： a) 若kj，則xk=1。因為yk xk,從而有yk xk b) 若k=j，由于 ，且對1ij，有yi=xi=1,而對jin,有xi0；故此時若ykxk，則將有 ，與Y是可行解相矛盾。而yk xk,所以yk xk c) 若kj，則 ，不能成立,在Y中作以下調(diào)整：將yk增加到xk，因為ykxk,為保持解的可行性，必須從(yk+1,yn)中減去同樣多的量。設(shè)調(diào)整后的解為Z=(z1, z2, , zn)，其中zixi，1ik，且有： Z的效益值有,差值0,由以上分析得， 若 ，則Y將不是最優(yōu)解； 若 ，則或者Z=X，

16、則X就是最優(yōu)解； 或者ZX，則重復(fù)以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解,程序62】背包問題的貪心算法 template class Knapsack public: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n;,template void Knapsack:GreedyKnapsack(float* x) /前置條件：wi已按pi/wi的非增次序排列 float u=m; fo

17、r (int i=0;iu) break; xi=1.0; u=u-wi; if (i=n) xi=u/wi;,6.3 帶時限的作業(yè)排序,6.3.1 問題描述,設(shè)有一個單機(jī)系統(tǒng)、無其它資源限制且每個作業(yè)運行相等時間，不妨假定每個作業(yè)運行1個單位時間?，F(xiàn)有n個作業(yè)，每個作業(yè)都有一個截止期限di0，di為整數(shù)。如果作業(yè)能夠在截止期限之內(nèi)完成，可獲得pi0的收益。問題要求得到一種作業(yè)調(diào)度方案，該方案給出作業(yè)的一個子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調(diào)度作業(yè)運行，該子集中的每個作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說這種作業(yè)調(diào)度是最優(yōu)的,6.3.2 貪心法求解,例62 設(shè)有4個作

18、業(yè)，每個作業(yè)的時限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27,6.3 帶有限期的作業(yè)排序,1. 問題描述 假定在一臺資源無約束的機(jī)器上處理n個作業(yè)，每個作業(yè)均可在單位時間內(nèi)完成；同時每個作業(yè)i都有一個截至期限di0,當(dāng)且僅當(dāng)作業(yè)i在其截至期限以前被完成時，則獲得pi0的效益。 問題：求這n個作業(yè)的一個子集J，其中的所有作業(yè)都可在其截至期限內(nèi)完成。J是問題的一個可行解。 可行解J中的 所有作業(yè)的效益之和是 ，具有最大效益值之和的可行解是該問題的最優(yōu)解,分析： 目標(biāo)函數(shù)： 約束條件：所有的作業(yè)都應(yīng)在其期限之前完成 如果所有的作業(yè)都

19、能在其期限之內(nèi)完成則顯然可以獲得當(dāng)前最大效益值； 否則，將有作業(yè)無法完成決策應(yīng)該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值,例6.2 n=4，(p1，p2，p3，p4)(100,10,15,20) (d1，d2，d3，d4)(2,1,2,1)。 可行解如下表所示： 問題的最優(yōu)解是。所允許的處理次序是：先處理作業(yè)4再處理作業(yè)1,1. 帶有限期的作業(yè)排序算法,1) 度量標(biāo)準(zhǔn)的選擇 以目標(biāo)函數(shù) 作為量度。 量度標(biāo)準(zhǔn)：下一個要計入的作業(yè)將是使得在滿足所產(chǎn)生的J是 一個可行解的限制條件下讓 得到最大增加的 作業(yè)。 處理規(guī)則： 按pi的非增次序來考慮這些作業(yè)； 同時因受作業(yè)期限的限制，必須為作業(yè)安排合理的處理順

20、序,例：例6.2求解 首先令J=, p1p4 p3 p2 作業(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，加工順序是：4，1。 最終效益值120（問題的最優(yōu)解,2)作業(yè)排序算法的概略描述 算法6.3 procedure GREEDY-JOB(D,J,n) /作業(yè)按p1p2pn的次序輸入，它們的期限值D(i)1, 1in,n1。J是在它們的截止期限前完成的作業(yè)的集合

21、/ J1 /用作業(yè)序號代表作業(yè)/ for i2 to n do if Ji的所有作業(yè)能在它們的截止期限前完成 then JJi endif repeat end GREEDY-JOB,2. 最優(yōu)解證明,定理6.2 算法6.3對于作業(yè)排序問題的解是問題的一個最優(yōu)解 證明： 設(shè)J是由算法6.3所得的作業(yè)集合貪心解， I是一個最優(yōu)解的作業(yè)集合。 若I=J，則J就是最優(yōu)解；否則 ，則至少存在兩個作業(yè)a和b，使得aJ且 ,bI且 。（為什么） 并設(shè)a是這樣的一個具有最高效益值的作業(yè) (由算法的處理規(guī)則可得：對于在I中而不在J中的作業(yè)所有b，有：papb,設(shè)SJ和SI分別是J和I的可行的調(diào)度表。因為J和I

22、都是可行解，故這樣的調(diào)度表一定存在； 設(shè)i是既屬于J又屬于I地一個作業(yè)，并設(shè)i在調(diào)度表SJ中的調(diào)度時刻是t，t+1，而在SI中的調(diào)度時刻是t，t+1。 在SJ和SI中作如下調(diào)整： 若tt，則將SJ中在t，t+1時刻調(diào)度的那個作業(yè)（如果有的話）與i相交換。如果J中在t，t+1時刻沒有作業(yè)調(diào)度，則直接將i移到t，t+1調(diào)度。新的調(diào)度表也是可行的,若tt，則在SI中作類似的調(diào)換，即將SI中在t，t+1時刻調(diào)度的那個作業(yè)（如果有的話）與i相交換。如果I中在t，t+1時刻沒有作業(yè)調(diào)度，則直接將i移到t，t+1調(diào)度。同樣，新的調(diào)度表也是可行的。 對J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為

23、SJ和SI，則在SJ和SI中J和I中所有的共有作業(yè)將在相同時間被調(diào)度,設(shè)a在SJ中的調(diào)度時刻是ta, ta+1， b是SI中該時刻調(diào)度的作業(yè)，則有papb（為什么？）。 在SI中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合I=（I-b）a的 一個可行的調(diào)度表，且I的效益值不小于I的效益值。而I中比I少了一個與J不同的作業(yè)。 重復(fù)上述的轉(zhuǎn)換，可使I在不減效益值的情況下轉(zhuǎn)換成J。從而J至少有和I一樣的效益值。所以J也是最優(yōu)解。 證畢,3. 如何判斷J的可行性,方法一：枚舉法，檢驗J中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成 若J中有k個作業(yè)，則將要檢查

24、k!個序列 判斷策略： 對于一個給定作業(yè)處理序列i1i2ik,由于作業(yè)ij完成的最早時間是j，因此只要判斷出排列中的每個作業(yè)的期限有dijj，就可得知是一個允許的調(diào)度序列，從而J是一可行解。 反之，如果排列中有一個作業(yè)有dijj,則將是一個行不通的調(diào)度序列，因為至少作業(yè)ij不能在其期限之前完成,方法二：檢查J中作業(yè)的一個特定序列就可判斷J的可行性： 這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列,定理6.3 設(shè)J是k個作業(yè)的集合，i1i2ik是J中作業(yè)的一種排列，它使得di1di2dik。則 J是一個可行解，當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序而又不違反任何一個期限的情況來處理,證明： 如果J

25、中的作業(yè)可以按照的次序而又不違反任何一個作業(yè)期限的情況來處理，則J是一個可行解 現(xiàn)證若J是一個可行解， 是否代表一個可行的調(diào)度序列？ J是可行解 必存在一可行的調(diào)度序列r1r2rk，使得drjj, 1jk。 若，則即是可行的調(diào)度序列。否則， ，令a是使得raia的最小下標(biāo)（如下圖,i1 i2 ia ic ik r1 r2 ra rb rk,設(shè)rb=ia。則有： ba 且 dradrb 故，在中調(diào)換ra與rb，所得的新序列 s1s2sk的處理次序不違反任何一個期限，而中位置a及a之前的作業(yè)均與相同。 重復(fù)上述過程，則可將轉(zhuǎn)換成且不違反任何一個期限，故是一個可行的調(diào)度序列 故定理得證,4. 帶有限

26、期的作業(yè)排序算法的實現(xiàn),對當(dāng)前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠?qū)⒆鳂I(yè)j合并到當(dāng)前部分解J中： 如果有合適的插入位置，則插入到序列中，形成新的可行解序列。 否則，舍棄該作業(yè)。 具體如下： 假設(shè)n個作業(yè)已經(jīng)按照效益值從大到小的次序，即p1p2pn的順序排列好，每個作業(yè)可以在單位時間內(nèi)完成，并具有相應(yīng)的時間期限di；且至少有一個單位時間可以執(zhí)行作業(yè) 首先，將作業(yè)1計入部分解J中，此時J是可行的； 然后，依次考慮作業(yè)2到n。假設(shè)已經(jīng)處理了i-1個作業(yè)，其中有k個作業(yè)計入了部分解J中：J(1),J(2)

27、,J(k)，且有 D(J(1)D(J(2)D(J(k,對當(dāng)前正在考慮的作業(yè)i,將D(i)依次和D(J(k), D(J(k-1),，D(J(1)相比較。若 1）找到位置q：使得 D(i) D(J(l)，qlk，且 D(J(q) D(i) q D(i) 此時，若D(J(l)l, qlk,即q位置之后的所有作業(yè)均可 推遲一個單位時間執(zhí)行，而又不違反各自的執(zhí)行期限。 執(zhí)行“移位”處理：將q位置之后的所有作業(yè)后移一位，將作 業(yè)i插入到位置q1處，從而得到一個包含k+1個作業(yè)的新的可行解。 2）若找不到這樣的位置q，作業(yè)i將被舍棄。 對i之后的其它作業(yè)重復(fù)上述過程，直到n個作業(yè)處理完畢。 最后J中所包含的

28、作業(yè)集合是此時算法的貪心解，根據(jù)定理3.2,也是問題的最優(yōu)解,算法6.4 帶有限期和效益的單位時間的作業(yè)排序貪心算法 procedure JS(D,J,n,k) /n1。作業(yè)已按p1p2pn的順序排序。 D(1),D(n)是期限值, J(i)是最優(yōu)解中的第i個作 業(yè)，1ik。終止時， D(J(i)D(J(i1)， 1ik/ integer D(0:n),J(0:n),i,k,n,r D(0)J(0)0 /初始化/ k1;J(1)1 /計入作業(yè)1/ for i2 to n do /按p的非增次序考慮作業(yè)i。找i的插入位置并檢查可行性/ rk while D(J(r)D(i) and D(J(r)

29、 r do / D(J(r) r/ rr-1 /這樣的r有D(J(r) r/ repeat If D(J(r)D(i) and D(i)r then /把i插入到J中/ for ik to r+1 by -1 do J(i+1) J(i) /將插入點的作業(yè)后移一位/ repeat J(r+1) i; kk+1 /將i計入J中/ endif repeat end JS,另一退出條件是D(J(r)D(i) 而 D(J(r) =r,計算時間分析 for i2 to n do 將循環(huán)n-1次 rk while D(J(r)D(i) and D(J(r) r do 至多循環(huán)k次， k是當(dāng)前計入J中的作業(yè)

30、數(shù) 1kn-1 rr-1 repeat If D(J(r)D(i) and D(i)r then for ik to r+1 by -1 do 循環(huán)k-r次，r是插入點之前的位置 最壞情況下循環(huán)k次，插入到最頭部 J(i+1) J(i) repeat J(r+1) I;kk+1 endif repeat 設(shè)s是最終計入J中的作業(yè)數(shù)，則算法JS所需要的總時間是O(sn)。sn，故 最壞情況：TJS = (n2)，特例情況：pi=di=n-i+1,1in 最好情況：TJS = (n)，特例情況：pi=n-i+1, di=i,1in,6. 一種“更快”的作業(yè)排序問題 判定作業(yè)i可行的另一種方法： 對

31、于作業(yè)i，若還沒有給i分配處理時間，則分配給它時間片-1,，其中是盡量取大且-1,為空的時間片。 即：盡量推遲作業(yè)i的處理時間。這樣在安排作業(yè)處理次序時不必每有一個作業(yè)加入就需移動J中已有的作業(yè)。 如果不存在這樣的時間片，作業(yè)i被舍棄。 （如何按照該方法改進(jìn)算法？） 使用不相交集合的 UNION和FIND算法（見數(shù)據(jù)結(jié)構(gòu)相關(guān)章節(jié)），可以將JS的計算時間降低到數(shù)量級接近(n)。 （略,程序63】帶時限作業(yè)排序的貪心算法 void GreedyJob(int d, Set X, int n) /前置條件：p0p1,pn-1 X=0; for (int i=1;in;i+) if ( 集合 Xi 中

32、作業(yè)都能在給定時限內(nèi)完成) X=Xi;,6.3.3 算法正確性,定理62 程序62的貪心算法對于帶時限作業(yè)排序問題將得到最優(yōu)解,6.3.4 可行性判定,定理63 X=（x0,x1,xk）是k個作業(yè)的集合，=（0, 1,k）是X 的一種特定排列，它使得，其中，是作業(yè)j的時限。X是一個可行解當(dāng)且僅當(dāng)X中的作業(yè)能夠按次序調(diào)度而不會有作業(yè)超期,6.3.5 作業(yè)排序貪心算法,定理63提供了一種高效的可行解判定方法。使得在按最優(yōu)量度標(biāo)準(zhǔn)，即按作業(yè)收益的非增次序選擇下一個作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X,程序64】帶時限的作業(yè)排序程序 int JS(int *d, int *x,

33、 int n) /設(shè)p0p1pn-1 int k=0; x0=0; for (int j=1;j=0,6.3.6 一種改進(jìn)算法,本小節(jié)將介紹一種帶時限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時間從(n2)減少到接近O(n,例63 設(shè)n=5個作業(yè)， 作業(yè)的時限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益為: (p0,p1,p2,p3,p4)=(20,15,10,5,1,程序65】使用并查集的帶時限作業(yè)排序 int FJS(int *d,int *x,int n) UFSet s(n); int b,k=-1,*f=new intn+1; for (

34、int i=0;i=n;i+) fi=i,for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1); s.Union(t,r); fr=ft; delete f; return k;,6.4 最佳合并模式,6.4.1 問題描述,兩路合并外排序算法通過反復(fù)執(zhí)行將兩個有序子文件合并成一個有序文件的操作，最終將n個長度不等的有序子文件合并成一個有序文件。 合并n個有序子文件成為一個有序文件的合并過程可以有多種方式，稱為合并模式。 在整個合并過程中，需從外存讀寫的記錄數(shù)最少的合并方

35、案稱為最佳合并模式（optimal merge pattern,例64 設(shè)有5個有序子文件（F1,F2,F3,F4,F5），其長度分別為（20，30，30，10，5）。現(xiàn)通過兩兩合并將其合并成一個有序文件,帶權(quán)外路徑長度是針對擴(kuò)充二叉樹而言的。擴(kuò)充二叉樹（extended binary tree）中除葉子結(jié)點外，其余結(jié)點都必須有兩個孩子。擴(kuò)充二叉樹的帶權(quán)外路徑長度（weighted external path length）定義為,6.4.2貪心法求解,兩路合并最佳模式問題的最優(yōu)量度標(biāo)準(zhǔn)為帶權(quán)外路徑長度最小,兩路合并最佳模式的貪心算法簡述如下： 設(shè)Ww0,w1 ,wn1是n個有序文件的長度；以

36、每個權(quán)值作為根結(jié)點值，構(gòu)造n棵只有根的二叉樹； 選擇兩棵根結(jié)點權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和； 重復(fù)第2步，直到合并成一棵二叉樹為止,程序66】兩路合并最佳模式的貪心算法 template struct HNode /優(yōu)先權(quán)隊列中的元素的類型 operator T()const return weight; BTNode *ptr; T weight;,template BTNode* CreateHfmTree (T* w,int n) /w 為一維數(shù)組保存n個權(quán)值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b

37、; for (int i=0;i(wi); a.ptr=p;a.weight=wi; pq.Append(a);,for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a); return a.ptr;,6.4.3 算法正確性,定理64 設(shè)有n個權(quán)值W=w0,w1 ,wn1作為外結(jié)點的權(quán)值，構(gòu)造兩路合并樹的貪心算法將生成一棵具有最小帶權(quán)外路徑長度的二叉樹,6.5 最小代價生成樹,6.5.1 問題描述,問題 一個無向連通圖的生成樹是一個極小連通子圖，它包括圖中全部結(jié)點，并且有盡可能少的邊。 一棵生成樹的代價是樹中各條邊

38、上的代價之和。一個網(wǎng)絡(luò)的各生成樹中，具有最小代價的生成樹稱為該網(wǎng)絡(luò)的最小代價生成樹（minimum-cost spanning tree,6.5.2 貪心法求解,最優(yōu)量度標(biāo)準(zhǔn) 選擇使得迄今為止已入選S中邊的代價之和增量最小的邊 克魯斯卡爾算法的貪心準(zhǔn)則是：按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v)。 普里姆算法的貪心準(zhǔn)則是：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價的邊e=(u,v,程序67】最小代價生成樹的貪心算法 ESetType SpanningTree(ESetType E, int n) /G=(V,E)為無向圖 ESetType S=; int

39、 u,v,k=0; EType e; while (kn-1,6.5.3普里姆算法,程序68】普里姆算法 template struct ENode /帶權(quán)圖的邊結(jié)點 int adjVex; T w; ENode* nextArc;,template class Graph public: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode* a; int n;,template void Graph:Prim(int s) /公有成員函數(shù) int* nearest

40、=new intn,*lowcost=new intn; Prim(s,nearest,lowcost); for(int j=0;jn;j+) cout(nearestj,“ j,lowcostj) ; coutendl; delete nearest; delete lowcost;,template void Graph:Prim(int k, int* nearest,T* lowcost) /私有成員函數(shù) bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=

41、-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true,for (i=1;inextArc) int j= p-adjVex; if (!markj ) 普里姆算法的運行時間是O(n2,6.5.4 克魯斯卡爾算法,克魯斯卡爾算法從邊的集合E中，按照邊的權(quán)值從小到大的次序依次選取邊加以考察。 template struct eNode operator T ()const return w; int u,v; T w;,程序69】克魯斯卡爾算法 template void Graph:Kruskal( PrioQueu

42、e,while (kn-1 克魯斯卡爾算法的時間復(fù)雜度為 O（elog e,6.5.5 算法正確性,定理65 設(shè)圖G=（V，E）是一個帶權(quán)連通圖，U是V的一個真子集。若邊(u,v)E是所有uU, vV-U的邊中權(quán)值最小者，那么一定存在G的一棵最小代價生成樹T=(V,S)，(u,v)S。這一性質(zhì)稱為MST（minimum spanning tree）性質(zhì),定理66 普里姆算法和克魯斯卡爾算法都將產(chǎn)生一個帶權(quán)無向連通圖的最小代價生成樹,6.6 單源最短路徑,6.6.1 問題描述,單源最短路徑問題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點sV，求從s到其余各結(jié)點的最短路徑，其中，s稱為源點,6.6

43、.2 貪心法求解,迪杰斯特拉（Dijkstra） 算法 首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有結(jié)點之間的最短路徑都已求得為止,6.6.3 迪杰斯特拉算法,程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T*,private: int Choose(int* d, bool* s); T*a; int n;,template int MGraph:Choose(int* d, bool* s) int i,minpos; T m