Greedy:算法範式-中文百科頻道

DOTA戰隊

戰隊簡介

2012年，随着DOTA類遊戲平台《天梯排行榜》的火熱和風靡，越來越多出類拔萃的路人玩家通過天梯排行榜和各大DOTA解說視頻漸漸進入了大家的視野，引起了廣大玩家的關注。在這些天賦過人和操作精妙的路人玩家中，有一支路人戰隊漸漸被大家公認為“天梯第一黑店”，他們就是GREEDY。由前DOTA著名前職業選手Yaphets和天才少年Somnus丶M領銜。

戰隊成員

YaphetS【中文名：蔔嚴駿】

江蘇南京人，被廣大玩家稱呼為：Pis。11對戰平台常用ID：範迪塞爾__、心靈震撼丶、yaphet咆哮、别掉線阿丶。天梯最高積分記錄：2805，天梯最高排名記錄：第1名。作為DOTA英雄中影魔的冠名者，無需過多介紹，公認的路人王大神。在GREEDY中根據陣容司職1号位。

Somnus丶M【中文名：路垚】

北京昌平人，熟悉他的玩家一般喊他：Maybe。11對戰平台常用ID：Somnus丶M、丶上頭雪，哪咤丶哪咤。天梯最高積分記錄：2870，天梯最高排名記錄：第1名。新一代路人王，經常能打出非常震撼眼球的擊殺。由于還在念高中，所以被稱其為：天才少年,高中生。在GREEDY中根據陣容司職2号位。

河北唐山人，熟悉他的玩家一般喊他：少男乖、醬油乖、洗碗乖、躺箭鵬、上頭乖，人稱：我叫唐小鬥，撒尿不洗手。自稱：唐山小旋風。天賦技能：洗碗、吸鐵石。最擅長：跳刀躲梅肯，塔下意識粉，殘血A回複，反補世界樹，推推吃盲壓，瘋臉A刃甲，分身躲秘法，血精解薄葬，TP切假腿，一級沖泉水等大神級操作。11平台常用ID：少男乖、唐小鬥、少年乖。天梯最高積分記錄：2671，天梯最高排名記錄：第14名。前職業選手，在GREEDY司職3号位，Maybe的好兄弟，一對兒上頭gank。憑借極強的個人能力和意識，一般是"烈士路"的首選。擅長東南亞SK，暴力水卡，抽藍狂魔，抽筋大牛，水槍，水虎傳。名下有四大天王：金閃閃，阿列列，大國手，saga。人們戲稱，四大天王得其二，此局必“穩”。自從實力戰将“殺馬特”（遊戲id：狂戰士）加入阿鬥幫之後，少男乖黑店從送分黑轉型相聲黑，但是黑店實力仍然是2800左右。

NL_KS【中文名：張凱】

東北人，熟悉他的玩家一般喊他：小凱、矮子、巨人凱、凱神。11對戰平台常用ID：NL_KS，天梯最高積分記錄：2414，天梯最高排名記錄：前100名。2013，小凱25歲，現是中國石油的一名技術員，接觸DotA的時間大概有4年，經驗豐富，是隊中的一位老大哥。擅長：火槍，巨牙海民、隐形刺客、小魚人、骨法等多名矮系英雄。

隊長給我球【戰隊隊長】

大球哥又名“送分球、弱智球、吳彥球”，11對戰平台常用ID：隊長給我球。天梯最高積分記錄：2722，天梯最高排名記錄：前7名。隊長給我球是Greedy中很特别的一位選手，因為他的聲音和聲調與常人不同，聽上去隐隐一絲喜感，但打DOTA時隊長的無私奉獻及亮眼操作給人印象深刻。技術特點：操作細膩、BP出色、輔助到位、GANK意識強。在GREEDY中根據陣容司職4-5号位。

戰隊榮譽

2012年DCG冠軍（獎金10W）

2013年17173天梯黑店争霸賽冠軍（獎金1W）

2013年VS“京東杯”DOTA超級聯賽冠軍（獎金2W）

WGT2013dota項目冠軍（獎金5W）

CPL2013電子競技大賽DotA項目線下總決賽冠軍（獎金￥50,000元）

USL-U9超級聯賽DOTA項目冠軍（獎金15000元）

2013年11平台DSC冠軍（獎金10000元+全套外設）

戰隊排名

截至2013年5月，來自Gosugamers的世界排名。

戰隊趣事

（1）當大家DOTA打的無聊或被路人虐了之後，經常打軍團戰争來消遣（防守類WAR3RPG地圖）。

（2）當大家有看到對方動物信使出現在附近的時候，一般會選擇先殺雞，再殺人。

（3）經常一起玩天梯頂分對黑局時，隊員之間經常出現互相調侃的歡樂局面。

貪心算法

算法思想

雖然設計一個好的求解算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細緻的調整。但是在某些情況下，算法經過調整之後性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。GreedyAlgorithm在設計方面不能保證求得的最後解是最佳的和不能用來求最大或最小解問題，隻能求滿足某些約束條件的可行解的範圍。

事例1

例1-4[找零錢]一個小孩買了價值少于1美元的糖，并将1美元的錢交給售貨員。售貨員希望用數目最少的硬币找給小孩。假設提供了數目不限的面值為25美分、10美分、5美分、及1美分的硬币。售貨員分步驟組成要找的零錢數，每次加入一個硬币。選擇硬币時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬币不應使零錢總數超過最終所需的數目。

