第三章 貪心方法

1、第4章 貪心方法,,從本章開始介紹一些與數(shù)據(jù)結(jié)構(gòu)中不同的算法設(shè)計方法：貪心法，動態(tài)規(guī)劃，分枝限界法。其它的方法還有：線性規(guī)劃，整數(shù)規(guī)劃，遺傳算法，模擬退火算法等等。,設(shè)計一個好的算法就像一門藝術(shù)。但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計方法，可以使用這些方法來設(shè)計算法。在許多情況下，為了獲得較好的性能，必須對這些算法進行細致的調(diào)整。但在某些情況下，算法經(jīng)過調(diào)整之后仍然無法達到要求，這時就必須尋求另外的方法來求解該問題。,

2、4.1 最優(yōu)化問題,1. 問題的一般特征 問題有n個輸入，問題的解是由這n個輸入的某個子集組成，這個子集必須滿足某些事先給定的條件。約束條件：子集必須滿足的條件；可行解：滿足約束條件的子集；可行解可能不唯一；目標函數(shù)：用來衡量可行解優(yōu)劣的標準，一般以函數(shù)的形式給出；最優(yōu)解：能夠使目標函數(shù)取極值（極大或極?。┑目尚薪?。,例1 [渴嬰問題] 有一個非?？实?、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種

3、類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n種不同的飲料。根據(jù)以前關(guān)于這n種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個滿意度值：飲用1盎司第i種飲料，對它作出相對評價，將一個數(shù)值si作為滿意度賦予第i種飲料。 通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴地需要，但是不幸地是：具有最大滿意度值地飲料有時并沒有足夠地量來滿足此嬰兒解

4、渴地需要。設(shè)ai是第i種飲料地總量，而此嬰兒需要t盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？,上述問題可形式描述如下：輸入：n,t,si,ai(其中1?i?n,n為整數(shù)，t、si、ai為正實數(shù))。,輸出：實數(shù)xi(1?i?n)，使 最大，且 。如果 ，則輸出適當?shù)腻e誤信息。,限制條件為,優(yōu)化函數(shù)為,任何滿足限制條件的一組實數(shù)xi都是

5、可行解，而使 最大的可行解是最優(yōu)解。,例2 [裝箱問題] 有一艘大船準備用來裝載貨物。所有待裝載貨物都裝在貨箱中，且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i種貨箱的重量為wi(1?i?n )，而貨船的最大載重量為c，我們的目標是在貨船上裝入最多的貨物。,這個問題可以作為最優(yōu)化問題進行描述：設(shè)存在一組標量xi ,其可能取值為0或1。如果xi 為0，則貨箱i不被裝上船；如xi 為1，則貨箱i將被裝上船。我們的目

6、的是找到一組xi ，使它滿足限制條件：,相應(yīng)的優(yōu)化函數(shù)是：,滿足限制條件的每一組xi 都是可行解，能使,取得最大值的方案是最優(yōu)解。,例3 [找零錢問題] 一個小孩買了價值少于1元的糖，并將1元錢交給了售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為50分、10分、5分、2分、1分的硬幣。 可以通過解不定方程來解決這一問題。也可以分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時采用如下準則：每一次選擇

7、應(yīng)使零錢數(shù)盡量增大。為保證解的可行性，所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。 假設(shè)需要找給小孩88分，首先選1枚50分的硬幣，然后選3枚10分硬幣，再選1枚5分硬幣，1枚2分硬幣，1枚1分的硬幣。 問題：這樣得到的硬幣數(shù)目達到最少嗎？ 類似問題：工資發(fā)放。,例4 [最小代價通訊網(wǎng)絡(luò)] 城市之間所有可能的通信連接可被視作一個無向圖，圖的每條邊都被賦予一個權(quán)值，權(quán)值表示建成由這條邊所表示的

8、通信連接所要付出的代價。包含圖中所有頂點（城市）的連通子圖都是一個可行解。設(shè)所有權(quán)值都為負，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解就是其中具有最小代價的生成樹。 在這個問題中，需要選擇一個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構(gòu)成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。,例5 [最短路徑問題] 在有向圖中求一個頂點到另一個頂點的最短路徑。（如路由問題）,例6 [機器調(diào)度]

