一正什、基本概念:
?所謂貪心算法是指,在對問題求解時(shí)裹唆,總是做出在當(dāng)前看來是最好的選擇誓斥。也就是說,不從整體最優(yōu)上加以考慮许帐,他所做出的僅是在某種意義上的局部最優(yōu)解岖食。
?貪心算法沒有固定的算法框架,算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇舞吭。必須注意的是泡垃,貪心算法不是對所有問題都能得到整體最優(yōu)解,選擇的貪心策略必須具備無后效性羡鸥,即某個(gè)狀態(tài)以后的過程不會影響以前的狀態(tài)蔑穴,只與當(dāng)前狀態(tài)有關(guān)。
?所以對所采用的貪心策略一定要仔細(xì)分析其是否滿足無后效性惧浴。
二存和、貪心算法的基本思路:
??? 1.建立數(shù)學(xué)模型來描述問題。
??? 2.把求解的問題分成若干個(gè)子問題。
??? 3.對每一子問題求解捐腿,得到子問題的局部最優(yōu)解纵朋。
??? 4.把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。
三茄袖、貪心算法適用的問題
????? 貪心策略適用的前提是:局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解操软。
實(shí)際上,貪心算法適用的情況很少宪祥。一般聂薪,對一個(gè)問題分析是否適用于貪心算法,可以先選擇該問題下的幾個(gè)實(shí)際數(shù)據(jù)進(jìn)行分析蝗羊,就可做出判斷藏澳。
四、貪心算法的實(shí)現(xiàn)框架
??? 從問題的某一初始解出發(fā)耀找;
??? while (能朝給定總目標(biāo)前進(jìn)一步)
??? {?
????????? 利用可行的決策翔悠,求出可行解的一個(gè)解元素;
??? }
??? 由所有解元素組合成問題的一個(gè)可行解野芒;
五蓄愁、貪心策略的選擇
???? 因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^解局部最優(yōu)解的策略來達(dá)到全局最優(yōu)解,因此复罐,一定要注意判斷問題是否適合采用貪心算法策略涝登,找到的解是否一定是問題的最優(yōu)解。
六效诅、例題分析
??? 下面是一個(gè)可以試用貪心算法解的題目胀滚,貪心解的確不錯(cuò),可惜不是最優(yōu)解乱投。
??? [背包問題]有一個(gè)背包咽笼,背包容量是M=150。有7個(gè)物品戚炫,物品可以分割成任意大小剑刑。
??? 要求盡可能讓裝入背包中的物品總價(jià)值最大,但不能超過總?cè)萘俊?/p>
??? 物品 A B C D E F G
??? 重量 35 30 60 50 40 10 25
??? 價(jià)值 10 40 30 50 35 40 30
??? 分析:
??? 目標(biāo)函數(shù): ∑pi最大
??? 約束條件是裝入的物品總重量不超過背包容量:∑wi<=M( M=150)
??? (1)根據(jù)貪心的策略双肤,每次挑選價(jià)值最大的物品裝入背包施掏,得到的結(jié)果是否最優(yōu)?
??? (2)每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解茅糜?
??? (3)每次選取單位重量價(jià)值最大的物品七芭,成為解本題的策略。
??? 值得注意的是蔑赘,貪心算法并不是完全不可以使用狸驳,貪心策略一旦經(jīng)過證明成立后预明,它就是一種高效的算法。
??? 貪心算法還是很常見的算法之一耙箍,這是由于它簡單易行撰糠,構(gòu)造貪心策略不是很困難。
??? 可惜的是辩昆,它需要證明后才能真正運(yùn)用到題目的算法中阅酪。
??? 一般來說,貪心算法的證明圍繞著:整個(gè)問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的卤材。
??? 對于例題中的3種貪心策略遮斥,都是無法成立(無法被證明)的峦失,解釋如下:
??? (1)貪心策略:選取價(jià)值最大者扇丛。反例:
??? W=30
??? 物品:A B C
??? 重量:28 12 12
??? 價(jià)值:30 20 20
??? 根據(jù)策略,首先選取物品A尉辑,接下來就無法再選取了帆精,可是,選取B隧魄、C則更好卓练。
??? (2)貪心策略:選取重量最小。它的反例與第一種策略的反例差不多购啄。
??? (3)貪心策略:選取單位重量價(jià)值最大的物品襟企。反例:
??? W=30
??? 物品:A B C
??? 重量:28 20 10
??? 價(jià)值:28 20 10
??? 根據(jù)策略,三種物品單位重量價(jià)值一樣狮含,程序無法依據(jù)現(xiàn)有策略作出判斷顽悼,如果選擇A,則答案錯(cuò)誤几迄。