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