9、 現(xiàn)有n件任務(wù)和無限多臺機器，任務(wù)可以在機器上得到處理。每件任務(wù)的開始時間為si ，完成時間為fi ， si <fi 。[si ,fi ]為處理任務(wù)i的時間范圍。兩個任務(wù)i,j重疊是指兩個任務(wù)的時間范圍區(qū)間重疊，而并非是指i,j的起點或終點重合。一個可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺機器。因此，在可行的分配中，每臺機器在任何時刻最多只處理一個任務(wù)。最優(yōu)分配是指使用的機器最少的可行分配方案。 假

10、設(shè)有n=7件任務(wù)，標號為a到g。它們的開始于完成時間如下：任務(wù) a b c d e f g開始 0 3 4 9 7 1 6完成 2 7 7 11 10 5 8 若將任務(wù)a分給機器M1,任務(wù)b分給機器M2,…,任務(wù)g分給機器M7這種分配是可行的分配，共使用了7臺機器。但它不是最優(yōu)分配。因為若將a、b、d分配給同一臺機器，則機器數(shù)目降為

11、5臺。,最優(yōu)化問題求解分類：根據(jù)描述問題約束條件和目標函數(shù)的數(shù)學模型的特性和問題的求解方法的不同，可分為：線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等。,貪心方法：一種改進的分級的處理方法，可對滿足上述特征的某些問題方便地求解。,2. 貪心方法的一般策略 問題的一般特征：問題的解是由n個輸入的、滿足某些事先給定的條件的子集組成。 1）一般方法 根據(jù)題意，選取一種度量標準。然后按照這種度量標準對n個輸入

12、排序，并按序一次輸入一個量。 如果這個輸入和當前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中。否則，將當前輸入合并到部分解中從而得到包含當前輸入的新的部分解。 2）貪心方法 這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法稱為貪心方法,注： 貪心解 ＝ 最優(yōu)解,3）使用貪心策略求解的關(guān)鍵 選取能夠得到問題最優(yōu)解的量度標準。,直接將目標函數(shù)作

13、為量度標準也不一定能夠得到問題的最優(yōu)解,？,3. 貪心方法的抽象化控制描述returnprocedure GREEDY(A,n) //A(1:n)包含n個輸入// solution←Φ //將解向量solution初始化為空// for i←1 to n do x←SELECT(A) //按照度量標準，從A中選擇一個輸入，其值賦予x, 并將之從A中刪除//

14、 if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中， 即是否能共同構(gòu)成可行解// solution←UNION(solution,x) //將x和當前的解向量合并成新的解向量，并修改目標函數(shù)// endif repeat end GREEDY,4.2 背包問題,1.問題的描述 已知n種物品具有重量

15、(w1,w2,…,wn)和效益值(p1,p2,…,pn) ，及一個可容納M重量的背包；設(shè)當物品i全部或一部分xi放入背包將得到pi xi的效益，這里，0≤ xi ≤1, pi >0。 問題：采用怎樣的裝包方法才能使裝入背包的物品的總效益最大？,② 如果所有物品的總重量不超過M，即 ≤M，則把所有的物品都裝入背包中將獲得最大可能的效益值。,③ 如果物品的總重量超過了M，則將有物品不能（全部）裝 入背包

16、中。由于0≤xi≤1，所以可以把物品的一部分裝入背包，所以最終背包中可剛好裝入重量為M的若干物品（整個或一部分） 目標：使裝入背包的物品的總效益達到最大。,分析：① 裝入背包的總重量不能超過M,問題的形式描述,可 行 解： 滿足上述約束條件的任一集合(x1,x2,…,xn) 都是問題的一個可行解——可行解可能有多個。 (x1,x2,…,xn)稱為問題的一個解向量最 優(yōu) 解：

17、能夠使目標函數(shù)取最大值的可行解是問題的最優(yōu)解。 ——最優(yōu)解也可能有多個。,約束條件：,目標函數(shù)：,例5.1 背包問題的實例 設(shè)，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下：,① (1/2,1/3,1/4) 16.5 24.2

18、5 //沒有放滿背包// ② (1, 2/15, 0 ) 20 28.2 ③ (0, 2/3, 1) 20 31 ④ (0, 1, 1/2) 20 31.5,(x1,x2,x3),2. 貪心策略求解 度量標準的選擇：三種不同的選擇1）以目標函數(shù)作為

