1、Chapter16 貪心算法貪心算法1Ch16.貪心算法貪心算法 求最優解的問題可看作是通過一系列步驟，每求最優解的問題可看作是通過一系列步驟，每一步有一選擇的集合，對于較簡單的問題，動態規一步有一選擇的集合，對于較簡單的問題，動態規劃顯得過于復雜，可用較簡單有效的算法求解之。劃顯得過于復雜，可用較簡單有效的算法求解之。 貪心算法總是在當前步驟上選取最好的方案，貪心算法總是在當前步驟上選取最好的方案，即它是一種局部最優的選擇，并希望它導致一個全即它是一種局部最優的選擇，并希望它導致一個全局最優，但有時是不可能導致全局最優。局最優，但有時是不可能導致全局最優。 例：求例：求v到到w的一條最短路徑

2、，若從的一條最短路徑，若從v搜索到鄰點搜索到鄰點t最短，未必是最短，未必是v到到w最短。最短。 但是，仍有許多問題貪心法將產生全局最優解，如但是，仍有許多問題貪心法將產生全局最優解，如MST，單源最短路徑等。，單源最短路徑等。216.1 活動選擇問題活動選擇問題n 多個活動競爭資源的調度問題：盡可能多地選擇互不多個活動競爭資源的調度問題：盡可能多地選擇互不沖突的活動沖突的活動n 設有設有n個活動個活動S=a1, a2,an，均要使用某資源，均要使用某資源(如教如教室室)，該資源使用方式為獨占式，一次只供一個活動，該資源使用方式為獨占式，一次只供一個活動使用使用v每個活動每個活動ai發生的時間為

3、發生的時間為si,fi), 0sifi v兩活動兩活動ai, aj相容（不沖突）是指：相容（不沖突）是指： si,fi), sj,fj)不不重疊，滿足重疊，滿足si ffj j or or sj ffi i。即：。即：一活動的開始一活動的開始時間大于等于另一活動的完成時間。時間大于等于另一活動的完成時間。v活動選擇問題：活動選擇問題：選擇最多的互不沖突的活動，使選擇最多的互不沖突的活動，使相容活動集合最大。即：相容活動集合最大。即：ASS， ，A A中活中活動動互不沖突互不沖突且且|A|A|最大。最大。316.1 活動選擇問題活動選擇問題n 例例（按完成時間遞增序排列）按完成時間遞增序排列）v

4、問題的解：問題的解：A1=a3,a9,a11, A2=a1,a4, a8,a11 A3=a2,a4,a9a11v最優解：最優解： A2和和A3 此問題可用迭代方法直接給出貪心算法，但為比較此問題可用迭代方法直接給出貪心算法，但為比較和動態規劃之關系，下面先考慮動態規劃解法。和動態規劃之關系，下面先考慮動態規劃解法。4i1234567891011si130535688212fi456789101112131416.1 活動選擇問題活動選擇問題1、活動選擇問題的最優子結構、活動選擇問題的最優子結構v子問題空間可描述為：子問題空間可描述為：Sij是是S的子集，它包含那些（可在活動的子集，它包含那些（

5、可在活動ai完成之后開完成之后開始）始）and（可在活動（可在活動aj開始之前完成）的活動開始之前完成）的活動ak。 亦即：亦即：Sij中所有活動中所有活動ak與活動與活動ai、aj相容，不妨稱相容，不妨稱ai、aj和子集和子集Sij相容，因此相容，因此ak也與所有不遲于也與所有不遲于fi完成的完成的活動以及與所有不早于活動以及與所有不早于sj開始的活動相容。開始的活動相容。Note：Sij中可能有沖突的活動。中可能有沖突的活動。為方便處理，設有兩個虛擬的活動為方便處理，設有兩個虛擬的活動a0和和an+1，并且假，并且假定定 因此，因此，5:jkkikijsfsfSaS10, 0nsf1,0

6、,1, 0njiSSn16.1 活動選擇問題活動選擇問題為了更嚴格定義為了更嚴格定義i和和j的范圍，假定所有活動已按完的范圍，假定所有活動已按完成時間的單調增有序：成時間的單調增有序：6式1 .16.1210nnfffff,/ /,01ijijSijSiji jijn 若易于用反證法證明只考慮當。因此的范圍是：16.1 活動選擇問題活動選擇問題v如何分解問題？如何分解問題？ 設子問題設子問題 。若。若Sij的解的解中選擇了中選擇了ak，使用，使用ak產生產生Sij的兩個子問題：的兩個子問題：Sij的解顯然是的解顯然是Sik和和Skj解的并，再加上解的并，再加上ak。 注意注意Sik和和Skj已

