基本認(rèn)識
貪心算法(又稱貪婪算法)是指洞翩,在對問題求解時骚亿,總是做出在當(dāng)前看來是最好的選擇熊赖。也就是說,不從整體最優(yōu)上加以考慮震鹉,它所做出的是在某種意義上的局部最優(yōu)解传趾。
基本思想與原理
貪心選擇是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇,即貪心選擇來達(dá)到浆兰。這是貪心算法可行的第一個基本要素,也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別榕订。貪心選擇是采用從頂向下蝶棋、以迭代的方法做出相繼選擇,每做一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題兼贸。對于一個具體問題吃溅,要確定它是否具有貪心選擇的性質(zhì),我們必須證明每一步所作的貪心選擇最終能得到問題的最優(yōu)解螺垢。通忱蹈瑁可以首先證明問題的一個整體最優(yōu)解,是從貪心選擇開始的庐冯,而且作了貪心選擇后展父,原問題簡化為一個規(guī)模更小的類似子問題玲昧。然后篮绿,用數(shù)學(xué)歸納法證明,通過每一步貪心選擇亲配,最終可得到問題的一個整體最優(yōu)解吼虎。
貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行,每一步都要確保能獲得局部最優(yōu)解鲸睛。每一步只考慮一個數(shù)據(jù)官辈,他的選取應(yīng)該滿足局部優(yōu)化的條件遍坟。若下一個數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時,就不把該數(shù)據(jù)添加到部分解中愿伴,直到把所有數(shù)據(jù)枚舉完隔节,或者不能再添加算法停止。
適用的問題
貪心策略適用的前提是:局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解怎诫。
實際上幻妓,貪心算法適用的情況很少。一般對一個問題分析是否適用于貪心算法肉津,可以先選擇該問題下的幾個實際數(shù)據(jù)進(jìn)行分析,就可以做出判斷偶洋。
大多數(shù)可以使用貪心算法的問題都有以下特點:
(1)原問題復(fù)雜度過高初烘;
(2)求全局最優(yōu)解的數(shù)學(xué)模型難以建立分俯;
(3)求全局最優(yōu)解的計算量過大哆料;
(4)沒有太大必要一定要求出全局最優(yōu)解东亦,“比較優(yōu)”就可以。
嚴(yán)格來說典阵,貪婪算法可解決的問題通常大部分都有如下的特性:
(1)隨著算法的進(jìn)行壮啊,將積累起其它兩個集合:一個包含已經(jīng)被考慮過并被選出的候選對象,另一個包含已經(jīng)被考慮過但被丟棄的候選對象歹啼。
(2)有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答狸眼。該函數(shù)不考慮此時的解決方法是否最優(yōu)。
(3)還有一個函數(shù)檢查是否一個候選對象的集合是可行的拓萌,也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣屡限,此時不考慮解決方法的最優(yōu)性炕倘。
(4)選擇函數(shù)可以指出哪一個剩余的候選對象最有希望構(gòu)成問題的解。
(5)最后拓型,目標(biāo)函數(shù)給出解的值瘸恼。
(6)為了解決問題,需要尋找一個構(gòu)成解的候選對象集合压固,它可以優(yōu)化目標(biāo)函數(shù)靠闭,貪婪算法一步一步的進(jìn)行坎炼。起初拦键,算法選出的候選對象的集合為空芬为。接下來的每一步中,根據(jù)選擇函數(shù)媚朦,算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行孙乖,那么該對象就被丟棄并不再考慮份氧;否則就加到集合里。每一次都擴充集合,并檢查該集合是否構(gòu)成解钮糖。如果貪婪算法正確工作酌住,那么找到的第一個解通常是最優(yōu)的。
求解的步驟與模板
貪婪算法并沒有固定的算法解決框架消痛,算法的關(guān)鍵是貪婪策略的選擇都哭,根據(jù)不同的問題選擇不同的策略。
必須注意的是策略的選擇必須具備無后效性纱新,即某個狀態(tài)的選擇不會影響到之前的狀態(tài)穆趴,只與當(dāng)前狀態(tài)有關(guān),所以對采用的貪婪的策略一定要仔細(xì)分析其是否滿足無后效性簿废。
引例部分
活動安排問題:
設(shè)有n個活動的集合E={1,2,…,n},其中每個活動都要求使用同一資源歪赢,如演講會場等导梆,而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si <fi 看尼。如果選擇了活動i藏斩,則它在半開時間區(qū)間[si, fi)內(nèi)占用資源。若區(qū)間[si, fi)與區(qū)間[sj, fj)不相交媳拴,則稱活動i與活動j是相容的兆览。也就是說,當(dāng)si≥fj或sj≥fi時子巾,活動i與活動j相容小压。活動安排問題: 要在所給的活動集合中選出最大的相容活動子集合怠益◎呃危活動安排問題的關(guān)鍵是如何按照一定的順序安排活動,使得選出的活動間相容并能安排盡量多的活動髓削。
解題思路:
把會場要安排的所有活動作為一個集合W镀娶,初始開始時間標(biāo)準(zhǔn)為preStart,初始結(jié)束時間標(biāo)準(zhǔn)為preEnd.每次放入W的活動要在滿足,開始時間s[i]>preStart的前提下f[i]最小宝泵。然后把f[i]賦值給preStart. 依次加入,直到加不進(jìn)去為止框往,從而把問題解決。
雖然貪心算法并不是針對任何一個問題都存在最優(yōu)解瓤鼻,但是針對會場安排問題可以得到最優(yōu)解。我們可以從貪心算法得到的結(jié)果集僅進(jìn)行倒推茬祷。首先去掉結(jié)果集中的第一個活動A祭犯,那么在剩下的活動中,結(jié)束時間最早的活動B的結(jié)束時間一定不早于A,那么A活動在最優(yōu)解中一定合理粥惧。再用同樣的方式判斷活動B,依次類推最盅,則結(jié)果集就是最優(yōu)解。
實戰(zhàn)部分
整數(shù)轉(zhuǎn)羅馬數(shù)字問題:
解題思路:
這道題要將4,9盼产,40勺馆,90,400灌灾,900的符號單列出來悲柱。然后我們使用貪心算法,每次運算都將總數(shù)減去最大的可能數(shù)值嘿般,直到減到0。(就像假如你要付67塊錢逼庞,肯定先找出一張50塊瞻赶,再找出一張10塊,再找出一張5塊璧南,最后找出兩張1塊)痹兜。
下面附上Python3的題解代碼
class Solution:
def intToRoman(self, num: int) -> str:
dic={'I':1,'IV':4,'V':5,'IX':9,'X':10,'XL':40,'L':50,'XC':90,'C':100,'CD':400,'D':500,'CM':900,'M':1000}
res=""
for val in sorted(dic.values())[::-1]:
if num==0:
break
tmp=num//val
if tmp==0:
continue
res +=(list (dic.keys()) [list (dic.values()).index (val)])*tmp
num -=val*tmp
return res
趁熱打鐵 刷題練習(xí)部分(持續(xù)更新)
以下是LeetCode題庫中一些用到貪心算法的經(jīng)典例題的題目及解析字旭,有題干,有題解代碼拍柒、有解題思路(持續(xù)更新):
No.12.整數(shù)轉(zhuǎn)羅馬字母:
https://blog.csdn.net/LanXiu_/article/details/104085783
No.13.羅馬數(shù)字轉(zhuǎn)整數(shù):
https://blog.csdn.net/LanXiu_/article/details/104085783
No.45.跳躍游戲Ⅱ:
https://blog.csdn.net/LanXiu_/article/details/104177349
No.55.跳躍游戲:
https://blog.csdn.net/LanXiu_/article/details/104216342