19、度量標準 即，每裝入一件物品，就使背包背包獲得最大可能的效益增量。 該度量標準下的 處理規(guī)則： ● 按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?● 如果正在考慮的物品放不進去，則只取其一部分裝滿背包：如果該物品的一部分不滿足獲得最大效益增量的度量標準，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。 如：若ΔM=2,背包外還剩兩件物品

20、i,j，且有(pi＝ 4，wi＝4) 和(pj＝ 3，wj＝2)，則下一步應(yīng)選擇j而非i放入背包： pi/2 = 2 ＜ pj＝ 3,實例分析（例4.1)∵ p1＞p2＞ p3∴ 首先將物品1放入背包，此時x1＝1，背包獲得p1＝25的效益增量，同時背包容量減少w1＝18個單位，剩余空間ΔM=2。 其次考慮物品2和3。就ΔM=2而言有，只能選擇物品2或3的一部分裝

21、入背包。 物品2： 若 x2＝2/15， 則 p2 x2＝16/5＝3.2 物品3： 若 x3＝2/10， 則 p3 x3＝3 為使背包的效益有最大的增量，應(yīng)選擇物品2的2/15裝包，即 x2＝2/15 最后，背包裝滿， ΔM=0，故物品3將不能裝入背包，x3＝0 。 背包最終可以獲得效益值＝ x1 p1 ＋x2 p2＋x3 p3

22、 ＝ 28.2 (次優(yōu)解,非問題的最優(yōu)解),2）以容量作為度量標準 以目標函數(shù)作為度量標準所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉了，從而不能裝入“更多”的物品。 改進：讓背包容量盡可能慢地消耗，從而可以盡量裝入“更多”的物品。 即，新的標準是：

23、以容量作為度量標準 該度量標準下的處理規(guī)則： ● 按物品重量的非降次序?qū)⑽锲费b入到背包； ● 如果正在考慮的物品放不進去，則只取其一部分裝滿背包；,實例分析（例4.1)∵ w3＜w2 ＜w1∴ 首先將物品3放入背包，此時x3＝1，背包容量減少w3＝10個單位，剩余空間ΔM=10。同時，背包獲得p3＝15的效益增量。 其次考慮物品1和2。就ΔM=10而言有，也只能選擇物品1或2的一

24、部分裝入背包。為使背包的按照“統(tǒng)一”的規(guī)則，下一步將放入物品2的10/15裝包，即 x2＝10/15＝2/3 最后，背包裝滿ΔM=0，故物品1將不能裝入背包，x1＝0 。 背包最終可以獲得效益值＝ x1 p1 ＋x2 p2＋x3 p3

25、 ＝ 31 (次優(yōu)解,非問題的最優(yōu)解) 存在的問題：效益值沒有得到“最大”的增加,3）最優(yōu)的度量標準 影響背包效益值的因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當前最大的單位效益。 在這種策略下的量度是：已裝入

26、的物品的累計效益值與所用容量之比。 故，新的量度標準是：每次裝入要使累計效益值與所用容量的比值有最多的增加和最小的減小。 此時，將按照物品的單位效益值：pi/wi 比值（密度）的非增次序考慮。,實例分析（例4.1)∵ p1/w1＜p3/w3 ＜p2/w2∴ 首先將物品2放入背包，此時x2＝1，背包容量減少w2＝15個單位，還剩余空間ΔM=5。同時，背包獲得p2＝24的效益增量。 其次考慮物品1和3。

27、此時，應(yīng)選擇物品3,且就ΔM=5而言有，也只能放入物品3的一部分到背包中 。即 x3＝5/10＝1/2 最后，背包裝滿ΔM=0，故物品1將不能裝入背包，x1＝0 。 背包最終可以獲得效益值＝ x1 p1 ＋x2 p2＋x3 p3

28、 ＝ 31.5 (最優(yōu)解),9,3. 背包問題的貪心求解算法,算法4.2 背包問題的貪心算法 procedure GREEDY－KNAPSACK(P,W,M,X,n) //p(1:n)和w(1:n)分別含有按P(i)/W(i)≥P(i＋1)/W(i＋1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量// real P(1:n),W(1:n),X(1:n),M,cu;

29、 integer I,n X←0 //將解向量初始化為空// cu←M //cu是背包的剩余容量// for i←1 to n do if W(i) > cu then exit endif X(i) ←1 cu ←cu-W(i) repeat if i≤n then X(i