7、去掉了那些與已去掉了那些與ak沖突的活動，而這些沖突的活動，而這些活動原來可能在活動原來可能在Sij中。中。7jkkiijkijsfsfSaS,相容的子集，這兩子集與均是開始前完成的那些活動完成之后開始，在包括在開始前完成的那些活動完成之后開始，在包括在kijjkkjkiikaSaaSaaS:16.1 活動選擇問題活動選擇問題v最優子結構最優子結構v用子問題的最優解構造原問題的最優解用子問題的最優解構造原問題的最優解8,ijijkijikkjikkjikkjSAaASSAAAAcutandpaste設的最優解是，則兩子問題和的解和也必須是最優的易用反證法證明：因為和是獨立的，可用證明的一個最優

8、解整個問題的最優解是式1, 0)2 .16(nkjkikijSAaAA16.1 活動選擇問題活動選擇問題2、一個遞歸解、一個遞歸解 設設Ci,j表示表示Sij的最優解的值，即的最優解的值，即Sij中相容活動最大子中相容活動最大子集的集的size：Ci,j=|Aij|1)2)9ijijijijASAjijiCS,/0,，此時時，當16.2 , , , 1,11,/ /110 , max , , 1ijkijikkjijijikkkjikkjijiji kjSaASSSC i jC i kC k jikjkjiAAaAAASC i jC i kC k jS 當時，假設，則可用和兩子問題的最優解來構

9、造的最優解，由式：有選擇當當16.1 活動選擇問題活動選擇問題n作業：作業：Ex16.1-11016.1 活動選擇問題活動選擇問題3、動態規劃到貪心法的轉化、動態規劃到貪心法的轉化 到此可直接寫出動態規劃解，留作練習到此可直接寫出動態規劃解，留作練習 可通過下面的定理簡化其解，該定理也說明貪心算法可通過下面的定理簡化其解，該定理也說明貪心算法的正確性。的正確性。Th16.1 設設Sij是任一非空子問題，是任一非空子問題，am是是Sij中具有最早中具有最早完成時間的活動：完成時間的活動：fm=minfk: ak Sij ，則：，則： 活動活動am必定被包含在必定被包含在Sij的某個最優解中；的某

10、個最優解中；子問題子問題Sim是空集，使是空集，使Smj是唯一可能的非空集是唯一可能的非空集 /選選am的目的的目的1112:21imkimikkmkmkijmijijijijkpfSaSfsfsaaaSaSASAa先證第 部分：假定非空，則，使的完成時間先于且這與是 的最早完成活動矛盾！再證第 部分：設是 的某個最優解，并假設 中的活動已按完成時間單調增排過序，是其中第一個活動。13kmmkmijijkmijkijijmkkijmkijijijijijijijmaaaaaAAaaAaASffaAaaAASAAASa若，則問題已得證，即最優解包含若，則構造子集，只需證也是最優解即可又是 中最早

11、完成的任務，比更早完成中的活動互不沖突，也即是 的一個解亦是 的一個最優解，它包含16.1 活動選擇問題活動選擇問題u該定理的價值可簡化問題的解該定理的價值可簡化問題的解v在動態規劃求解時，原問題在動態規劃求解時，原問題Sij可分解為兩個子問題可分解為兩個子問題Sik和和Skj求解，且這種分解有求解，且這種分解有j-i-1中可能中可能v定理定理16.1將其簡化為：將其簡化為： 求求Sij的最優解時只用到一個子問題，另一個子問的最優解時只用到一個子問題，另一個子問題為空；題為空； 只須考慮一種選擇：即選只須考慮一種選擇：即選Sij中最早完成的活動中最早完成的活動vv該定理帶來的另一個好處是：能以

12、自頂向下的方式該定理帶來的另一個好處是：能以自頂向下的方式解每一個子問題：解每一個子問題：1416.1 活動選擇問題活動選擇問題對原問題對原問題S=S0,n+1，選其中最早完成的活動，選其中最早完成的活動am1 S中的活動已按完成時間單調增有序中的活動已按完成時間單調增有序 m1=1。下一子問題應是。下一子問題應是Sm1，n+1/已去掉與已去掉與am1沖突的沖突的活動活動選選Sm1,n+1中最早完成的活動中最早完成的活動am2一般形式，當選擇一般形式，當選擇ami到解集中之后，需解的子問題變到解集中之后，需解的子問題變為為Smi,n+1 顯然，所選活動是按完成時間單調增有序的顯然，所選活動是按