假設需要找給小孩67美分，首先入選的是兩枚25美分的硬币，第三枚入選的不能是25美分的硬币，否則硬币的選擇将不可行（零錢總數超過67美分），第三枚應選擇10美分的硬币，然後是5美分的，最後加入兩個1美分的硬币。

貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬币數目最少（至少是接近最少的數目）。可以證明采用上述貪婪算法找零錢時所用的硬币數目的确最少（見練習1）。

事例2

例1-5[機器調度]現有n件任務和無限多台的機器，任務可以在機器上得到處理。每件任務的開始時刻為si，完成時刻為fi，si

假設有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(nlogn)的貪婪算法：首先采用一個複雜性為O(nlogn)的排序算法（如堆排序）按Si的遞增次序排列各個任務，然後使用一個關于舊機器可用時間的最小堆。

事例3

例1-6[最短路徑]給出一個有向網絡，路徑的長度定義為路徑所經過的各邊的耗費之和。要求找一條從初始頂點s到達目的頂點d的最短路徑。

貪婪算法分步構造這條路徑，每一步在路徑中加入一個頂點。假設當前路徑已到達頂點q，

且頂點q并不是目的頂點d。加入下一個頂點所采用的貪婪準則為：選擇離q近且不在路徑中的頂點。

這種貪婪算法并不一定能獲得最短路徑。例如，假設在圖13-2中希望構造從頂點1到頂點5的最短路徑，利用上述貪婪算法，從頂點1開始并尋找目前不在路徑中的離頂點1最近的頂點。到達頂點3，長度僅為2個單位，從頂點3可以到達的頂點為4，從頂點4到達頂點2，最後到達目的頂點5。所建立的路徑為1,3,4,2,5，其長度為10。這條路徑并不是有向圖中從1到5的最短路徑。事實上，有幾條更短的路徑存在，例如路徑1，4，5的長度為6。

總結

根據上面三個例子，回想一下前幾章所考察的一些應用，其中有幾種算法也是貪婪算法。例如，霍夫曼樹算法，利用n-1步來建立最小加權外部路徑的二叉樹，每一步都将兩棵二叉樹合并為一棵，算法中所使用的貪婪準則為：從可用的二叉樹中選出權重最小的兩棵。LPT調度規則也是一種貪婪算法，它用n步來調度n個作業。首先将作業按時間長短排序，然後在每一步中為一個任務分配一台機器。選擇機器所利用的貪婪準則為：使目前的調度時間最短。将新作業調度到最先完成的機器上（即最先空閑的機器）。

存在問題

注意到在機器調度問題中，貪婪算法并不能保證最優，然而，那是一種直覺的傾向且一般情況下結果總是非常接近最優值。它利用的規則就是在實際環境中希望人工機器調度所采用的規則。算法并不保證得到最優結果，但通常所得結果與最優解相差無幾，這種算法也稱為啟發式方法（heuristics)。因此LPT方法是一種啟發式機器調度方法。定理9-2陳述了LPT調度的完成時間與最佳調度的完成時間之間的關系，因此LPT啟發式方法具有限定性

能（boundedperformance）。具有限定性能的啟發式方法稱為近似算法（approximationalgorithm）。

本章的其馀部分将介紹幾種貪婪算法的應用。在有些應用中，貪婪算法所産生的結果總是最優的解決方案。但對其他一些應用，生成的算法隻是一種啟發式方法，可能是也可能不是近似算法。

兩大難點

貪心方法

怎樣才能從衆多可行解中找到最優解呢？其實，大部分都是有規律的。在樣例中，貪心就有很明顯的規律。但你得到了[fontlang=EN-US]N=5時的最優解後，你隻需要在已用上的5塊木闆中尋找最靠近的兩塊，然後貼上中間的幾個牛棚，使兩塊木闆變成一塊。這樣生成的N=4的解必定最優。因為這樣木闆的浪費最少。同樣，其他的貪心題也會有這樣的性質。正因為貪心有如此性質，它才能比其他算法要快。

正确性

要證明貪心性質的正确性，才是貪心算法的真正挑戰，因為并不是每次局部最優解都會與整體最優解之間有聯系，往往靠貪心生成的解不是最優解。這樣，貪心性質的證明就成了貪心算法正确的關鍵。一個你想出的貪心性質也許是錯的，即使它在大部分數據中都是可行的，你必須考慮到所有可能出現的特殊情況，并證明你的貪心性質在這些特殊情況中仍然正确。這樣經過千錘百煉的性質才能構成一個正确的貪心。

在樣例中，我們的貪心性質是正确的。如下：

假設我們的答案蓋住了較大的空牛棚連續列，而不是較小的。那麼我們把那部分蓋空牛棚的木闆鋸下來，用來把較小的空牛棚連續列蓋住，還會有剩馀。那麼鋸掉它們！還給木材商！同時我們的解也變小了。也就是說，我們獲得更優的解。所以，靠蓋住較大空牛棚連續列的方法無法獲得最優解，我們也應該盡量貪心那些距離小的木闆合并。

如果仍有一個空牛棚連續列與我們的答案蓋住的那個相同，我們同樣使用上述的方法。會發現獲得的新解與原解相同，那麼不論我們選哪個，結果都将一樣。

由此可見，如果我們合并的兩塊木闆間距離最短，那麼總能獲得最優解。所以，在解題的每一步中，我們都隻需要尋找兩塊距離最小的木闆并合并它們。這樣，我們獲得的解必定最優。