1、會計學1 貪心算法貪心算法Greedy 一、貪心法的設計思想一、貪心法的設計思想 貪心法把構造可行解的工作分成許多階段來完成. 在各個階段,選擇那些在某些意義下是局部最優 的方案,期望各階段的局部最優的選擇帶來整體 最優. 第1頁/共25頁 n貪心算法總是作出在當前看來最好的選擇。 n貪心算法并不從整體最優考慮，它所作出的選擇 只是在某種意義上的局部最優選擇。 n雖然貪心算法不能對所有問題都得到整體最優解， 但對許多問題它能產生整體最優解。如單源最短 路徑問題，最小生成樹問題等。在一些情況下， 即使貪心算法不能得到整體最優解，其最終結果 卻是最優解的很好近似。 第2頁/共25頁 例活動安排問題

2、例活動安排問題 活動安排問題就是要在所給 的活動集合中選出最大的相容活 動子集合。該問題要求高效地安 排一系列爭用某一公共資源的活 動。 第3頁/共25頁 活動安派問題就是在所給的活動集合中選出最大的相容活動安派問題就是在所給的活動集合中選出最大的相容 活動子集合。活動子集合。 設有n個活動的集合E=1,2,n，其中每個活動都要求 使用同一資源，如演講會場等，而在同一時間內只有一個活動 能使用這一資源。每個活動i都有一個要求使用該資源的起始 時間si和一個結束時間fi,且si fi 。如果選擇了活動i，則 它在半開時間區間si, fi)內占用資源。若區間si, fi)與區 間sj, fj)不相

3、交，則稱活動i與活動j是相容的。也就是說， 當sifj或sjfi時，活動i與活動j相容。 第4頁/共25頁 下面給出解活動安排問題的貪心算法 GreedySelectorGreedySelector : 各活動的起始時間和結束時間存儲于數組s和f中，且按結束 時間的非減序排列f1f2 fn 第5頁/共25頁 第6頁/共25頁 i12345678910 11 Si 130535688212 fi45678910 11 12 13 14 第7頁/共25頁 算法greedySelector 的 計算過程如左圖所示。 圖中每行相應于算法的 一次迭代。陰影長條表 示的活動是已選入集合 A的活動，而空白長

4、條 表示的活動是當前正在 檢查相容性的活動。 第8頁/共25頁 第9頁/共25頁 二、貪心算法的基本要素二、貪心算法的基本要素 第10頁/共25頁 1 1、貪心選擇、貪心選擇 性質性質 所謂貪心選擇性質貪心選擇性質是指所求問題的整體最優解整體最優解可以 通過一系列局部最優局部最優的選擇，即貪心選擇來達到。這是 貪心算法可行的第一個基本要素，也是貪心算法與動態 規劃算法的主要區別。 動態規劃算法通常以自底向上自底向上的方式解各子問題， 而貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方 式作出相繼的貪心選擇，每作一次貪心選擇就將所求問 題簡化為規模更小的子問題。 第11頁/共25頁 當一個

5、問題的最優解包含其子問題的最優解時， 稱此問題具有最優子結構性質。問題的最優子結構性質 是該問題可用動態規劃算法或貪心算法求解的關鍵特征。 2 2、最優子結構性質、最優子結構性質 第12頁/共25頁 貪心算法和動態規劃算法都要求問題具有最優子結構 性質，這是2類算法的一個共同點。但是，對于具有最優 子結構的問題應該選用貪心算法還是動態規劃算法求解? 是否能用動態規劃算法求解的問題也能用貪心算法求解? 下面研究2個經典的組合優化問題，并以此說明貪心算法 與動態規劃算法的主要差別。 3、貪心算法與動態規劃算法的差異 第13頁/共25頁 0-1背包問題： 在選擇裝入背包的物品時，對每種物品在選擇裝入

6、背包的物品時，對每種物品i i只有只有2 2種選擇，即裝種選擇，即裝 入背包或不裝入背包。不能將物品入背包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝裝入背包多次，也不能只裝 入部分的物品入部分的物品i i。 例例2 2背包問題背包問題 第14頁/共25頁 這2類問題都具有最優子結構最優子結構性質，極為相似， 但背包問題可以用貪心算法求解，而0-1背包問題卻不 能用貪心算法求解。 第15頁/共25頁 用貪心算法解背包問題的基本步驟： 第16頁/共25頁 算法算法knapsackknapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為的主要

7、計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為 O O（nlognnlogn）。）。 為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。 第17頁/共25頁 第18頁/共25頁 有一批集裝箱要裝上一艘載重量為c的輪船。其 中集裝箱i的重量為Wi。最優裝載問題要求確定在 裝載體積不受限制的情況下，將盡可能多的集裝箱 裝上輪船。 例最優裝載 第19頁/共25頁 1. 1. 算法描述算法描述 最優裝載問題可用貪心算法求解。采用重量最輕者先裝的貪 心選擇策略，可產生最優裝載問題的最優解。具體算法描述 如下

8、頁。 第20頁/共25頁 第21頁/共25頁 例多機調度問題例多機調度問題 多機調度問題多機調度問題要求給出一種作業調度方案，使所給 的n個作業在盡可能短的時間內由m臺機器加工處理完成。 這個問題是NPNP完全問題完全問題，到目前為止還沒有有效的 解法。對于這一類問題,用貪心選擇策略貪心選擇策略有時可以設計出 較好的近似算法。 約定，每個作業均可在任何一臺機器上加工處理，但未約定，每個作業均可在任何一臺機器上加工處理，但未 完工前不允許中斷處理。作業不能拆分成更小的子作業。完工前不允許中斷處理。作業不能拆分成更小的子作業。 第22頁/共25頁 采用最長處理時間作業優先最長處理時間作業優先的貪心選擇策略可以設 計出解多機調度問題的較好的近似算法。 按此策略，當 時，只要將機器i的0, ti時間區 間分配給作業i即可，算法只需要O(1)時間。 當 時，首先將n個作業依其所需的處理時間從 大到小排序。然后依此順序將作業分配給空閑的處理機。 算法所需的計算時間為O(nlogn)。 mn mn 第23