13、完成時間單調增有序的(m1m2mi)15221, 11未必為到沖突的活動刪除才能得中與須將mSaSnmm16.1 活動選擇問題活動選擇問題vv貪心選擇貪心選擇 當某個當某個ami加入解集合后，我們總是在剩余加入解集合后，我們總是在剩余的活動中選擇第一個不與的活動中選擇第一個不與ami沖突的活動加入解沖突的活動加入解集合，該活動是能夠最早完成且與集合，該活動是能夠最早完成且與ami相容。相容。 這種選擇為剩余活動的調度留下了盡可能這種選擇為剩余活動的調度留下了盡可能多的機會。即：留出盡可能多的時間給剩余的多的機會。即：留出盡可能多的時間給剩余的尚未調度的活動，以使解集合中包含的活動最尚未調度的活

14、動，以使解集合中包含的活動最多。多。 每次選一個最早完成并與剛加入解集元素每次選一個最早完成并與剛加入解集元素相容的活動相容的活動1616.1 活動選擇問題活動選擇問題4、遞歸的貪心算法、遞歸的貪心算法v輸入：向量輸入：向量s和和f，并假定已按，并假定已按f單調增有序單調增有序 子問題子問題Sij的下標的下標v輸出：輸出：Sij的最優解的最優解v算法：算法：17181121Re( , , )/ /0,11;/ /0()() / /1;/ /,.,1()/ /ijmiiijiijimcursiveActivitySelector s f i jijnmiiawhile mj and sfdoaS

15、mmaaaaaif mj then 求S 的最優解.原問題的解：當時，有 必加入解集將與 沖突的活動去掉，才能得到在中找第 個與 相容的活動,1Re( , );/ /;/ /mimijimmmjjisf aSareturnacursiveActivitySelector s f m jaSelsereturnaa是中的第 個活動， /即在 完成后開始且最早能完成的活動和最優解并開始前能夠完成的活動均與 沖突16.1 活動選擇問題活動選擇問題n 時間時間v若要排序，則時間為若要排序，則時間為v若已排序，則若已排序，則RecursiveActivitySelector(s,f,0,n+1)的時間為

