第五章 貪心方法

1、2024/3/6,第五章 貪心方法,2024/3/6,5.1 一般方法,1. 問題的一般特征 問題有n個(gè)輸入，問題的解是由這n個(gè)輸入的某個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件。 約束條件：子集必須滿足的條件； 可行解：滿足約束條件的子集；可行解可能不唯一； 目標(biāo)函數(shù)：用來衡量可行解優(yōu)劣的標(biāo)準(zhǔn)，一般以函數(shù)的形式給出； 最優(yōu)解：能夠使目標(biāo)函數(shù)取極值（極大或極?。┑目尚薪?。

2、 分類：根據(jù)描述問題約束條件和目標(biāo)函數(shù)的數(shù)學(xué)模型的特性和問題的求解方法的不同，可分為：線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等。 ——最優(yōu)化問題求解 貪心方法：一種改進(jìn)的分級的處理方法，可對滿足上述特征的某些問題方便地求解。,2024/3/6,例[找零錢]

3、一個(gè)小孩買了價(jià)值少于1元的糖，并將1元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供數(shù)目不限的面值為25分、10分、5分及1分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個(gè)硬幣。 選擇硬幣時(shí)所采用的貪心算法如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為確保解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。 假設(shè)需要找給小孩67分，首先入選的是兩枚25分的硬幣，第三枚入選

4、的不能是25分的硬幣，否則將不可行（零錢總數(shù)超過67分），第三枚應(yīng)選擇10分的硬幣，然后是5分的，最后加入兩個(gè)1分的硬幣。 貪心算法有種直覺的傾向，在找零錢時(shí)，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）,2024/3/6,2. 貪心方法的一般策略 問題的一般特征：問題的解是由n個(gè)輸入的、滿足某些事先給定的條件的子集組成。 1）一般方法 根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。然后按照這

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

6、量度標(biāo)準(zhǔn)也不一定能夠得到問題的最優(yōu)解 3）使用貪心策略求解的關(guān)鍵 選取能夠得到問題最優(yōu)解的量度標(biāo)準(zhǔn)。,2024/3/6,3. 貪心方法的抽象化控制描述 procedure GREEDY(A,n) //A(1:n)包含n個(gè)輸入// solution←Φ //將解向量solution初始化為空// for i←1 to n do x←S

7、ELECT(A) //按照度量標(biāo)準(zhǔn)，從A中選擇一個(gè)輸入，其值賦予x 并將之從A中刪除// if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中， 即是否能共同構(gòu)成可行解//

8、 solution←UNION(solution,x) //將x和當(dāng)前的解向量合并成新的解 向量，并修改目標(biāo)函數(shù)// endif repeat return(solution) end GREEDY,2024/3/6,5.2 背包問題,1.問題的描述

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

10、中將獲得最大可能的效益值 ③ 如果物品的總重量超過了M，則將有物品不能（全部）裝 入背包中。由于0≤xi≤1，所以可以把物品的一部分裝入背包，所以最終背包中可剛好裝入重量為M的若干物品（整個(gè)或一部分） 目標(biāo)：使裝入背包的物品的總效益達(dá)到最大。,2024/3/6,問題的形式描述 目標(biāo)函數(shù)： 約束條件： 可 行 解：滿足上

11、述約束條件的任一集合(x1,x2,…,xn) 都是問題 的一個(gè)可行解——可行解可能為多個(gè)。 (x1,x2,…,xn)稱為問題的一個(gè)解向量 最 優(yōu) 解：能夠使目標(biāo)函數(shù)取最大值的可行解是問題的 最優(yōu)解——最優(yōu)解也可能為多個(gè)。,2024/3/6,例5.1 背包問題的實(shí)例 設(shè)，n=3，M=2

12、0， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下： (x1,x2,x3) ① (1/2,1/3,1/4) 16.5 24.25 //沒有放滿背包// ② (1, 2/15, 0 ) 20

