去年“新智元”有一篇報(bào)道《清華畢業(yè)計(jì)算機(jī)教授遭持槍劫車，靠“貪心算法”追回秒殺美國警察》贾铝，整個故事像看微小說一樣，可對于核心問題“貪心算法”是什么并沒有說清楚。于是就有了下面的內(nèi)容刘离。
什么是貪心算法
貪心的意思在于在作出選擇時，每次都要選擇對自身最為有利的結(jié)果睹栖，保證自身利益的最大化硫惕。貪心算法就是利用這種貪心思想而得出一種算法。
貪心算法可以簡單描述為：大事化小野来，小事化了恼除。對于一個較大的問題，通過找到與子問題的重疊曼氛，把復(fù)雜的問題劃分為多個小問題豁辉。并且對于每個子問題的解進(jìn)行選擇，找出最優(yōu)值舀患，進(jìn)行處理徽级，再找出最優(yōu)值，再處理聊浅。也就是說貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇餐抢，從而希望得到結(jié)果是最好或最優(yōu)的算法现使。
貪心算法在對問題求解時，總是做出在當(dāng)前看來是最好的選擇旷痕。也就是說碳锈，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解欺抗。貪心算法不是對所有問題都能得到整體最優(yōu)解售碳，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。
貪心算法基本思路
步驟一：建立數(shù)學(xué)模型來描述問題
步驟二：把求解的問題分成若干個子問題
步驟三：對每個子問題求解绞呈，得到子問題的局部最優(yōu)解
步驟四：把子問題的解局部最優(yōu)解合成原來問題的一個解
貪心算法的選擇
所謂貪心選擇是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇贸人，換句話說，當(dāng)考慮做何種選擇的時候报强，我們只考慮對當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果灸姊。
貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題秉溉。對于一個具體問題力惯，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解召嘶。
我們下面通過示例來看一下貪心算法如何選擇父晶。
貪心算法示例
看一下《算法導(dǎo)論》中的經(jīng)典例題：活動選擇問題
有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用弄跌。每個活動ai都有一個開始時間si和結(jié)束時間fi 甲喝。一旦被選擇后，活動ai就占據(jù)半開時間區(qū)間[si,fi)铛只。如果[si,fi]和[sj,fj]互不重疊埠胖，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行淳玩。（標(biāo)紅的是我們利用貪心算法求出的結(jié)果1直撤、4、8蜕着、11）
第一步：分析題目：
目標(biāo)函數(shù)count（n）活動次數(shù)最多
約束條件是下一個活動開始時間大于或等于上一個活動開始時間s[i]>=f[j]
第二步：選擇解題思路：
（1）每次選擇開始時間最早的活動
（2）每次選擇持續(xù)時間最短的活動
（3）每次選取結(jié)束時間最早的活動
第三步：證明上面哪種思路可以應(yīng)用于本題：
為了方便谋竖，我們用不同顏色的線條代表每個活動，線條的長度就是活動所占據(jù)的時間段承匣，藍(lán)色的線條表示我們已經(jīng)選擇的活動蓖乘；紅色的線條表示我們沒有選擇的活動。
1）如果我們每次都選擇開始時間最早的活動韧骗，不能得到最優(yōu)解：
證明（反證法）：
例如我們選擇了10號活動（開始時間2點(diǎn)嘉抒，結(jié)束時間13點(diǎn)）
2號活動待選擇（開始時間3點(diǎn)，結(jié)束時間5點(diǎn)）
則會出現(xiàn)上圖所示的情況袍暴，這顯然違背了約束條件
2)如果我們每次都選擇持續(xù)時間最短的活動众眨，不能得到最優(yōu)解：
證明（反證法）：
例如我們選擇了2號活動（開始時間3點(diǎn)握牧，結(jié)束時間5點(diǎn)）
1號活動待選擇（開始時間1點(diǎn)，結(jié)束時間4點(diǎn)）
則會出現(xiàn)上圖所示的情況娩梨，這顯然也違背了約束條件
3）如果我們每次都選取結(jié)束時間最早的活動，能夠得到最優(yōu)解（采用的貪心策略）：
那么怎么證明貪心算法是對的呢览徒？要證明一個算法是錯的非常簡單狈定，要證明是對的卻非常的難，對于貪心算法的證明习蓬，一是使用歸納法纽什，二是采用反證法。像上面兩種策略躲叼，我們實(shí)際上就用到了反證法芦缰。
回到策略本身，按這種方法選擇相容活動枫慷，能夠?yàn)槲窗才诺幕顒恿粝卤M可能多的時間让蕾。
第四步：選好策略，那我們就來按照貪心算法的基本思路總結(jié)一下：
步驟一：數(shù)學(xué)模型是目標(biāo)函數(shù)count（n）最大或听，約束條件是s[i]>=f[j]
步驟二：求解哪個活動結(jié)束時間最早（本題目顯然是活動1）
步驟三：求解哪個動開始時間s[i]大于上一個活動結(jié)束時間f[j]
步驟四：把步驟三求出的活動依次取出探孝，作為我們選取的活動
上代碼
這段代碼的含義是：
定義活動號n，活動開始時間誉裆、結(jié)束時間Type s[]顿颅，Type f[]，布爾邏輯判斷A[]
定義進(jìn)入算法的活動序號足丢，最終選取的活動序號i粱腻，j
初始活動i=1，由于1號活動結(jié)束時間斩跌，所以選取j=1
從2號活動開始進(jìn)入運(yùn)算绍些，具體運(yùn)算規(guī)則：
判斷條件：活動開始時間（i）>上一個活動結(jié)束時間（j）
A[]為true，j選中
A[]為false滔驶，j不選擇
i自增1位遇革，繼續(xù)判斷，直至i=11
上圖直觀展示了算法的整個運(yùn)行過程揭糕。
貪心算法應(yīng)用
貪心算法應(yīng)用非常廣泛萝快，特別電腦游戲AI或者一些推薦。
以經(jīng)典的跳躍游戲?yàn)槔?/p>
1著角、題目描述
給定一個非負(fù)整數(shù)數(shù)組揪漩，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度吏口。
判斷是否能夠到達(dá)最后一個位置奄容。
2冰更、問題分析
先轉(zhuǎn)化為數(shù)學(xué)模型：給定一個數(shù)組，數(shù)組中每個位置的數(shù)字代表當(dāng)前位置i能夠向前跳躍num[i]的距離昂勒，然后判斷是否能夠從第一個位置跳到最后一個位置蜀细。
這道題的難點(diǎn)就在于每次跳多遠(yuǎn)的距離算合適呢？如果從i的位置能跳num[i]距離最遠(yuǎn)能到達(dá)j的位置戈盈，那么這中間的任何一個位置我們都能跳到奠衔，但我們具體是跳到i--j之間的哪個位置才是真正合適的位置？
利用貪心的思想我們的目的是判斷最后能否跳到最后一個位置塘娶，其實(shí)就是只要能保證在i--j之間跳到一個能夠在下一次跳的更遠(yuǎn)的距離归斤，那么這個位置就是最合適的位置。