30、) ←cu/W(i) endif end GREEDY-KNAPSACK,4. 最優(yōu)解的證明,即證明：由第三種策略所得到的貪心解是問題的最優(yōu)解。 最優(yōu)解的含義：在滿足約束條件的情況下，可使目標函數(shù)取極（大或?。┲档目尚薪?。貪心解是可行解，故只需證明：貪心解可使目標函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 ● 如果這兩個解相同，則顯然貪心解就是最優(yōu)解。

31、否則， ● 這兩個解不同，就去找開始不同的第一個分量位置i，然后設(shè)法用貪心解的這個xi去替換最優(yōu)解的那個xi ，并證明最優(yōu)解在分量代換前后總的效益值沒有任何變化。 可反復進行代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣。這一代換過程中，最優(yōu)解的效益值沒有任何損失，從而證明貪心解的效益值與代換前后最優(yōu)解的效益值相同。即，貪心解如同最優(yōu)解一樣可取得目標函數(shù)的最大/最小值。 從而得證：該貪心解也即問題的最優(yōu)

32、解。,定理4.1 如果p1/w1≥ p2/w2≥…≥ pn/wn,則算法GREEDY-KNAPSACK對于給定的背包問題實例生成一個最優(yōu)解。證明： 設(shè)X=(x1, x2, …, xn)是GRDDDY-KNAPSACK所生成的貪心解。① 如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則，② 設(shè)j是使xi≠1的最小下標。由算法可知， xi=1 1≤i＜j, 0≤xj＜1

33、 xi=0 j＜i≤n 若X不是問題的最優(yōu)解，則必定存在一個可行解 Y=(y1, y2, …, yn),使得：,且應(yīng)有：,設(shè)k是使得yk≠ xk的最小下標，則有yk＜ xk: a) 若k<j，則xk=1。因為yk≠ xk,從而有yk ＜ xk b) 若k=j，由于 ，且對1≤i＜j，有yi=xi=1,而對j＜i≤n,有xi＝0；故此時若yk

34、＞xk，則將有 ，與Y是可行解相矛盾。而yk≠ xk,所以yk ＜ xk c) 若k＞j，則 ，不能成立 在Y中作以下調(diào)整：將yk增加到xk，因為yk≤xk,為保持解的可行性，必須從(yk , yk+1,…,yn)中減去同樣多的量。設(shè)調(diào)整后的解為Z=(z1, z2, …, zn)，其中zi＝xi，1≤i≤k，且有： 則對

35、于Z有：,(1)若,或者Z≠X，則重復以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解。,(2)若,由以上分析得：,則或者Z=X，則X就是最優(yōu)解；,，則Y將不是最優(yōu)解；,練習PP87 3.[0/1背包問題],4.3 帶有限期的作業(yè)排序,1. 問題描述 假定在一臺機器上處理n個作業(yè)，每個作業(yè)均可在單位時間內(nèi)完成；同時每個作業(yè)i都有一個截至期限di>0,當且僅當作業(yè)i在其截至期限以前被完成時

36、，則獲得pi>0的效益。 問題：求這n個作業(yè)的一個子集J，其中的所有作業(yè)都可在其截至期限內(nèi)完成。——J是問題的一個可行解。 可行解J中的所有作業(yè)的效益之和是?pi ，具有最大效益值的可行解是該問題的最優(yōu)解。 如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得當前最大效益值；否則，將有作業(yè)無法完成——決策應(yīng)該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。,目標函數(shù)：,約束條件：所有的作業(yè)都應(yīng)在其

37、期限之前完成 ti<=di;其中，ti是完成時間di是截止期限,例4.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) 度量標準的選擇 以目標函數(shù) 作為量度。

38、 量度標準：下一個要計入的作業(yè)將是使得在滿足所產(chǎn)生的J是一個可行解的限制條件下讓 得到最大增加的作業(yè)。 處理規(guī)則：按pi的非增次序來考慮這些作業(yè)。,② 作業(yè)1具有當前的最大效益值，且{1}是可行解，所以作業(yè)1計入J； ③ 在剩下的作業(yè)中，作業(yè)4具有最大效益值，且{1,4}也是可行解，故作業(yè)4計入J，即J={1,4}；