13、28.2 ③ (0, 2/3, 1) 20 31 ④ (0, 1, 1/2) 20 31.5,2024/3/6,2. 貪心策略求解 度量標(biāo)準(zhǔn)的選擇：三種不同的選擇1）以目標(biāo)函數(shù)作為度量標(biāo)準(zhǔn) 即，每裝入一件物品，就使背包背包獲得最大可能的效益增量。 該度量標(biāo)準(zhǔn)下的 處理規(guī)則：

14、 ● 按效益值的非增次序?qū)⑽锲芬患胤湃氲奖嘲?● 如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包：如果該物品的一部分不滿足獲得最大效益增量的度量標(biāo)準(zhǔn)，則在剩下的物品種選擇可以獲得最大效益增量的其它物品，將它或其一部分裝入背包。 如：若ΔM=2,背包外還剩兩件物品i,j，且有(pi＝ 4，wi＝4) 和(pj＝ 3，wj＝2)，則下一步應(yīng)選擇j而非i放入背包：

15、 pi/2 = 2 ＜ pj＝ 3,2024/3/6,實(shí)例分析（例5.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)∵ p1＞p2＞ p3∴ 首先將物品1放入背包，此時(shí)x1＝1，背包獲得p1＝25的效益增量，同時(shí)背包容量減少w1＝18個(gè)單位，剩余空間ΔM=2。 其次考慮物品2和3。就ΔM=2而言有，只能選擇物品2或3的一部分裝入背包。

16、 物品2： 若 x2＝2/15， 則 p2 x2＝16/5＝3.1 物品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

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

18、標(biāo)準(zhǔn)是：以容量作為度量標(biāo)準(zhǔn) 該度量標(biāo)準(zhǔn)下的處理規(guī)則： ● 按物品重量的非降次序?qū)⑽锲费b入到背包； ● 如果正在考慮的物品放不進(jìn)去，則只取其一部分裝滿背包；,2024/3/6,實(shí)例分析（例5.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)∵ w3＜w2 ＜w1∴ 首先將物品3放入背包，此時(shí)x3＝1，背包容量減少w3＝10個(gè)單位，還剩

19、余空間ΔM=10。同時(shí)，背包獲得p3＝15的效益增量。 其次考慮物品1和2。就ΔM=10而言有，也只能選擇物品1或2的一部分裝入背包。為使背包的按照“統(tǒng)一”的規(guī)則，下一步將放入物品2的10/15裝包，即 x2＝10/15＝2/3 最后，背包裝滿ΔM=0，故物品1將不能裝入背包，x1＝0 。 背包最終可以獲得效益值＝ x1 p1 ＋x2 p2＋x3

20、 p3 ＝ 31 (次優(yōu)解,非問題的最優(yōu)解) 存在的問題：效益值沒有得到“最大”的增加,2024/3/6,3）最優(yōu)的度量標(biāo)準(zhǔn) 影響背包效益值得因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長速率

21、和背包容量消耗速率之間取得平衡，即每次裝入的物品應(yīng)使它所占用的每一單位容量能獲得當(dāng)前最大的單位效益。 在這種策略下的量度是：已裝入的物品的累計(jì)效益值與所用容量之比。 故，新的量度標(biāo)準(zhǔn)是：每次裝入要使累計(jì)效益值與所用容量的比值有最多的增加（首次裝入）和最小的減小（其后的裝入）。 此時(shí)，將按照物品的單位效益值：pi/wi 比值（密度）的非增次序考慮。,2024/3/6,實(shí)例分析（例5.1)(p1

22、,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)∵ p1/w1＜p3/w3 ＜p2/w2∴ 首先將物品2放入背包，此時(shí)x2＝1，背包容量減少w2＝15個(gè)單位，還剩余空間ΔM=5。同時(shí)，背包獲得p2＝24的效益增量。 其次考慮物品1和3。此時(shí)，應(yīng)選擇物品3,且就ΔM=5而言有，也只能放入物品3的一部分到背包中 。即 x3＝5

23、/10＝1/2 最后，背包裝滿ΔM=0，故物品1將不能裝入背包，x1＝0 。 背包最終可以獲得效益值＝ x1 p1 ＋x2 p2＋x3 p3 ＝ 31.5 (最優(yōu)解),2024/3/6,3. 背包問題的貪心求解算法,算法5.2 背包問題的貪心算法 procedure GREEDY

