第三章 貪心方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、能夠使目標(biāo)函數(shù)取最大值的可行解是問題的最優(yōu)解。 ——最優(yōu)解也可能有多個(gè)。,約束條件：,目標(biāo)函數(shù)：,例5.1 背包問題的實(shí)例 設(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. 貪心策略求解 度量標(biāo)準(zhǔn)的選擇：三種不同的選擇1）以目標(biāo)函數(shù)作為

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

20、i,j，且有(pi＝ 4，wi＝4) 和(pj＝ 3，wj＝2)，則下一步應(yīng)選擇j而非i放入背包： pi/2 = 2 ＜ pj＝ 3,實(shí)例分析（例4.1)∵ p1＞p2＞ p3∴ 首先將物品1放入背包，此時(shí)x1＝1，背包獲得p1＝25的效益增量，同時(shí)背包容量減少w1＝18個(gè)單位，剩余空間Δ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）以容量作為度量標(biāo)準(zhǔn) 以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn)所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉了，從而不能裝入“更多”的物品。 改進(jìn)：讓背包容量盡可能慢地消耗，從而可以盡量裝入“更多”的物品。 即，新的標(biāo)準(zhǔn)是：

23、以容量作為度量標(biāo)準(zhǔn) 該度量標(biāo)準(zhǔn)下的處理規(guī)則： ● 按物品重量的非降次序?qū)⑽锲费b入到背包； ● 如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包；,實(shí)例分析（例4.1)∵ w3＜w2 ＜w1∴ 首先將物品3放入背包，此時(shí)x3＝1，背包容量減少w3＝10個(gè)單位，剩余空間ΔM=10。同時(shí)，背包獲得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)的度量標(biāo)準(zhǔn) 影響背包效益值的因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長(zhǎng)速率和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前最大的單位效益。 在這種策略下的量度是：已裝入

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

27、此時(shí)，應(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)解的含義：在滿足約束條件的情況下，可使目標(biāo)函數(shù)取極（大或?。┲档目尚薪狻Ｘ澬慕馐强尚薪?，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 ● 如果這兩個(gè)解相同，則顯然貪心解就是最優(yōu)解。

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

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

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

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

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

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

37、期限之前完成 ti<=di;其中，ti是完成時(shí)間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) 度量標(biāo)準(zhǔn)的選擇 以目標(biāo)函數(shù) 作為量度。

38、 量度標(biāo)準(zhǔn)：下一個(gè)要計(jì)入的作業(yè)將是使得在滿足所產(chǎn)生的J是一個(gè)可行解的限制條件下讓 得到最大增加的作業(yè)。 處理規(guī)則：按pi的非增次序來考慮這些作業(yè)。,② 作業(yè)1具有當(dāng)前的最大效益值，且{1}是可行解，所以作業(yè)1計(jì)入J； ③ 在剩下的作業(yè)中，作業(yè)4具有最大效益值，且{1,4}也是可行解，故作業(yè)4計(jì)入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對(duì)于作業(yè)排序問題總是得

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

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

43、如果J中在[t’，t’+1]時(shí)刻沒有作業(yè)調(diào)度，則直接將i移到[t’，t’+1]調(diào)度?！碌恼{(diào)度表也是可行的。反之， ● 若t’＜t，則在SI中作類似的調(diào)換，即將SI中在[t，t+1]時(shí)刻調(diào)度的那個(gè)作業(yè)（如果有的話）與i相交換。如果I中在[t，t+1]時(shí)刻沒有作業(yè)調(diào)度，則直接將i移到[t，t+1]調(diào)度?！瑯?，新的調(diào)度表也是可行的。 對(duì)J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為S’J和S

44、’I，則在S’J和S’I中J和I中共有的所有作業(yè)將在相同的時(shí)間被調(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)度時(shí)刻是[ta, ta+1]， b是S’I中該時(shí)刻調(diào)度的作業(yè)。根據(jù)以上的討論有：pa≥pb。 在S’I中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合I’=I- ∪{a}的 一個(gè)可行地調(diào)度表，且I’的效益值不小于I的效益值。而I’中比I少了一個(gè)與J不同的作業(yè)。 重復(fù)上述的轉(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è)的一個(gè)特定序列就可判斷J的可行性： 對(duì)于所給出的一個(gè)排列σ＝i1i2…ik

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

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

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

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

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

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) 此時(shí)，若D(J(L))＞L, q＜L≤k,即說明q位置之后的所有作業(yè)均可推遲一個(gè)單位時(shí)間執(zhí)行，而又不違反各自的執(zhí)行期限。 若 D(i)>=q，將q位置之后的所有作業(yè)后移一位，作業(yè)i插入到位置q＋1處，

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

55、)是最優(yōu)解中的第i個(gè)作業(yè)，1≤i≤k。終止時(shí)， 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 //計(jì)入作業(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) //將插入點(diǎn)的作業(yè)后移一位// repeat J(r+1) ←I;k←k+1;K當(dāng)前解中的作業(yè)數(shù) endif repeat end JS,計(jì)算時(shí)間分析 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是當(dāng)前計(jì)入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是插入點(diǎn)的位置 －－－－－③ J(i+1) ←J(i) repeat J(r+1) ←I;k←k+1 endif repeat設(shè)s是最終計(jì)入J中的作業(yè)數(shù)，則算法JS所需要的總時(shí)間是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的計(jì)算時(shí)間降低到數(shù)量級(jí)接近О(n)。 前一種方法，納入序列J的作業(yè)存在向后移動(dòng)問題，改進(jìn)思想：將計(jì)入J的作業(yè)i盡量延遲處理，當(dāng)然是在di之前。,時(shí)間片：[α-1,α]的單位時(shí)間稱為時(shí)間片α對(duì)作業(yè)

61、i分配處理時(shí)間時(shí)，分配盡量大的空時(shí)間片α 。如果找不到一個(gè)空時(shí)間片，則拋棄i例5.3 n=5 p1-p5=20 15 10 5 1d1-d5=2 2 1 3 3J 已分配時(shí)間片 正考慮作業(yè) 動(dòng)作Ф 無 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 舍棄,,問題：如何確定最大的空時(shí)間片是多少？隨著作業(yè)的不斷加入，最大空時(shí)間

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

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

65、F(j) =nj≠0即有空時(shí)間片，則這個(gè)作業(yè)分配時(shí)間片nj 并且 將這個(gè)集合與包含F(xiàn)(j)-1的集合合并（因?yàn)樵摷现兴衅谙拗档淖鳂I(yè)最大可分配時(shí)間片減少1）若 F(j)=0 則無空時(shí)間片，放棄此作業(yè)，處理下一個(gè)作業(yè)，直到處理完n個(gè)作業(yè)。,初始值：F(i)=i 0 <=i<=b p(i)=-1;只包含一個(gè)期限值的樹,算法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è)序號(hào)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計(jì)入解 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