39、 ④ 考慮{1,3,4}和{1,2,4}均不能構(gòu)成新的可行解，作業(yè)3和2將被舍棄。 故最后的J={1,4}，最終效益值＝120（問題的最優(yōu)解）,例：例4.2求解① 首先令J=Φ,,2)作業(yè)排序算法的概略描述 算法4.3 procedure GREEDY-JOB(D,J,n) //作業(yè)按p1≥p2≥…≥pn的次序輸入，它們的期限值D(i)≥1, 1≤i

40、≤n,n≥1。J是在它們的截止期限完成的作業(yè)的集合// J←{1} for i←2 to n do if J∪{i}的所有作業(yè)能在它們的截止期限前完成 then J←J∪{i} endif repeat end GREEDY-JOB,2. 最優(yōu)解證明,定理4.2 算法4.3對于作業(yè)排序問題總是得

41、到問題的一個最優(yōu)解證明： 設(shè)J是由算法所得的貪心解作業(yè)集合，I是一個最優(yōu)解的作業(yè)集合。 ① 若I=J，則J就是最優(yōu)解；否則 ② ，即至少存在兩個作業(yè)a和b，使得a∈J且 ,b∈I且 。 并設(shè)a是這樣的一個具有最高效益值的作業(yè)，且由算法的處理規(guī)則可得：對于在I中而不在J中的作業(yè)所有b，有：

42、 pa≥pb,設(shè)SJ和SI分別是J和I的可行的調(diào)度表。因為J和I都是可行解，故這樣的調(diào)度表一定存在； 設(shè)i是既屬于J又屬于I的一個作業(yè)，并i設(shè)在調(diào)度表SJ中的調(diào)度時刻是[t，t+1]，而在SI中的調(diào)度時刻是[t’，t’+1]。 在SJ和SI中作如下調(diào)整： ● 若t＜t’，則將SJ中在[t’，t’+1]時刻調(diào)度的那個作業(yè)（如果有的話）與i相交換。

43、如果J中在[t’，t’+1]時刻沒有作業(yè)調(diào)度，則直接將i移到[t’，t’+1]調(diào)度?！碌恼{(diào)度表也是可行的。反之， ● 若t’＜t，則在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)度表為S’J和S

44、’I，則在S’J和S’I中J和I中共有的所有作業(yè)將在相同的時間被調(diào)度。,sj o o o o o o o o o o i o o o o o o t’ tsi’ o o o o o o o o o o i o o o o o o t’ tsi o o o o o o i o

45、o o o o o o o o o,sj o o o o o o i o o o o o o o o o o t t’sj’ o o o o o o o o o o i o o o o o o t t’si o o o o o o o o o o i o o o o o o,設(shè)

46、a在S’J中的調(diào)度時刻是[ta, ta+1]， b是S’I中該時刻調(diào)度的作業(yè)。根據(jù)以上的討論有：pa≥pb。 在S’I中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合I’=I- ∪{a}的 一個可行地調(diào)度表，且I’的效益值不小于I的效益值。而I’中比I少了一個與J不同的作業(yè)。 重復上述的轉(zhuǎn)換，可使I在不減效益值的情況下轉(zhuǎn)換成J。從而J至少有和I一樣的效益值。所以J也是最優(yōu)解。證畢。,si’ o o

47、o o o o o b o o o o o o tasj’ o o o o o o o a o o o o o o tasi’ o o o o o o o a o o o o o o,3. 如何判斷J的可行性,方法二：檢查J中作業(yè)的一個特定序列就可判斷J的可行性： 對于所給出的一個排列σ＝i1i2…ik

48、,由于作業(yè)ij完成的最早時間是j，因此只要判斷出σ排列中的每個作業(yè)dij≥j，就可得知σ是一個允許的調(diào)度序列，從而J是一個可行解。 反之，如果σ排列中有一個dij＜j,則σ將是一個行不通的調(diào)度序列，因為至少作業(yè)ij不能在其期限之前完成。 這一檢查過程可以只通過檢驗J中作業(yè)的一種特殊的排列：按照作業(yè)期限的非降次序排列的作業(yè)序列即可完成。,方法一：檢驗J中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠

49、在其期限前完成——若J中有k個作業(yè)，則將要檢查k!個序列,定理4.3 設(shè)J是k個作業(yè)的集合，σ＝i1i2…ik是J中作業(yè)的一種排列，它使得di1≤di2≤…≤dik。J是一個可行解，當且僅當J中的作業(yè)可以按照σ的次序而又不違反任何一個期限的情況來處理。證明： ① 如果J中的作業(yè)可以按照σ的次序而又不違反任何一個期限的情況來處理，則J是一個可行解 ② 若J是一個可行解，則必存在序列σ’＝r1r2…rk，使得drj

50、≥j, 1≤j≤k。 ★ 若σ＝σ’，則σ即是可行解。否則， ★ σ≠σ’，令a是使得ra≠ia的最小下標，并設(shè)rb=ia。則有： b＞a 且 dra≥drb (為什么?) 在σ’中調(diào)換ra與rb，所得的新序列σ’’＝ s1s2…sk的處理次序不違反任何一個期限。 重復上述過程，則可將σ’轉(zhuǎn)換成σ且不違反任何一個期限。故σ是一個可行的調(diào)度序列

51、 故定理得證。,σ’ ooooooraoooorboooooσ ooooooiaoooooooraooo,5. 帶有限期的作業(yè)排序算法的實現(xiàn),對當前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠合并到當前部分解J中。如果可以，則插入到序列中，形成新的可行解序列。否則，舍棄該作業(yè)。具體如下： 假設(shè)n個作業(yè)已經(jīng)按照效益值

52、從大到小的次序，即p1≥p2≥…≥pn的順序排列好，每個作業(yè)可以在單位時間內(nèi)完成，并具有相應(yīng)的時間期限；且至少有一個單位時間可以執(zhí)行作業(yè) 首先，將作業(yè)1存入部分解J中，此時J是可行的； 然后，依次考慮作業(yè)2到n。假設(shè)已經(jīng)處理了i-1個作業(yè)，其中有k個作業(yè)計入了部分解J中：J(1),J(2),…,J(k)，且有 D(J(1))≤D(J(2))≤…≤D(J(k)),對當前正在考

53、慮的作業(yè)i,將D(i)依次和D(J(k)), D(J(k-1)),…，D(J(1))相比較，直到找到位置q：使得 ★ D(i)＜ D(J(l))，q＜l≤k，且 ★ D(J(q))≤ D(i) 此時，若D(J(L))＞L, q＜L≤k,即說明q位置之后的所有作業(yè)均可推遲一個單位時間執(zhí)行，而又不違反各自的執(zhí)行期限。 若 D(i)>=q，將q位置之后的所有作業(yè)后移一位，作業(yè)i插入到位置q＋1處，

54、從而得到一個包含k+1個作業(yè)的新的可行解。 若找不到這樣的q，作業(yè)i將被舍棄。 對i之后的其它作業(yè)重復上述過程直到n個作業(yè)處理完畢。最后J中所包含的作業(yè)集合是此時算法的貪心解，也是問題的最優(yōu)解。,,①,②,③,④,算法5.4 帶有限期和效益的單位時間的作業(yè)排序貪心算法 procedure JS(D,J,n,k) //D(1),…,D(n)是期限值。n≥1。作業(yè)已按p1≥p2≥…≥pn的順序排序。J(i

55、)是最優(yōu)解中的第i個作業(yè)，1≤i≤k。終止時， D(J(i))≤D(J(i＋1))， 1≤i＜k// integer D(0:n),J(0:n),i,k,n,r D(0)←J(0)←0 //初始化，設(shè)置崗哨// k←1;J(1)←1 //計入作業(yè)1// for i←2 to n do //按p的非增次序考慮作業(yè)。找i的位置并檢查插入的可行性// r←k

56、 while D(J(r))＞D(i) and D(J(r)) ≠r do r←r-1 repeat If D(J(r))≤D(i) and D(i)＞r then //把i插入到J中// for i←k to r+1 by -1 do J(i+

57、1) ←J(i) //將插入點的作業(yè)后移一位// repeat J(r+1) ←I;k←k+1;K當前解中的作業(yè)數(shù) endif repeat end JS,計算時間分析 for i←2 to n do ? 將循環(huán)n-1次－－－－－－－－－－－－－－－－－－① r←k while

58、 D(J(r))＞D(i) and D(J(r)) ≠r do ? 至多循環(huán)k次， k是當前計入J中的作業(yè)數(shù) －－－② r←r-1 repeat If D(J(r))≤D(i) and D(i)＞r then