24、－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; integer I,n X←0 //將解向量初始化為空//

25、 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) ←cu/W(i) endif end GREEDY-KNAPSACK

26、,2024/3/6,4. 最優(yōu)解的證明,即證明：由第三種策略所得到的貪心解是問題的最優(yōu)解。 最優(yōu)解的含義：在滿足約束條件的情況下，可使目標(biāo)函數(shù)取極（大或?。┲档目尚薪?。貪心解是可行解，故只需證明：貪心解可使目標(biāo)函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 ● 如果這兩個(gè)解相同，則顯然貪心解就是最優(yōu)解。否則， ● 這兩個(gè)解不同，就去找開始不同的第一個(gè)分

27、量位置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)解。,2024/3/6,定理5.1 如果p1/w1≥ p2/w

28、2≥…≥ pn/wn,則算法GREEDY-KNAPSACK對于給定的背包問題實(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 xi=0 j＜

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

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

31、24/3/6,由以上分析得，若 ，則Y將不是最優(yōu)解；若 ，則或者Z=X，則X就是最優(yōu)解；或者Z≠X，則重復(fù)以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解,2024/3/6,5.3 帶有限期的作業(yè)排序,1. 問題描述 假定在一臺機(jī)器上處理n個(gè)作業(yè)，每個(gè)作業(yè)均可在單位時(shí)間內(nèi)完成

32、；同時(shí)每個(gè)作業(yè)i都有一個(gè)截至期限di>0,當(dāng)且僅當(dāng)作業(yè)i在其截至期限以前被完成時(shí)，則獲得pi>0的效益。 問題：求這n個(gè)作業(yè)的一個(gè)子集J，其中的所有作業(yè)都可在其截至期限內(nèi)完成?！狫是問題的一個(gè)可行解。 可行解J中的 所有作業(yè)的效益之和是 ，具有最大效益值的可行解是該問題的最優(yōu)解。 如果所有的作業(yè)都能在其期限之內(nèi)完成則顯然可以獲得當(dāng)前最大效益值；否則，將有

33、作業(yè)無法完成——決策應(yīng)該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。 目標(biāo)函數(shù)： 約束條件：所有的作業(yè)都應(yīng)在其期限之前完成,2024/3/6,例5.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。,2024/3/6,1. 帶有

34、限期的作業(yè)排序算法,1) 度量標(biāo)準(zhǔn)的選擇 以目標(biāo)函數(shù) 作為量度。 量度標(biāo)準(zhǔn)：下一個(gè)要計(jì)入的作業(yè)將是使得在滿足所 產(chǎn)生的J是一個(gè)可行解的限制條件下讓 得到最大增加的作業(yè)。 處理規(guī)則：按pi的非增次序來考慮這些作業(yè)。,2024/3/6,例：例5.2求解 (p

35、1，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將被舍

36、棄。 故最后的J={1,4}，最終效益值＝120（問題的最優(yōu)解）,2024/3/6,2)作業(yè)排序算法的概略描述 算法5.3 procedure GREEDY-JOB(D,J,n) //作業(yè)按p1≥p2≥…≥pn的次序輸入，它們的期限值D(i)≥1, 1≤i≤n,n≥1。J是在它們的截止期限完成的作業(yè)的集合// J←{1}

37、 for i←2 to n do if J∪{i}的所有作業(yè)能在它們的截止期限前完成 then J←J∪{i} endif repeat end GREEDY-JOB,2024/3/6,2. 最優(yōu)解證明,定理5.2 算法5.3對于作業(yè)排序問題總是得到問題的一個(gè)最優(yōu)解證明： 設(shè)J是由算法所得的貪心解作業(yè)集合，I是一個(gè)

