基本介紹
- 中文名：貪心算法
- 外文名：greedy algorithm
- 別稱：貪婪算法
- 性質：一種改進了的分級處理方法
- 核心：根據題意選取一種量度標準
基本要素,貪心選擇,最優子結構,基本思路,思想,過程,算法特性,例題分析,0-1背包問題,馬踏棋盤,均分紙牌,備註,套用,
基本要素
貪心選擇
貪心選擇是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規划算法的主要區別。貪心選擇是採用從頂向下、以疊代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。對於一個具體問題，要確定它是否具有貪心選擇的性質，我們必須證明每一步所作的貪心選擇最終能得到問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步貪心選擇，最終可得到問題的一個整體最優解。
最優子結構
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。運用貪心策略在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動態規划算法求解的關鍵特徵。貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。動態規劃主要運用於二維或三維問題，而貪心一般是一維問題。
基本思路
思想
貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個最佳化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部最佳化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加算法停止。
過程
- 建立數學模型來描述問題；
- 把求解的問題分成若干個子問題；
- 對每一子問題求解，得到子問題的局部最優解；
- 把子問題的解局部最優解合成原來解問題的一個解。
算法特性
貪婪算法可解決的問題通常大部分都有如下的特性：
- 隨著算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
- 有一個函式來檢查一個候選對象的集合是否提供了問題的解答。該函式不考慮此時的解決方法是否最優。
- 還有一個函式檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函式一樣，此時不考慮解決方法的最優性。
- 選擇函式可以指出哪一個剩餘的候選對象最有希望構成問題的解。
- 最後，目標函式給出解的值。
- 為了解決問題，需要尋找一個構成解的候選對象集合，它可以最佳化目標函式，貪婪算法一步一步的進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函式，算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那么該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優的。
例題分析
0-1背包問題
有一個背包，背包容量是M=150kg。有7個物品，物品不可以分割成任意大小。要求儘可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目標函式：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
⑵每次挑選所占重量最小的物品裝入是否能得到最優解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的算法。
貪心算法還是很常見的算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的算法中。
一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
⑴貪心策略：選取價值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
⑵貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略：選取單位重量價值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程式無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
【注意：如果物品可以分割為任意大小，那么策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條最佳化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
W=40
物品：A B C
重量：25 20 15
價值：25 20 15
附：本題是個DP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃算法後本題就有了新的解法。
馬踏棋盤
在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜尋問題，運用深度優先搜尋進行求解。算法如下：
⒈ 輸入初始位置坐標x,y；
⒉ 步驟 c:
如果c> 64輸出一個解，返回上一步驟c--
（x,y) ← c
計算(x,y）的八個方位的子結點，選出那些可行的子結點
循環遍歷所有可行子結點，步驟c++重複2
顯然⑵是一個遞歸調用的過程，大致如下：
C++程式：
#define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();//輸出一個解 return; } for(i=0; i<8; i++) { tx=hn[i].x;//hn[]保存八個方位子結點 ty=hn[i].y; s[tx][ty]=count; dfs(tx,ty,count+1);//遞歸調用 s[tx][ty]=0; }}Pascal程式：
ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcedureFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1）；{讀入結束坐標}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎么才能快速地得到部分解呢？
【貪心算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的算法。在每個結點對其子結點進行選取時，優先選擇‘出口’最小的進行搜尋，‘出口’的意思是在這些子結點中它們的可行子結點的個數，也就是‘孫子’結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現‘死’結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜尋純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種算法稱為為貪心算法，也叫貪婪算法或啟發式算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。
均分紙牌
#include<cstdio>#include<iostream>#include<cstdlib>int a[1000];using namespace std;int f(int n){ int ave=0; int f=0; for (int i=1;i<=n;i++) { f=f+a[i]; } return f/n;}int main(){ int n; int ans=0; int ave; scanf ("%d",&n); for (int i=1;i<=n;i++) { scanf ("%d",&a[i]); } ave=f(n); for (int i=1;i<=n;i++) { if (a[i]==ave) { continue; } if (a[i]!=ave) { a[i+1]+=a[i]-ave; ans++; } } printf ("%d",ans); return 0;}備註
所以需要說明的是，貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。其實很多的智慧型算法（也叫啟發式算法），本質上就是貪心算法和隨機化算法結合——這樣的算法結果雖然也是局部最優解，但是比單純的貪心算法更靠近了最優解。例如遺傳算法，模擬退火算法。
套用
如把3/7和13/23分別化為三個單位分數的和
【貪心算法】
設a、b為互質正整數，a<b 分數a/b 可用以下的步驟分解成若干個單位分數之和：
步驟一： 用b 除以a，得商數q1 及餘數r1。（r1=b - a*q1）
步驟二：把a/b 記作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步驟三：重複步驟2，直到分解完畢
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
設某個真分數的分子為a，分母為b;
把b除以a的商部分加1後的值作為埃及分數的某一個分母c；
將a乘以c再減去b，作為新的a；
將b乘以c，得到新的b；
如果a大於1且能整除b，則最後一個分母為b/a；算法結束；
或者，如果a等於1，則，最後一個分母為b；算法結束；
否則重複上面的步驟。
備註：事實上，後面判斷a是否大於1和a是否等於1的兩個判斷可以合在一起，及判斷b%a是否等於0，最後一個分母為b/a，顯然是正確的。
PHP代碼：
class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0){ $this->weight=$weight; $this->price=$price; }}//生成數據$n=10;for($i=1;$i<=$n;$i++){ $weight=rand(1,20); $price=rand(1,10); $x[$i]=new tanxin($weight,$price);}//輸出結果function display($x){ $len=count($x); foreach($x as $val){ echo $val->weight,' ',$val->price; echo '<br>'; }}//按照價格和重量比排序function tsort(&$x){ $len=count($x); for($i=1;$i<=$len;$i++) { for($j=1;$j<=$len-$i;$j++) { $temp=$x[$j]; $res=$x[$j+1]->price/$x[$j+1]->weight; $temres=$temp->price/$temp->weight; if($res>$temres){ $x[$j]=$x[$j+1]; $x[$j+1]=$temp; } } } }//貪心算法function tanxin($x,$totalweight=50){ $len=count($x); $allprice=0; for($i=1;$i<=$len;$i++){ if($x[$i]->weight>$totalweight) break; else{ $allprice+=$x[$i]->price; $totalweight=$totalweight-$x[$i]->weight; } } if($i<$len) $allprice+=$x[$i]->price*($totalweight/$x[$i]->weight); return $allprice;}tsort($x);//按非遞增次序排序display($x);//顯示echo '0-1背包最優解為:';echo tanxin($x);