計算機算法設計與分析_第4章_貪心算法

1、 設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間si, fi)內占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。下面給出解活動安排問題的貪心算法GreedySelectorGreedySelector :各活動的起始時間和結各活動的起始時間和結束時間存儲于數(shù)組束時間存儲于數(shù)組s s和和f f中且按結束時間的非減中

2、且按結束時間的非減序排列序排列 所謂貪心選擇性質貪心選擇性質是指所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上自底向上的方式解各子問題，而貪心算法則通常以自頂向下自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。2 2、最優(yōu)子結構性質、最優(yōu)子結構性質3、貪心算法與動態(tài)規(guī)劃算法的差異 在選擇裝入背包的物

3、品時，對每種物品在選擇裝入背包的物品時，對每種物品i i只有只有2 2種選擇，即種選擇，即裝入背包或不裝入背包。不能將物品裝入背包或不裝入背包。不能將物品i i裝入背包多次，也不能只裝入背包多次，也不能只裝入部分的物品裝入部分的物品i i。 這2類問題都具有最優(yōu)子結構最優(yōu)子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 用貪心算法解背包問題的基本步驟： 算法算法knapsackknapsack的的主要計算時間在于將主要計算時間在于將各種物品依其單位重各種物品依其單位重量的價值從大到小排量的價值從大到小排序。因此，算法的計序。因此，算法的計算時間上界為算時間上界為O O（nlognnlogn）。）。為了證明算法的正確為了證明算法的正確性，還必須證明背包性，還必須證明背包問題具有貪心選擇性問題具有貪心選擇性質質。)()()(cdcfTBTCc Dijkstra算法的迭代過程： )(nO)(2nO)(2nO)(2nO)log(eeO)(2ne)(2noe 約定，每個作業(yè)均可在任何一臺機器上加工處理，但未約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。mn mn ),(GGGISMAxxWAW)()