38、最優(yōu)解的作業(yè)集合。 ① 若I=J，則J就是最優(yōu)解；否則 ② ，即至少存在兩個(gè)作業(yè)a和b，使得a∈J且 ,b∈I且 。 并設(shè)a是這樣的一個(gè)具有最高效益值的作業(yè)，且由算法的處理規(guī)則可得：對于在I中而不在J中的作業(yè)所有b，有： pa≥pb,2024/3/6,設(shè)S

39、J和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相交換。如果J中在[t’，t’+1]時(shí)刻沒有作業(yè)調(diào)度，則直接將i移到[t’

40、，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)度表也是可行的。 對J和I中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為S’J和S’I，則在S’J和S’I中J和I中共有的所有作業(yè)將在相同的時(shí)間被調(diào)

41、度。,2024/3/6,設(shè)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)解。證

42、畢。,2024/3/6,3. 如何判斷J的可行性,方法一：檢驗(yàn)J中作業(yè)所有可能的排列，對于任一種次序排列的作 業(yè)排列，判斷這些作業(yè)是否能夠在其期限前完成——若J 中有k個(gè)作業(yè)，則將要檢查k!個(gè)序列方法二：檢查J中作業(yè)的一個(gè)特定序列就可判斷J的可行性： 對于所給出的一個(gè)排列σ＝i1i2…ik,由于作業(yè)ij完成的 最早時(shí)間是j，因此只

43、要判斷出σ排列中的每個(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è)序列即可完成。,2024/3/6,定理5.3 設(shè)J是k個(gè)作業(yè)的集合，σ＝i1i

44、2…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≥j, 1≤j≤k。 ★ 若σ＝σ’，則σ即是可行解。否則， ★ σ≠σ’，

45、令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)度序列 故定理得證。,2024/3/6,σ＝

46、 i1 i2 … ia … … ic … ikσ’＝r1 r2 … ra … rb … rk ★ a＜b ★ dra≥drb,,,2024/3/6,5. 帶有限期的作業(yè)排序算法的實(shí)現(xiàn),對當(dāng)前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個(gè)按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠合并到當(dāng)前部分解J中。如果可以，則插入到序列中，

47、形成新的可行解序列。否則，舍棄該作業(yè)。具體如下： 假設(shè)n個(gè)作業(yè)已經(jīng)按照效益值從大到小的次序，即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)，且有

48、 D(J(1))≤D(J(2))≤…≤D(J(k)),2024/3/6,對當(dāng)前正在考慮的作業(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í)行，而又不違反

49、各自的執(zhí)行期限。 最后，將q位置之后的所有作業(yè)后移一位，將作業(yè)i插入到位置q＋1處，從而得到一個(gè)包含k+1個(gè)作業(yè)的新的可行解。 若找不到這樣的q，作業(yè)i將被舍棄。 對i之后的其它作業(yè)重復(fù)上述過程直到n個(gè)作業(yè)處理完畢。最后J中所包含的作業(yè)集合是此時(shí)算法的貪心解，也是問題的最優(yōu)解。,2024/3/6,算法5.4 帶有限期和效益的單位時(shí)間的作業(yè)排序貪心算法 procedure JS(D,J,n,k)

50、 //D(1),…,D(n)是期限值。n≥1。作業(yè)已按p1≥p2≥…≥pn的順序排序。J(i)是最優(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 //初始化// k←1;J(1)←1 //計(jì)入作業(yè)1// for i←2 t

51、o n do //按p的非增次序考慮作業(yè)。找i的位置并檢查插入的可行性// r←k 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中//

52、 for i←k to r+1 by -1 do J(i+1) ←J(i) //將插入點(diǎn)的作業(yè)后移一位// repeat J(r+1) ←i;k←k+1 endif repeat end JS,2024/3/6,計(jì)算時(shí)間分析 for i←2 to n do

53、 ? 將循環(huán)n-1次－－－－－－－－－－－－－－－－－－① r←k while 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

54、 If D(J(r))≤D(i) and D(i)＞r then 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是最

