1.2 算法思想
2019-11-17 05:46:01
供稿：網友
在貪婪算法（greedy method）中采用逐步構造最優解的方法。在每個階段，都作出一個看上去最優的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據稱為貪婪準則（greedy criterion）。 例1-4 [找零錢] 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。 假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。 貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證實采用上述貪婪算法找零錢時所用的硬幣數目的確最少（見練習1）。 例1-5 [機器調度] 現有n 件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi ，si < fi 。[si , fi ] 為處理任務i 的時間范圍。兩個任務i，j 重指兩個任務的時間范圍區間有重疊，而并非是指i，j 的起點或終點重合。例如：區間[ 1，4 ]與區間[ 2，4 ]重疊，而與區間[ 4，7 ]不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優分配是指使用的機器最少的可行分配方案。 假設有n= 7件任務，標號為a 到g。它們的開始與完成時間如圖13-1a 所示。若將任務a分給機器M1，任務b 分給機器M2，. . .，任務g 分給機器M7，這種分配是可行的分配，共使用了七臺機器。但它不是最優分配，因為有其他分配方案可使利用的機器數目更少，例如：可以將任務a、b、d分配給同一臺機器，則機器的數目降為五臺。 一種獲得最優分配的貪婪方法是逐步分配任務。每步分配一件任務，且按任務開始時間的非遞減次序進行分配。若已經至少有一件任務分配給某臺機器，則稱這臺機器是舊的；若機器非舊，則它是新的。在選擇機器時，采用以下貪婪準則：根據欲分配任務的開始時間，若此時有舊的機器可用，則將任務分給舊的機器。否則，將任務分配給一臺新的機器。 根據例子中的數據，貪婪算法共分為n = 7步，任務分配的順序為a、f、b、c、g、e、d。第一步沒有舊機器，因此將a 分配給一臺新機器（比如M1）。這臺機器在0到2時刻處于忙狀態。在第二步，考慮任務f。由于當f 啟動時舊機器仍處于忙狀態，因此將f 分配給一臺新機器(設為M2 )。第三步考慮任務b, 由于舊機器M1在Sb = 3時刻已處于閑狀態，因此將b分配給M1執行，M1下一次可用時刻變成fb = 7，M2的可用時刻變成ff = 5。第四步，考慮任務c。由于沒有舊機器在Sc = 4時刻可用，因此將c 分配給一臺新機器（M3），這臺機器下一次可用時間為fc = 7。第五步考慮任務g，將其分配給機器M2，第六步將任務e 分配給機器M1, 最后在第七步，任務2分配給機器M3。（注重：任務d 也可分配給機器M2）。 上述貪婪算法能導致最優機器分配的證實留作練習（練習7）。可按如下方式實現一個復雜性為O (nl o gn)的貪婪算法：首先采用一個復雜性為O (nl o gn)的排序算法（如堆排序）按Si 的遞增次序排列各個任務，然后使用一個關于舊機器可用時間的最小堆。 例1-6 [最短路徑] 給出一個有向網絡，路徑的長度定義為路徑所經過的各邊的耗費之和。要求找一條從初始頂點s 到達目的頂點d 的最短路徑。 貪婪算法分步構造這條路徑，每一步在路徑中加入一個頂點。假設當前路徑已到達頂點q， 且頂點q 并不是目的頂點d。加入下一個頂點所采用的貪婪準則為：選擇離q 最近且目前不在路徑中的頂點。 這種貪婪算法并不一定能獲得最短路徑。例如，假設在圖1 3 - 2中希望構造從頂點1到頂點5的最短路徑，利用上述貪婪算法，從頂點1開始并尋找目前不在路徑中的離頂點1最近的頂點。到達頂點3，長度僅為2個單位，從頂點3可以到達的最近頂點為4，從頂點4到達頂點2，最后到達目的頂點5。所建立的路徑為1 , 3 , 4 , 2 , 5，其長度為1 0。這條路徑并不是有向圖中從1到5的最短路徑。事實上，有幾條更短的路徑存在，例如路徑1，4，5的長度為6。 根據上面三個例子，回想一下前幾章所考察的一些應用，其中有幾種算法也是貪婪算法。例如，霍夫曼樹算法，利用n- 1步來建立最小加權外部路徑的二叉樹，每一步都將兩棵二叉樹合并為一棵，算法中所使用的貪婪準則為：從可用的二叉樹中選出權重最小的兩棵。L P T調度規則也是一種貪婪算法，它用n 步來調度n 個作業。首先將作業按時間長短排序，然后在每一步中為一個任務分配一臺機器。選擇機器所利用的貪婪準則為：使目前的調度時間最短。將新作業調度到最先完成的機器上（即最先空閑的機器）。 注重到在機器調度問題中，貪婪算法并不能保證最優，然而，那是一種直覺的傾向且一般情況下結果總是非常接近最優值。它利用的規則就是在實際環境中希望人工機器調度所采用的規則。算法并不保證得到最優結果，但通常所得結果與最優解相差無幾，這種算法也稱為啟發式方法（ h e u r i s t i c s )。因此L P T方法是一種啟發式機器調度方法。定理9 - 2陳述了L P T調度的完成時間與最佳調度的完成時間之間的關系，因此L P T啟發式方法具有限定性 能（ bounded performance ）。具有限定性能的啟發式方法稱為近似算法（ a p p r o x i m a t i o na l g o r i t h m）。 本章的其余部分將介紹幾種貪婪算法的應用。在有些應用中，貪婪算法所產生的結果總是最優的解決方案。但對其他一些應用，生成的算法只是一種啟發式方法，可能是也可能不是近似算法。