59、 for i←k to r+1 by -1 do ? 循環(huán)k-r次，r是插入點的位置 －－－－－③ J(i+1) ←J(i) repeat J(r+1) ←I;k←k+1 endif repeat設(shè)s是最終計入J中的作業(yè)數(shù)，則算法JS所需要的總時間是O(sn)。s≤n，故最壞情況：TJS = О(n2)，特例

60、情況：pi=di=n-i+1,1≤i≤n最好情況：TJS = О(n)，特例情況：pi=di=i,1≤i≤n,6. 一種“更快”的作業(yè)排序問題 使用不相交集合的 UNION和FIND算法（見1.4.3節(jié)），可以將JS的計算時間降低到數(shù)量級接近О(n)。 前一種方法，納入序列J的作業(yè)存在向后移動問題，改進思想：將計入J的作業(yè)i盡量延遲處理，當然是在di之前。,時間片：[α-1,α]的單位時間稱為時間片α對作業(yè)

61、i分配處理時間時，分配盡量大的空時間片α 。如果找不到一個空時間片，則拋棄i例5.3 n=5 p1-p5=20 15 10 5 1d1-d5=2 2 1 3 3J 已分配時間片 正考慮作業(yè) 動作Ф 無 1 分配[1,2]{1} [1,2]

62、2 分配[0,1]{1,2} [0,1][1,2] 3 舍棄{1,2} [0,1][1,2] 4 分配[2,3]{1,2,4} [0,1][1,2][2,3] 5 舍棄,,問題：如何確定最大的空時間片是多少？隨著作業(yè)的不斷加入，最大空時間

63、片是變化的。如何動態(tài)改變作業(yè)的最大空時間片？,基本思想,1.用i表示時間片[i-1,i],只需考慮這樣的時間片 [i-1,i] , 1≦i ≦b, b=min{n,max{dj}}2.將b個期限值分成一些集合:i:期限值,ni時間片對于任意一個期限值i,ni是使得nj ≦i的最大整數(shù)且是空時間片。ni是i的最大空時間片，nj是j的最大空時間片當且僅當ni=nj時i和j在同一集合中即，具有相同最大空時間片的期限值在同一

64、集合中,3.用F(i)表示期限值i的當前最大空時間片 F(i)=niF(i)的值在每次處理完一個作業(yè)后，可能要更新。引入虛擬時間片0[-1,0]避免極端情況產(chǎn)生b+1個期限值初始時為F(i)=i 0≦i≦b4. 用樹來表示集合P(i)>0時 表示期限i的父親結(jié)點P(i)<0時 表示期限i是根，且該集合中有|P(i)|個結(jié)點,5.當前正考慮作業(yè)具有期限值d，則需要尋找期限值d所在集合，即尋找所在樹的根j若

65、F(j) =nj≠0即有空時間片，則這個作業(yè)分配時間片nj 并且 將這個集合與包含F(xiàn)(j)-1的集合合并（因為該集合中所有期限值的作業(yè)最大可分配時間片減少1）若 F(j)=0 則無空時間片，放棄此作業(yè)，處理下一個作業(yè)，直到處理完n個作業(yè)。,初始值：F(i)=i 0 <=i<=b p(i)=-1;只包含一個期限值的樹,算法4.5 作業(yè)排序的更快算法proc fjs（D,n,b,J,

66、k）//假定作業(yè)按pi非增序排列，b=min{n,max{dj}}for i=1 to b do F(i)=i,P(i)=-1; repeatk=0;//J中的作業(yè)序號for i=1 to n do j=Find(min(n,D(i)));//找期限值所屬集合的根j if F(j) ≠0 then k=k+1 ;J(k)=i//作業(yè)i計入解 l=Find(F(j)-1);Union

67、(l,j); F(j)=F(l) endifrepeatend fjs,例4.4 n=7, p1-p7=35,30,25,20,15,10,5d1-d7=4,2,4,3,4,8,3.利用fjs算法求最優(yōu)解解：考慮 F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) J作業(yè)無 0 1 2 3 4

68、 5 6 7 Ф 1 0 1 2 3 3 5 6 7 {1}2 0 1 1 3 3 5 6 7 {12}3 0 1 1 1 3 5 6 7 {123}4 0