55、終計(jì)入J中的作業(yè)數(shù)，則算法JS所需要的總時(shí)間是O(sn)。s≤n，故最壞情況：TJS = О(n2)，特例情況：pi=di=n-i+1,1≤i≤n最好情況：TJS = О(n)，特例情況：di=i,1≤i≤n,2024/3/6,6. 一種“更快”的作業(yè)排序問題 使用不相交集合的 UNION和FIND算法（見2.4.3節(jié)），可以將JS的計(jì)算時(shí)間降低到數(shù)量級接近О(n)。 （略）,2024/3/6,例5.3 設(shè)

56、n=5,(p1,…,p5)=(20,15,10,5,1),(d1,…,d5)=(2,2,1,3,3)。,最優(yōu)解是J＝{1,2,4},2024/3/6,5.4 最優(yōu)歸并模式,1. 問題的描述1）兩個(gè)文件的歸并問題 兩個(gè)已知文件的一次歸并所需的計(jì)算時(shí)間＝O(兩個(gè)文件的元素總數(shù)) 例： n個(gè)記錄的文件 ＋

57、 (n+m) 個(gè)記錄的文件 m個(gè)記錄的文件 О(n+m) 2）多個(gè)文件的歸并 已知n個(gè)文件，將之歸并成一個(gè)單一的文件 例：假定文件X1，X2， X3， X4，采用兩兩歸并的方式，可能的歸并模式有： ① X1+X2=Y1+X3= Y2+X4= Y3 ② X1+

58、X2 = Y1 + →Y3 X3+X4=Y2,,2024/3/6,二路歸并模式：每次僅作兩個(gè)文件的歸并；當(dāng)有多個(gè)文件時(shí)，采用兩兩歸并的模式，最終得到一個(gè)完整的記錄文件。 二元?dú)w并樹：二路歸并模式的歸并過程可以用一個(gè)二元樹的形式描述，稱之為二元?dú)w并樹。如 歸并樹的構(gòu)造

59、 外結(jié)點(diǎn)：n個(gè)原始文件 內(nèi)結(jié)點(diǎn)：一次歸并后得到的文件 在兩路歸并模式下，每個(gè)內(nèi)結(jié)點(diǎn)剛好有兩個(gè)兒子，代表把它的兩個(gè)兒子表示的文件歸并成其本身所代表的文件,2024/3/6,不同的歸并順序帶來的計(jì)算時(shí)間是不同的。 例5.5 已知X1,X2,X3是分別為30、20、10個(gè)記錄長度的已分類文件。將這3個(gè)文件歸并成長度為60的文件?？赡艿臍w并過程和相應(yīng)的記錄移動次數(shù)如下：

60、 問題：采用怎樣的歸并順序才能使歸并過程中元素的移動次數(shù)最?。ɑ驁?zhí)行的速度最快）,2024/3/6,2. 貪心求解1) 度量標(biāo)準(zhǔn)的選擇 ★ 任意兩個(gè)文件的歸并所需的元素移動次數(shù)與這兩個(gè)文件的長度之和成正比； ★ 度量標(biāo)準(zhǔn)：每次選擇需要移動次數(shù)最少的兩個(gè)集合進(jìn)行歸并； ★ 處理規(guī)則：每次選擇長度最小的兩個(gè)文件進(jìn)行歸并。,(F1,F2,F3,F4,F5) = (20,30,10,5,30)

61、,2024/3/6,2) 目標(biāo)函數(shù) 目標(biāo)：元素移動的次數(shù)最少 實(shí)例：為得到歸并樹根結(jié)點(diǎn)表示的歸并文件，外部結(jié)點(diǎn)中每個(gè)文件記錄需要移動的次數(shù)＝該外部結(jié)點(diǎn)到根的距離，即根到該外部結(jié)點(diǎn)路徑的長度。如， F4 ： 則F4中所有記錄在整個(gè)歸并過程中移動的總量＝|F4|*3 帶權(quán)外部路徑長度：記di是由根到代表文件Fi的外部結(jié)點(diǎn)的距離，qi是Fi的長度，則這棵樹的代表的歸并

