第五章 貪心方法

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

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

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

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

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

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

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

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

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

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

11、述約束條件的任一集合(x1,x2,…,xn) 都是問題 的一個可行解——可行解可能為多個。 (x1,x2,…,xn)稱為問題的一個解向量 最 優(yōu) 解：能夠使目標函數(shù)取最大值的可行解是問題的 最優(yōu)解——最優(yōu)解也可能為多個。,2024/3/6,例5.1 背包問題的實例 設(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. 貪心策略求解 度量標準的選擇：三種不同的選擇1）以目標函數(shù)作為度量標準 即，每裝入一件物品，就使背包背包獲得最大可能的效益增量。 該度量標準下的 處理規(guī)則：

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

15、 pi/2 = 2 ＜ pj＝ 3,2024/3/6,實例分析（例5.1)(p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)∵ p1＞p2＞ p3∴ 首先將物品1放入背包，此時x1＝1，背包獲得p1＝25的效益增量，同時背包容量減少w1＝18個單位，剩余空間Δ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 為使背包的效益有最大的增量，應選擇物品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）以容量作為度量標準 以目標函數(shù)作為度量標準所存在的問題：盡管背包的效益值每次得到了最大的增加，但背包容量也過快地被消耗掉了，從而不能裝入“更多”的物品。 改進：讓背包容量盡可能慢地消耗，從而可以盡量裝入“更多”的物品。 即，新的

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

19、余空間ΔM=10。同時，背包獲得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)的度量標準 影響背包效益值得因素： 背包的容量M 放入背包中的物品的重量及其可能帶來的效益值 可能的策略是：在背包效益值的增長速率

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

22、,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)∵ p1/w1＜p3/w3 ＜p2/w2∴ 首先將物品2放入背包，此時x2＝1，背包容量減少w2＝15個單位，還剩余空間ΔM=5。同時，背包獲得p2＝24的效益增量。 其次考慮物品1和3。此時，應選擇物品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)解的含義：在滿足約束條件的情況下，可使目標函數(shù)取極（大或?。┲档目尚薪?。貪心解是可行解，故只需證明：貪心解可使目標函數(shù)取得極值。 證明的基本思想：將此貪心解與（假設(shè)中的）任一最優(yōu)解相比較。 ● 如果這兩個解相同，則顯然貪心解就是最優(yōu)解。否則， ● 這兩個解不同，就去找開始不同的第一個分

27、量位置i，然后設(shè)法用貪心解的這個xi去替換最優(yōu)解的那個xi ，并證明最優(yōu)解在分量代換前后總的效益值沒有任何變化。 可反復進行代換，直到新產(chǎn)生的最優(yōu)解與貪心解完全一樣。這一代換過程中，最優(yōu)解的效益值沒有任何損失，從而證明貪心解的效益值與代換前后最優(yōu)解的效益值相同。即，貪心解如同最優(yōu)解一樣可取得目標函數(shù)的最大/最小值。 從而得證：該貪心解也即問題的最優(yōu)解。,2024/3/6,定理5.1 如果p1/w1≥ p2/w

28、2≥…≥ 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 xi=0 j＜

29、i≤n 若X不是問題的最優(yōu)解，則必定存在一個可行解 Y=(y1, y2, …, yn),使得： 且應有：,2024/3/6,設(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＞

30、xk，則將有 ，與Y是可行解相矛盾。而yk≠ xk,所以yk ＜ xk c) 若k＞j，則 ，不能成立 在Y中作以下調(diào)整：將yk增加到xk，因為yk≤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，則重復以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解,2024/3/6,5.3 帶有限期的作業(yè)排序,1. 問題描述 假定在一臺機器上處理n個作業(yè)，每個作業(yè)均可在單位時間內(nèi)完成

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