16、的時間為 在所有的調用里，每個活動被檢查一次，請注意每次在所有的調用里，每個活動被檢查一次，請注意每次循環檢查時，活動序號只增加不減少，從循環檢查時，活動序號只增加不減少，從RAS(s,f,i,j)調用到調用到RAS(s,f,m,j)時，必有時，必有im。j始終為始終為n+119)lg(nn)(n16.1 活動選擇問題活動選擇問題5、迭代的貪心算法、迭代的貪心算法 上述遞歸很接近于尾遞歸，只是結束前多了一個上述遞歸很接近于尾遞歸，只是結束前多了一個Union操作，很易轉換為迭代算法：操作，很易轉換為迭代算法： j始終不變，始終不變，j=n+1當一個活動當一個活動ai加入解集合之后，我們只要從加

17、入解集合之后，我們只要從ai依次往后找到第一個不與依次往后找到第一個不與ai沖突的活動沖突的活動am，由，由于活動事先按完成時間單調增有序，故于活動事先按完成時間單調增有序，故am是最是最早完成且與早完成且與ai相容的活動，它也是相容的活動，它也是Sij中的第一中的第一個活動個活動20211,1( ,)/ / ; ;/ /1;/ /2/ /()/ /,;/ /;/ /ii nmimmimmiGreedyActivitySelector S ffnlength sAaAiiAaformtondoSaif fsthenim aaAAaaaimi單調增有序為解集合是最近加入解集合 的活動 的下標找中

18、最早完成的活動與 相容是與 相容且完成時間 /最早的活動仍記錄最近加入/ /endif;iAareturnA的活動 的下標16.1 活動選擇問題活動選擇問題 注意，若直接給出迭代算法，一般要證注意，若直接給出迭代算法，一般要證A確實為最優解。確實為最優解。這一點由遞歸算法得以保證，亦可用歸納法直接證明：這一點由遞歸算法得以保證，亦可用歸納法直接證明：v 總是存在一個最優解，第一步是貪心的選擇，即選擇活總是存在一個最優解，第一步是貪心的選擇，即選擇活動動a1；v 在已做的選擇數目上做歸納法證明在已做的選擇數目上做歸納法證明 2216.1 活動選擇問題活動選擇問題 vv 算法要點算法要點vi始終表

19、示最近加入始終表示最近加入A的活動的下標的活動的下標v時間：時間：O(n) /已排序已排序23max:iikkmmimmfAffaAaAsfsAaA活動已按完成時間有序總是當前 中所有活動的最大完成時間： 當加入 時，也大于 中所有活動的完成時間，即與 中所有活動相容.活動選擇問題活動選擇問題n作業：作業：Ex16.1-32416.2貪心策略要點貪心策略要點 貪心算法是通過做一系列選擇來獲得最優解，在算貪心算法是通過做一系列選擇來獲得最優解，在算法里的每一個決策點上，都力圖選擇最好的方案，這種法里的每一個決策點上，都力圖選擇最好的方案，這種啟發式策略并非總能產生最優解。啟發式策略并非總能產生最

20、優解。n 上節介紹的貪心算法的步驟上節介紹的貪心算法的步驟v確定問題的最優子結構確定問題的最優子結構v給出遞歸解（指遞歸方程）給出遞歸解（指遞歸方程）v證明在遞歸的每一步，有一個最優的選擇是貪心的證明在遞歸的每一步，有一個最優的選擇是貪心的選擇，因此做出這種選擇是安全的。選擇，因此做出這種選擇是安全的。v證明除了貪心選擇導出的子問題外，其余子問題都證明除了貪心選擇導出的子問題外，其余子問題都是空集合是空集合v根據貪心策略寫出遞歸算法根據貪心策略寫出遞歸算法v將遞歸算法轉換為迭代算法將遞歸算法轉換為迭代算法2516.2 貪心策略要點貪心策略要點 上述步驟是以動態規劃為基礎的。實際上可改進它，重上

21、述步驟是以動態規劃為基礎的。實際上可改進它，重點關注貪心選擇。例如，活動選擇問題可改進為（直接點關注貪心選擇。例如，活動選擇問題可改進為（直接寫出遞歸解）：寫出遞歸解）：v首先定義子問題首先定義子問題Sij，i，j均可變均可變v如果我們總是做貪心選擇，則如果我們總是做貪心選擇，則n+1不變，可省略，子問題變為：不變，可省略，子問題變為：v證明一個貪心的選擇（即選證明一個貪心的選擇（即選Si中第一個完成的活動中第一個完成的活動am），和剩余子問題），和剩余子問題Sm（與（與am相容）的最優解結合，相容）的最優解結合，能產生能產生Si的最優解。的最優解。261, niijSS:/ /ikikiiS

22、aSfsSa表示 完成后開始的任務集16.2 貪心策略要點貪心策略要點n 貪心算法的一般設計步驟貪心算法的一般設計步驟v 將優化問題分解為做出一種選擇及留下一個將優化問題分解為做出一種選擇及留下一個待解的子問題待解的子問題v 證明對于原問題總是存在一個最優解會做出證明對于原問題總是存在一個最優解會做出貪心選擇，從而保證貪心選擇是安全的貪心選擇，從而保證貪心選擇是安全的v 驗證當做出貪心選擇之后，它和剩余的一個驗證當做出貪心選擇之后，它和剩余的一個子問題的最優解組合在一起，構成了原問題子問題的最優解組合在一起，構成了原問題的最優解的最優解n 沒有一個一般的方法告訴我們一個貪心算法是否沒有一個一般

23、的方法告訴我們一個貪心算法是否會解決一個特殊的最優問題，但是有兩個要素有會解決一個特殊的最優問題，但是有兩個要素有助于使用貪心算法：助于使用貪心算法： 貪心選擇性質，貪心選擇性質， 最優子結構最優子結構2716.2 貪心策略要點貪心策略要點1、貪心選擇性質、貪心選擇性質v 貪心選擇性質：一個全局最優解能夠通過局部最貪心選擇性質：一個全局最優解能夠通過局部最優（貪心）選擇達到優（貪心）選擇達到v 貪心法總是在當前步驟上選擇最優決策，然后解貪心法總是在當前步驟上選擇最優決策，然后解由此產生的子問題由此產生的子問題v 貪心選擇只依賴了目前所做的選擇，但不依賴于貪心選擇只依賴了目前所做的選擇，但不依賴

24、于將來的選擇及子問題的解將來的選擇及子問題的解v 自頂向下，每做一次貪心選擇，就將子問題變得自頂向下，每做一次貪心選擇，就將子問題變得更小更小v 貪心算法一般總存在相應的動態規劃解，但貪心貪心算法一般總存在相應的動態規劃解，但貪心法的效率更高，原因：法的效率更高，原因： 對輸入做預處理對輸入做預處理使用合適的數據結構（如優先隊列）使用合適的數據結構（如優先隊列）2816.2 貪心策略要點貪心策略要點2、最優子結構、最優子結構vv和動態規劃一樣，該性質也是貪心法的一個關鍵要素和動態規劃一樣，該性質也是貪心法的一個關鍵要素 例如，活動選擇問題的動態規劃解中：例如，活動選擇問題的動態規劃解中：vv對

25、貪心算法更直接對貪心算法更直接29的最優解和包含則若的最優解kjikijijkijijSSAAaAS,原問題的最優解貪心選擇子問題的最優解通常可使用歸納法證明在每一步上做貪心選擇可產生最優解，由此可導出最優子結構16.2 貪心策略要點貪心策略要點3、貪心法與動態規劃的比較、貪心法與動態規劃的比較v 相同點：兩種方法都利用了最優子結構特征相同點：兩種方法都利用了最優子結構特征v 易錯誤處：易錯誤處： 當貪心算法滿足全局最優時，可能我們試圖使當貪心算法滿足全局最優時，可能我們試圖使用動態規劃求解，但前者更有效用動態規劃求解，但前者更有效 當實事上只有動態規劃才能求解時，錯誤地使當實事上只有動態規劃

26、才能求解時，錯誤地使用了貪心法用了貪心法 為了說明兩種技術的細微區別，請看一個古典優化問為了說明兩種技術的細微區別，請看一個古典優化問題的兩個變種：題的兩個變種：背包問題：背包問題：n個物品重個物品重w1,w2,wn,背包可放入重量背包可放入重量W，問能否從，問能否從n件物品中選擇若干件放入背包，使重量件物品中選擇若干件放入背包，使重量和正好等于和正好等于W。3016.2 貪心策略要點貪心策略要點n 0-1背包問題和零頭背包問題背包問題和零頭背包問題v 0-1背包：某物品拿與不拿背包：某物品拿與不拿(1,0的選擇的選擇)v 零頭背包：某物品可取部分裝包零頭背包：某物品可取部分裝包想象：小偷偷東

27、西，包容量有限，想盡可能使偷走的想象：小偷偷東西，包容量有限，想盡可能使偷走的東西總價值最大，東西總價值最大，0-1背包偷走的是金條之類物品，背包偷走的是金條之類物品，零頭背包偷走的是金粉之類物品。零頭背包偷走的是金粉之類物品。31個物品互不相同，可理解為不允許一物品多次裝包重量內含有價值最大，且總怎樣選物品裝包使得包磅（整數）為整數，背包載重量：和磅，重量件物品價值；第物品件數：nWWwvwviniiii$16.2 貪心策略要點貪心策略要點n 兩個背包問題都具有最優子結構兩個背包問題都具有最優子結構v0-1背包問題背包問題原問題的最優解：設背包中裝有重量至多為原問題的最優解：設背包中裝有重量

28、至多為W磅的磅的最有價值的若干物品；最有價值的若干物品；子問題的最優解：從原問題的最優解中去掉某物品子問題的最優解：從原問題的最優解中去掉某物品j，則包中剩余物品應是除，則包中剩余物品應是除j外，取自原外，取自原n-1件物品中件物品中最有價值，且總重不超過最有價值，且總重不超過W-wj的若干物品。的若干物品。顯然，原問題分解為子問題時，原問題的最優解也顯然，原問題分解為子問題時，原問題的最優解也要求子問題的解最優要求子問題的解最優3216.2 貪心策略要點貪心策略要點v零頭背包零頭背包子問題：從背包中去掉物品子問題：從背包中去掉物品j，重量為，重量為w(該物品該物品剩余剩余wj-w)，則包中剩

29、余物品應是除，則包中剩余物品應是除j之外，取自之外，取自原原n-1件物品以及物品件物品以及物品j的的wj-w部分中最有價值且部分中最有價值且總重至多為總重至多為W-w的若干物品的若干物品顯然，原問題解最優亦要求子問題的解最優顯然，原問題解最優亦要求子問題的解最優3316.2 貪心策略要點貪心策略要點n 兩個背包問題的不同解法兩個背包問題的不同解法v0-1背包只能用動態規劃求解背包只能用動態規劃求解按每磅價值按每磅價值(vi/wi)排序排序貪心選擇策略：取單位價值最大者裝包，若裝不貪心選擇策略：取單位價值最大者裝包，若裝不下，考慮下一單位價值最大的物品，直至包裝滿下，考慮下一單位價值最大的物品，

30、直至包裝滿或所有物品都考慮過為止或所有物品都考慮過為止實際上，裝入當前每磅價值最大者只能保證當前實際上，裝入當前每磅價值最大者只能保證當前最優（局部最優），然而放棄它可能使得后續選最優（局部最優），然而放棄它可能使得后續選擇更優。所以在裝包前，應將某物品裝包的子問擇更優。所以在裝包前，應將某物品裝包的子問題的解和放棄它的子問題的解進行比較，這將導題的解和放棄它的子問題的解進行比較，這將導致許多重疊子問題，這正是動態規劃的特點。致許多重疊子問題，這正是動態規劃的特點。343516.2 貪心策略要點貪心策略要點v零頭背包：可用貪心算法求出最優解零頭背包：可用貪心算法求出最優解3616.3 Huff

31、man編碼編碼n略略3716.4 貪心算法的理論基礎貪心算法的理論基礎 該理論可用來確定貪心法何時能產生最優解該理論可用來確定貪心法何時能產生最優解，它用到了一種組合結構：，它用到了一種組合結構：matroid（胚）。該（胚）。該結構是結構是Whitney于于1935年在研究矩陣中線性無關年在研究矩陣中線性無關結構時抽象出來的，有結構時抽象出來的，有Korte于于80年代初將該理年代初將該理論發展為貪心算法理論。該理論覆蓋了許多貪心論發展為貪心算法理論。該理論覆蓋了許多貪心法的應用實例，但并未覆蓋所有情況（如活動選法的應用實例，但并未覆蓋所有情況（如活動選擇問題），但它仍在發展。擇問題），但它

32、仍在發展。3816.4.1 胚胚n Def：一個胚是滿足下列條件的有序對：一個胚是滿足下列條件的有序對M=(S,I)v S是一有窮非空集是一有窮非空集v I是是S的一個非空子集（稱為的一個非空子集（稱為S的獨立子集）的獨立子集）簇，使得若簇，使得若BI且且AB，則，則A I。滿足此性。滿足此性質的質的I是遺傳的，即是遺傳的，即B獨立（指獨立（指BI ），則），則B的的子集也獨立。注意子集也獨立。注意I。 若若AI，BI且且|A|0w(x)0，若權最大的獨立子集若權最大的獨立子集A不是不是最大獨立子集，可將其擴張至最大獨立子集，后者最大獨立子集，可將其擴張至最大獨立子集，后者的權更大，使的權更大

33、，使A的權非最大的權非最大4616.4.2 加權胚上的貪心算法加權胚上的貪心算法v例例47000( ,)( )0( )( )( )0,:( )(1)( )GGGGV EMSTGww eMww eww ewMeEw eMAGMSTpfAw AVww AA ，求連通無向圖的問題加權胚中求權最大的獨立子集問題。即：求胚的最優子集設 的權函數 定義為邊的長度，且加權胚的權定義為：，大于各邊的最大長度。在中，故的每個最優子集 是 的一棵是胚的最大獨立子集它是一棵生成樹，它的權為也是權最大的獨立子集( )( )MSTw Aw AAG，最大必有最小，即 是 的一棵16.4.2 加權胚上的貪心算法加權胚上的貪

34、心算法n 加權胚的貪心算法加權胚的貪心算法v適用于任何加權胚求最優子集適用于任何加權胚求最優子集Av貪心之處：盡可能選權值最大的元素擴充到貪心之處：盡可能選權值最大的元素擴充到A4849(,)/ /( , ); ( ) ( ) / / /;Greedy M wMS IwAwS MforxS Mw xdoifAxI MthenAAxxAxreturnA輸入胚， 表示正的權函數按權 單調遞減對排序每個，按單調遞減 ； 擴充 未破壞 的獨立性否則放棄50( lg ) ( ( ),( lg( )SnO nnfornAxO f nO nnnf n時間分析：設，排序循環 次，每次檢驗是否獨立，設檢查時間為

35、總時間為16.4.2 加權胚上的貪心算法加權胚上的貪心算法16.4.2 加權胚上的貪心算法加權胚上的貪心算法n Greedy算法返回算法返回1個最優子集個最優子集A是獨立子集易從是獨立子集易從獨立開始用歸納法證明獨立開始用歸納法證明vLemma16.7 （胚呈現貪心選擇性質）（胚呈現貪心選擇性質）設設M=(S,I)是加權胚，權函數為是加權胚，權函數為w，且，且S已按權值的已按權值的單調遞減有序，設單調遞減有序，設x是是S的第一個使的第一個使x獨立的元素獨立的元素（若這樣的（若這樣的x存在）。若存在）。若x存在，則存在存在，則存在S的一個最的一個最優子集優子集A包含包含x。（即說明第一步貪心選擇

36、正確）。（即說明第一步貪心選擇正確）51:(1)(2)pfxBSxBAB若無這樣的 存在，則唯一的獨立子集是否則，設 為 的任一非空最優子集 若，則令，證畢；16.4.2 加權胚上的貪心算法加權胚上的貪心算法52( )( ) ( )( ) ( )( )xBBAxw Aw BiyBw xw yyByBBSBIyxSSw xw y 若，則可從 構造一個最優子集 ， 使其包含 ，為此需證先證，有 由于 是 的最優子集，故 也是獨立子集， 由 的遺傳性知亦是獨立子集是 的第一個獨立子集， 而 中元素已按單調減有序,53) , )( )( )( )( )( )iiAxAAxABAAABAByxyiw A

37、w Bw yw xw BBAx構造集 ，使其包含 且 最優 開始令顯然 是獨立， 利用交換性質，重復地在 中找新的元素 擴充到 使 獨立，直至。于是有： 對某個 成立 由 立即知道： 由 是最優子集即可知 亦是最優子集， 且它包括 。16.4.2 加權胚上的貪心算法加權胚上的貪心算法 下面的引理和推論說明：若一元素開始未被選中，下面的引理和推論說明：若一元素開始未被選中，則此后亦不可能被選中則此后亦不可能被選中vLemma16.8 設設M=(S,I)是任一胚，若是任一胚，若S的一個元素的一個元素x是是S的某個獨立子集的某個獨立子集A的一個擴張，則的一個擴張，則x亦是亦是的一個的一個擴張擴張54

38、的一個擴張是獨立的，它是的遺傳性知，由的擴張是:xIIxAAxpf16.4.2 加權胚上的貪心算法加權胚上的貪心算法v推論推論16.9 設設M=(S,I)是任一胚，若是任一胚，若S的一個元素的一個元素x不是不是的擴張，則的擴張，則x也不是也不是S的任何獨立子集的任何獨立子集A的一個擴張的一個擴張 pf：由引理：由引理16.8易證易證v該推論告訴我們，若一開始某元素沒被選中，此后亦該推論告訴我們，若一開始某元素沒被選中，此后亦不會選中，保證不會選中，保證Greedy算法開始的正確性算法開始的正確性5516.4.2 加權胚上的貪心算法加權胚上的貪心算法v引理引理16.10（胚具有最優子結構性質）（

39、胚具有最優子結構性質）對于加權胚對于加權胚M=(S,I)，設，設x是是Greedy算法選中的第一個算法選中的第一個元素，找一個包含元素，找一個包含x的權最大的獨立子集的剩余問題可的權最大的獨立子集的剩余問題可歸結為找加權胚歸結為找加權胚M=(S,I)的一個權值最大的獨立子集的一個權值最大的獨立子集，這里：，這里：且且M的權函數是的權函數是M的權函數，但只限于的權函數，但只限于S。我們稱。我們稱M是是由元素由元素x引起的引起的M的收縮，它是的收縮，它是M的子問題。的子問題。56: , / / : / /SySx yISSxIBSxBxIISx即由 中可擴張至中的元素構成即 是由 的不包含 的獨立

40、子集構成57: ( )()(x)() pfAMxIAAxMMAMAAxw Aw AwxAMw AAMAMAMxA若 是的任一包含 的最優子集（即權最大的獨立子集），則由 的定義可知： 是的一個獨立子集，反之，的任一獨立子集產生的一個獨立子集：兩種情況下，均有包含 的 是中權最大的獨立子集，保證了須最大，即是的最優子集，反之亦然即： 是原問題的最優解要求是子問題的最優解；反之，A構成原問題的最優解16.4.2 加權胚上的貪心算法加權胚上的貪心算法vTh16.11 （胚的貪心算法的正確性）（胚的貪心算法的正確性） 若若 M = ( S , I ) 是 權 函 數 為是 權 函 數 為 w 的 加

41、權 胚 ， 則 調 用的 加 權 胚 ， 則 調 用Greedy(M,w)將返回一個最優子集將返回一個最優子集 pf:由推論由推論16.9知，一開始被忽略的元素可以放棄，因知，一開始被忽略的元素可以放棄，因為它們不是為它們不是的擴張意味著此后也不會是任何獨立的擴張意味著此后也不會是任何獨立子集的擴張。子集的擴張。一旦一個元素一旦一個元素x被選中，引理被選中，引理16.7保證了算法將其保證了算法將其擴充到擴充到A中是正確的，因為存在一個最優子集包含中是正確的，因為存在一個最優子集包含x。5816.4.2 加權胚上的貪心算法加權胚上的貪心算法引理引理16.10蘊含著剩余子問題是在蘊含著剩余子問題是

42、在M中找一最優子中找一最優子集。在集。在Greedy將將A置為置為x之后，剩下的各步驟可之后，剩下的各步驟可解釋為是在胚解釋為是在胚M中進行的，因為中進行的，因為 B BII ，B在在M中中獨立等價于獨立等價于Bx在在M中獨立。因此，中獨立。因此，Greedy的的后續操作將找出后續操作將找出M的一個最優子集（可用歸納的一個最優子集（可用歸納法），法），Greedy的全部操作可以找到的全部操作可以找到M的最優子集的最優子集n 若一應用問題能抽象為加權胚，則一定能用貪心法求若一應用問題能抽象為加權胚，則一定能用貪心法求出其最優解出其最優解5916.5 一個任務調度問題一個任務調度問題n 問題描述問

43、題描述在單處理器上對單位時間任務進行最優調度在單處理器上對單位時間任務進行最優調度v輸入輸入任務集：任務集：S=a1,a2,an，每個任務在單位時間內，每個任務在單位時間內完成，總時間為完成，總時間為n截止期：截止期： a ai iSS，a ai i的截止期的截止期di為整數，且為整數，且1din，即，即a ai i須在須在di或或di時刻之前完成時刻之前完成權（罰款）：權（罰款）： a ai iSS，ai的權的權wi0，表示，表示ai沒有在沒有在di或或di之前完成所導致的罰款，但提前完成或按時之前完成所導致的罰款，但提前完成或按時完成的任務沒有罰款完成的任務沒有罰款v輸出：求出輸出：求出S

44、的一個調度，使總罰款最小的一個調度，使總罰款最小 顯然顯然S的任意枚舉都是一個調度方案，在總時間的任意枚舉都是一個調度方案，在總時間n內肯定完成，內肯定完成，但我們力圖使延期完成的任務權值和最小但我們力圖使延期完成的任務權值和最小6016.5 一個任務調度問題一個任務調度問題n 將問題抽象為加權胚將問題抽象為加權胚v早任務：在給定的調度中，能按期或提前完成的任早任務：在給定的調度中，能按期或提前完成的任務（即在務（即在deadline之前完成任務）之前完成任務）v遲任務：在給定的調度中，在截止期之后完成的任遲任務：在給定的調度中，在截止期之后完成的任務務v早任務優先形式：將早任務排在遲任務之前

45、的調度早任務優先形式：將早任務排在遲任務之前的調度v任何調度均可安排成早任務優先形式任何調度均可安排成早任務優先形式例：例：ajaj aiaj 遲遲 早早 早早 遲遲交換位置不影響交換位置不影響ai和和aj的早遲特性，即總罰款不變的早遲特性，即總罰款不變6116.5 一個任務調度問題一個任務調度問題v調度的規范形式調度的規范形式 早任務在前、遲任務在后（即先將其按早任務優早任務在前、遲任務在后（即先將其按早任務優先形式調度）；并且將所有早任務按先形式調度）；并且將所有早任務按deadline單單調增次序調度（遲任務可按任意次序調度）。調增次序調度（遲任務可按任意次序調度）。v規范形式的調度不改

46、變任務的早遲特性，因此任規范形式的調度不改變任務的早遲特性，因此任何調度均可安排成該形式而保持總罰款不變何調度均可安排成該形式而保持總罰款不變 例：例：6216.5 一個任務調度問題一個任務調度問題 這里這里s1。在規范形勢下，。在規范形勢下，ai應和應和aj交換：交換：1.aj交換后，其完成時間由交換后，其完成時間由k+s提前至提前至k，仍是早，仍是早任務任務2.交換前交換前aj是早任務，即是早任務，即k+sdj，由，由djdi知知k+sdj16.5 一個任務調度問題一個任務調度問題v最優調度的規范次序最優調度的規范次序 因為任一調度都有一規范形式，所以最優調度因為任一調度都有一規范形式，所

47、以最優調度也存在規范形式也存在規范形式 在最優調度在最優調度S中找出早任務集中找出早任務集A 將將A中任務按中任務按deadlines遞增序排列遞增序排列 遲任務集遲任務集S-A可按任意序排列可按任意序排列注意：注意： 因為早任務不導致罰款，遲任務的次序也不因為早任務不導致罰款，遲任務的次序也不改變罰款的多少（權的大小），所以上述安改變罰款的多少（權的大小），所以上述安排不改變最優調度的權值排不改變最優調度的權值6416.5 一個任務調度問題一個任務調度問題v獨立任務集獨立任務集 若存在一個調度使得任務集若存在一個調度使得任務集A中沒有遲任務，則稱中沒有遲任務，則稱A是獨立的。是獨立的。 下面的引理可判定一給定任務集下面的引理可判定一給定任務集A是否獨立，為此是否獨立，為此先給出一個定義。先給出一個定義。Def：對：