62、過程的元素移動總量是： 最優(yōu)的二路歸并模式：與一棵具有最小外部帶權(quán)路徑長度的二元樹相對應(yīng)。,2024/3/6,算法5.6 生成二元?dú)w并樹的算法 procedure TREE(L,n) //L是n個(gè)單結(jié)點(diǎn)的二元樹表// for i←1 to n-1 do call GETNODE(T) //構(gòu)造一顆新樹T// LCHILD(T) ←

63、LEAST(L) //從表L中選當(dāng)前根WEIGHT最小的樹， 并從中刪除// RCHILD(T) ←LEAST(L) WEIGHT(T) ←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T)) call INSERT

64、(L,T) //將歸并的樹T加入到表L中// repeat return (LEAST(L)) //此時(shí)，L中的樹即為歸并的結(jié)果// end TREE,2024/3/6,例5.6 已知六個(gè)初始文件，長度分別為：2,3,5,7,9,13。 采用算法TREE，各階段的工作狀態(tài)如圖所示：,2024/3/6,2024/3/6,時(shí)間分析 1) 循環(huán)體：n-

65、1次 2) L以有序序列表示 LEAST(L): О(1) INSERT(L,T): О(n) 總時(shí)間： О(n2) 3) L以min-堆表示 LEAST(L): О(logn) INSERT(L,T): О(logn) 總時(shí)間： О(

66、nlogn),2024/3/6,3. 最優(yōu)解的證明 定理5.4 若L最初包含n≥1個(gè)單結(jié)點(diǎn)的樹，這些樹有WEIGHT值為(q1,q2,…,qn)，則算法TREE對于具有這些長度的n個(gè)文件生成一棵最優(yōu)的二元?dú)w并樹。證明：歸納法證明 ① 當(dāng)n=1時(shí)，返回一棵沒有內(nèi)部結(jié)點(diǎn)的樹。定理得證。 ② 假定算法對所有的(q1,q2,…,qn)，1≤m＜n,生成一棵最優(yōu)二元?dú)w并樹。

67、 ③ 對于n,假定q1≤q2≤…≤qn,則q1和q2將是在for循環(huán)的第一次迭代中首先選出的具有最小WEIGHT值的兩棵樹（的WEIGHT值）；如圖所示，T是由這樣的兩棵樹構(gòu)成的子樹：,2024/3/6,■ 設(shè)T’是一棵對于(q1,q2,…,qn)的最優(yōu)二元?dú)w并樹。 ■ 設(shè)P是T’中距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。 若P的兩棵子樹不是q1和q2，則用q1和q2代換P當(dāng)前的子樹而不會增加T’的帶權(quán)外部路徑長

68、度。 故，T應(yīng)是最優(yōu)歸并樹中的子樹。 則在T’中用一個(gè)權(quán)值為q1＋q2的外部結(jié)點(diǎn)代換T，得到的是一棵關(guān)于(q1＋q2,…,qn)最優(yōu)歸并樹T”。 而由歸納假設(shè)，在用權(quán)值為q1＋q2的外部結(jié)點(diǎn)代換了T之后，過程TREE將針對(q1＋q2,…,qn)得到一棵最優(yōu)歸并樹。將T帶入該樹，根據(jù)以上討論，將得到關(guān)于(q1,q2,…,qn)的最優(yōu)歸并樹。 故，TREE生成一棵關(guān)于(q1,q2,…

69、,qn)的最優(yōu)歸并樹。,2024/3/6,5. k路歸并模式 每次同時(shí)歸并k個(gè)文件。 k元?dú)w并樹：可能需要增加“虛”結(jié)點(diǎn)，以補(bǔ)充不足的外部結(jié)點(diǎn)。 ★ 如果一棵樹的所有內(nèi)部結(jié)點(diǎn)的度都為k，則外部結(jié)點(diǎn)數(shù)n滿足 n mod (k-1) = 1 ★ 對于滿足 n mod (k－1) =1的整數(shù)n，存在一棵具有n個(gè)外部結(jié)點(diǎn)的k元樹T，且T中所有結(jié)點(diǎn)的度為k。 至多需要增加k-2個(gè)外部結(jié)點(diǎn)。