|
第 1 章 貪婪算法 雖然設計一個好的求解算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調整。但是在某些情況下，算法經過調整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。 本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應用該算法給出貨箱裝船問題、背包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。 1.1 最優(yōu)化問題 本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（ optimization problem），每個最優(yōu)化問題都包含一組限制條件（ c o n s t r a i n t）和一個優(yōu)化函數(shù)（ optimization function），符合限制條件的問題求解方案稱為可行解（ feasible solution），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（optimal solution）。 例1-1 [ 渴嬰問題] 有一個非常渴的、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n 種不同的飲料。根據(jù)以前關于這n 種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個滿意度值：飲用1盎司第i 種飲料，對它作出相對評價，將一個數(shù)值si 作為滿意度賦予第i 種飲料。 通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時并沒有足夠的量來滿足此嬰兒解渴的需要。設ai是第i 種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？ 設各種飲料的滿意度已知。令xi 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問題是： 找到一組實數(shù)xi（1≤i≤n），使n åi = 1si xi 最大，并滿足：n åi=1xi =t 及0≤xi≤ai 。 需要指出的是：如果n åi = 1ai < t，則不可能找到問題的求解方案，因為即使喝光所有的飲料也不能使嬰兒解渴。 對上述問題精確的數(shù)學描述明確地指出了程序必須完成的工作，根據(jù)這些數(shù)學公式，可以對輸入/ 輸出作如下形式的描述： 輸入：n，t，si ，ai（其中1≤i≤n，n 為整數(shù)，t、si 、ai 為正實數(shù)）。 輸出：實數(shù)xi（1≤i≤n），使n åi= 1si xi 最大且n åi=1xi =t（0≤xi≤ai）。如果n åi = 1ai <t，則輸出適當?shù)腻e誤信息。 在這個問題中，限制條件是n åi= 1xi =t 且0≤xi≤ai，1≤i≤n。而優(yōu)化函數(shù)是n åi= 1si xi 。任何滿足限制條件的一組實數(shù)xi 都是可行解，而使n åi= 1si xi 最大的可行解是最優(yōu)解。 例1-2 [裝載問題] 有一艘大船準備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第i 個貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。 這個問題可以作為最優(yōu)化問題進行描述：設存在一組變量xi ，其可能取值為0或1。如xi 為0，則貨箱i 將不被裝上船；如xi 為1，則貨箱i 將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件n åi = 1wi xi ≤c 且x i Î {0, 1}, 1 ≤i≤n。相應的優(yōu)化函數(shù)是n åi= 1xi 。 滿足限制條件的每一組xi 都是一個可行解，能使n åi= 1xi 取得最大值的方案是最優(yōu)解。 例1-3 [最小代價通訊網絡] 城市及城市之間所有可能的通信連接可被視作一個無向圖，圖的每條邊都被賦予一個權值，權值表示建成由這條邊所表示的通信連接所要付出的代價。包含圖中所有頂點（城市）的連通子圖都是一個可行解。設所有的權值都非負，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解是其中具有最小代價的生成樹。 在這個問題中，需要選擇一個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權值之和。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:37:49 b 等級：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊：2003-8-28 第 2 樓 1.2 算法思想 在貪婪算法（greedy method）中采用逐步構造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準則（greedy criterion）。 例1-4 [找零錢] 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應使零錢總數(shù)超過最終所需的數(shù)目。 假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過6 7美分），第三枚應選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。 貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時所用的硬幣數(shù)目的確最少（見練習1）。 例1-5 [機器調度] 現(xiàn)有n 件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi ，si < fi 。[si , fi ] 為處理任務i 的時間范圍。兩個任務i，j 重指兩個任務的時間范圍區(qū)間有重疊，而并非是指i，j 的起點或終點重合。例如：區(qū)間[ 1，4 ]與區(qū)間[ 2，4 ]重疊，而與區(qū)間[ 4，7 ]不重疊。一個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。 假設有n= 7件任務，標號為a 到g。它們的開始與完成時間如圖13-1a 所示。若將任務a分給機器M1，任務b 分給機器M2，. . .，任務g 分給機器M7，這種分配是可行的分配，共使用了七臺機器。但它不是最優(yōu)分配，因為有其他分配方案可使利用的機器數(shù)目更少，例如：可以將任務a、b、d分配給同一臺機器，則機器的數(shù)目降為五臺。 一種獲得最優(yōu)分配的貪婪方法是逐步分配任務。每步分配一件任務，且按任務開始時間的非遞減次序進行分配。若已經至少有一件任務分配給某臺機器，則稱這臺機器是舊的；若機器非舊，則它是新的。在選擇機器時，采用以下貪婪準則：根據(jù)欲分配任務的開始時間，若此時有舊的機器可用，則將任務分給舊的機器。否則，將任務分配給一臺新的機器。 根據(jù)例子中的數(shù)據(jù)，貪婪算法共分為n = 7步，任務分配的順序為a、f、b、c、g、e、d。第一步沒有舊機器，因此將a 分配給一臺新機器（比如M1）。這臺機器在0到2時刻處于忙狀態(tài)。在第二步，考慮任務f。由于當f 啟動時舊機器仍處于忙狀態(tài)，因此將f 分配給一臺新機器(設為M2 )。第三步考慮任務b, 由于舊機器M1在Sb = 3時刻已處于閑狀態(tài)，因此將b分配給M1執(zhí)行，M1下一次可用時刻變成fb = 7，M2的可用時刻變成ff = 5。第四步，考慮任務c。由于沒有舊機器在Sc = 4時刻可用，因此將c 分配給一臺新機器（M3），這臺機器下一次可用時間為fc = 7。第五步考慮任務g，將其分配給機器M2，第六步將任務e 分配給機器M1, 最后在第七步，任務2分配給機器M3。（注意：任務d 也可分配給機器M2）。 上述貪婪算法能導致最優(yōu)機器分配的證明留作練習（練習7）?？砂慈缦路绞綄崿F(xiàn)一個復雜性為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。 根據(jù)上面三個例子，回想一下前幾章所考察的一些應用，其中有幾種算法也是貪婪算法。例如，霍夫曼樹算法，利用n- 1步來建立最小加權外部路徑的二叉樹，每一步都將兩棵二叉樹合并為一棵，算法中所使用的貪婪準則為：從可用的二叉樹中選出權重最小的兩棵。L P T調度規(guī)則也是一種貪婪算法，它用n 步來調度n 個作業(yè)。首先將作業(yè)按時間長短排序，然后在每一步中為一個任務分配一臺機器。選擇機器所利用的貪婪準則為：使目前的調度時間最短。將新作業(yè)調度到最先完成的機器上（即最先空閑的機器）。 注意到在機器調度問題中，貪婪算法并不能保證最優(yōu)，然而，那是一種直覺的傾向且一般情況下結果總是非常接近最優(yōu)值。它利用的規(guī)則就是在實際環(huán)境中希望人工機器調度所采用的規(guī)則。算法并不保證得到最優(yōu)結果，但通常所得結果與最優(yōu)解相差無幾，這種算法也稱為啟發(fā)式方法（ h e u r i s t i c s )。因此L P T方法是一種啟發(fā)式機器調度方法。定理9 - 2陳述了L P T調度的完成時間與最佳調度的完成時間之間的關系，因此L P T啟發(fā)式方法具有限定性 能（ bounded performance ）。具有限定性能的啟發(fā)式方法稱為近似算法（ a p p r o x i m a t i o na l g o r i t h m）。 本章的其余部分將介紹幾種貪婪算法的應用。在有些應用中，貪婪算法所產生的結果總是最優(yōu)的解決方案。但對其他一些應用，生成的算法只是一種啟發(fā)式方法，可能是也可能不是近似算法。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:12 b 等級：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊：2003-8-28 第 3 樓 練習 1. 證明找零錢問題（例1 3 - 4）的貪婪算法總能產生具有最少硬幣數(shù)的零錢。 2. 考慮例1 3 - 4的找零錢問題，假設售貨員只有有限的2 5美分， 1 0美分， 5美分和1美分的硬幣，給出一種找零錢的貪婪算法。這種方法總能找出具有最少硬幣數(shù)的零錢嗎？證明結論。 3. 擴充例1 3 - 4的算法，假定售貨員除硬幣外還有50, 20, 10, 5, 和1美元的紙幣，顧客買價格為x 美元和y 美分的商品時所付的款為u 美元和v 美分。算法總能找出具有最少紙幣與硬幣數(shù)目的零錢嗎？證明結論。 4. 編寫一個C + +程序實現(xiàn)例1 3 - 4的找零錢算法。假設售貨員具有面值為1 0 0，2 0，1 0，5和1美元的紙幣和各種硬幣。程序可包括輸入模塊（即輸入所買商品的價格及顧客所付的錢數(shù)），輸出模塊（輸出零錢的數(shù)目及要找的各種貨幣的數(shù)目）和計算模塊（計算怎樣給出零錢）。 5. 假設某個國家所使用硬幣的幣值為1 4 , 2 , 5和1分，則例1 3 - 4的貪婪算法總能產生具有最少硬幣數(shù)的零錢嗎？證明結論。 6. 1) 證明例1 3 - 5的貪婪算法總能找到最優(yōu)任務分配方案。 2) 實現(xiàn)這種算法，使其復雜性為O (nl o gn)（提示：根據(jù)完成時間建立最小堆）。 *7. 考察例1 3 - 5的機器調度問題。假定僅有一臺機器可用，那么將選擇最大數(shù)量的任務在這臺機器上執(zhí)行。例如，所選擇的最大任務集合為{a,b,e}。解決這種任務選擇問題的貪婪算法可按步驟選擇任務，每步選擇一個任務，其貪婪準則如下：從剩下的任務中選擇具有最小的完成時間且不會與現(xiàn)有任務重疊的任務。 1) 證明上述貪婪算法能夠獲得最優(yōu)選擇。 2) 實現(xiàn)該算法，其復雜性應為O(nl o gn)。（提示：采用一個完成時間的最小堆） ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:26 b 等級：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國 注冊：2003-8-28 第 4 樓 1.3 應用 1.3.1 貨箱裝船 這個問題來自例1 - 2。船可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據(jù)這種思想可利用如下貪婪準則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。 例1-7 假設n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用貪婪算法時，所考察貨箱的順序為7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。貨箱7 , 3 , 6 , 8 , 4 , 1的總重量為3 9 0個單位且已被裝載，剩下的裝載能力為1 0個單位，小于剩下的任何一個貨箱。在這種貪婪解決算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且åxi = 6。 定理1-1 利用貪婪算法能產生最佳裝載。 證明可以采用如下方式來證明貪婪算法的最優(yōu)性：令x = [x1 , ..., xn ]為用貪婪算法獲得的解，令y =[ y1 , ..., yn ]為任意一個可行解，只需證明n åi= 1xi ≥n åi= 1yi 。不失一般性，可以假設貨箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分幾步將y 轉化為x，轉換過程中每一步都產生一個可行的新y，且n åi = 1yi 大于等于未轉化前的值，最后便可證明n åi = 1xi ≥n åj = 1yi 。 根據(jù)貪婪算法的工作過程，可知在[0, n] 的范圍內有一個k，使得xi =1, i≤k且xi =0, i>k。尋找[ 1 ,n]范圍內最小的整數(shù)j，使得xj≠yj 。若沒有這樣的j 存在，則n åi= 1xi =n åi = 1yi 。如果有這樣的j 存在，則j≤k，否則y 就不是一個可行解，因為xj≠yj ，xj = 1且yj = 0。令yj = 1，若結果得到的y 不是可行解，則在[ j+ 1 ,n]范圍內必有一個l 使得yl = 1。令yl = 0，由于wj≤wl ，則得到的y 是可行的。而且，得到的新y 至少與原來的y 具有相同數(shù)目的1。 經過數(shù)次這種轉化，可將y 轉化為x。由于每次轉化產生的新y 至少與前一個y 具有相同數(shù)目的1，因此x 至少與初始的y 具有相同的數(shù)目1。貨箱裝載算法的C + +代碼實現(xiàn)見程序1 3 - 1。由于貪婪算法按貨箱重量遞增的順序裝載，程序1 3 - 1首先利用間接尋址排序函數(shù)I n d i r e c t S o r t對貨箱重量進行排序（見3 . 5節(jié)間接尋址的定義），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時間為O (nl o gn)（也可利用9 . 5 . 1節(jié)的堆排序及第2章的歸并排序），算法其余部分所需時間為O (n)，因此程序1 3 - 1的總的復雜性為O (nl o gn)。 程序13-1 貨箱裝船 template<class T> void ContainerLoading(int x[], T w[], T c, int n) {// 貨箱裝船問題的貪婪算法 // x[i] = 1 當且僅當貨箱i被裝載， 1<=i<=n // c是船的容量, w 是貨箱的重量 // 對重量按間接尋址方式排序 // t 是間接尋址表 int *t = new int [n+1]; I n d i r e c t S o r t ( w, t, n); // 此時, w[t[i]] <= w[t[i+1]], 1<=i<n // 初始化x for (int i = 1; i <= n; i++) x[i] = 0; // 按重量次序選擇物品 for (i = 1; i <= n && w[t[i]] <= c; i++) { x[t[i]] = 1; c -= w[t[i]];} // 剩余容量 delete [] t; } ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
|
|
|
來自： 絕地戰(zhàn)士 > 《我的圖書館》