33、作業(yè)無法完成——決策應該執(zhí)行哪些作業(yè)，以獲得最大可能的效益值。 目標函數(shù)： 約束條件：所有的作業(yè)都應在其期限之前完成,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) 度量標準的選擇 以目標函數(shù) 作為量度。 量度標準：下一個要計入的作業(yè)將是使得在滿足所 產(chǎn)生的J是一個可行解的限制條件下讓 得到最大增加的作業(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具有當前的最大效益值，且{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將被舍

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è)排序問題總是得到問題的一個最優(yōu)解證明： 設(shè)J是由算法所得的貪心解作業(yè)集合，I是一個

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

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

40、，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’I，則在S’J和S’I中J和I中共有的所有作業(yè)將在相同的時間被調(diào)

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

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

43、要判斷出σ排列中的每個作業(yè) dij≥j，就可得知σ是一個允許的調(diào)度序列，從而J是一個 可行解。反之，如果σ排列中有一個dij＜j,則σ將是一個 行不通的調(diào)度序列，因為至少作業(yè)ij不能在其期限之前完 成。 這一檢查過程可以只通過檢驗J中作業(yè)的一種特殊的排列：按照作業(yè)期限的非降次序排列的作業(yè)序列即可完成。,2024/3/6,定理5.3 設(shè)J是k個作業(yè)的集合，σ＝i1i

44、2…ik是J中作業(yè)的一種排列，它使得di1≤di2≤…≤dik。J是一個可行解，當且僅當J中的作業(yè)可以按照σ的次序而又不違反任何一個期限的情況來處理。證明： ① 如果J中的作業(yè)可以按照σ的次序而又不違反任何一個期限的情況來處理，則J是一個可行解 ② 若J是一個可行解，則必存在序列σ’＝r1r2…rk，使得drj≥j, 1≤j≤k。 ★ 若σ＝σ’，則σ即是可行解。否則， ★ σ≠σ’，

45、令a是使得ra≠ia的最小下標，并設(shè)rb=ia。則有： b＞a 且 dra≥drb (為什么?) 在σ’中調(diào)換ra與rb，所得的新序列σ’’＝ s1s2…sk的處理次序不違反任何一個期限。 重復上述過程，則可將σ’轉(zhuǎn)換成σ且不違反任何一個期限。故σ是一個可行的調(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è)排序算法的實現(xiàn),對當前正在考慮的作業(yè)j，按限期大小采用一種“插入排序”的方式，嘗試將其“插入”到一個按限期從小到大順序構(gòu)造的作業(yè)調(diào)度序列中，以此判斷是否能夠合并到當前部分解J中。如果可以，則插入到序列中，

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

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

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

50、 //D(1),…,D(n)是期限值。n≥1。作業(yè)已按p1≥p2≥…≥pn的順序排序。J(i)是最優(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 //初始化// k←1;J(1)←1 //計入作業(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) //將插入點的作業(yè)后移一位// repeat J(r+1) ←i;k←k+1 endif repeat end JS,2024/3/6,計算時間分析 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是當前計入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是插入點的位置 －－－－－③ J(i+1) ←J(i) repeat J(r+1) ←I;k←k+1 endif repeat設(shè)s是最

55、終計入J中的作業(yè)數(shù)，則算法JS所需要的總時間是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的計算時間降低到數(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）兩個文件的歸并問題 兩個已知文件的一次歸并所需的計算時間＝O(兩個文件的元素總數(shù)) 例： n個記錄的文件 ＋

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

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

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

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

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

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

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

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

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

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

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)二元歸并樹。 ■ 設(shè)P是T’中距離根最遠的一個內(nèi)部結(jié)點。 若P的兩棵子樹不是q1和q2，則用q1和q2代換P當前的子樹而不會增加T’的帶權(quán)外部路徑長

68、度。 故，T應是最優(yōu)歸并樹中的子樹。 則在T’中用一個權(quán)值為q1＋q2的外部結(jié)點代換T，得到的是一棵關(guān)于(q1＋q2,…,qn)最優(yōu)歸并樹T”。 而由歸納假設(shè)，在用權(quán)值為q1＋q2的外部結(jié)點代換了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路歸并模式 每次同時歸并k個文件。 k元歸并樹：可能需要增加“虛”結(jié)點，以補充不足的外部結(jié)點。 ★ 如果一棵樹的所有內(nèi)部結(jié)點的度都為k，則外部結(jié)點數(shù)n滿足 n mod (k-1) = 1 ★ 對于滿足 n mod (k－1) =1的整數(shù)n，存在一棵具有n個外部結(jié)點的k元樹T，且T中所有結(jié)點的度為k。 至多需要增加k-2個外部結(jié)點。