貪心法“>算法->貪心法

一、基本概念：

所謂貪心算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
貪心算法沒(méi)有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇。必須注意的是，貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。
所以對(duì)所采用的貪心策略一定要仔細(xì)分析其是否滿足無(wú)后效性。

二、貪心算法的基本思路：
1.建立數(shù)學(xué)模型來(lái)描述問(wèn)題。
2.把求解的問(wèn)題分成若干個(gè)子問(wèn)題。
3.對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。
4.把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。

三、貪心算法適用的問(wèn)題
貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解。
實(shí)際上，貪心算法適用的情況很少。一般，對(duì)一個(gè)問(wèn)題分析是否適用于貪心算法，可以先選擇該問(wèn)題下的幾個(gè)實(shí)際數(shù)據(jù)進(jìn)行分析，就可做出判斷。

四、貪心算法的實(shí)現(xiàn)框架
從問(wèn)題的某一初始解出發(fā)；
while （能朝給定總目標(biāo)前進(jìn)一步）
{
利用可行的決策，求出可行解的一個(gè)解元素；
}
由所有解元素組合成問(wèn)題的一個(gè)可行解；

五、貪心策略的選擇
因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^(guò)解局部最優(yōu)解的策略來(lái)達(dá)到全局最優(yōu)解，因此，一定要注意判斷問(wèn)題是否適合采用貪心算法策略，找到的解是否一定是問(wèn)題的最優(yōu)解。

六、例題分析
下面是一個(gè)可以試用貪心算法解的題目，貪心解的確不錯(cuò)，可惜不是最優(yōu)解。
[背包問(wèn)題]有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊?br /> 物品 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最大
約束條件是裝入的物品總重量不超過(guò)背包容量：∑wi<=M( M=150)
（1）根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？
（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？
（3）每次選取單位重量?jī)r(jià)值最大的物品，成為解本題的策略。
值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過(guò)證明成立后，它就是一種高效的算法。
貪心算法還是很常見(jiàn)的算法之一，這是由于它簡(jiǎn)單易行，構(gòu)造貪心策略不是很困難。
可惜的是，它需要證明后才能真正運(yùn)用到題目的算法中。
一般來(lái)說(shuō)，貪心算法的證明圍繞著：整個(gè)問(wèn)題的最優(yōu)解一定由在貪心策略中存在的子問(wèn)題的最優(yōu)解得來(lái)的。
對(duì)于例題中的3種貪心策略，都是無(wú)法成立（無(wú)法被證明）的，解釋如下：
（1）貪心策略：選取價(jià)值最大者。反例：
W=30
物品：A B C
重量：28 12 12
價(jià)值：30 20 20
根據(jù)策略，首先選取物品A，接下來(lái)就無(wú)法再選取了，可是，選取B、C則更好。
（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量?jī)r(jià)值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
價(jià)值：28 20 10
根據(jù)策略，三種物品單位重量?jī)r(jià)值一樣，程序無(wú)法依據(jù)現(xiàn)有策略作出判斷，如果選擇A，則答案錯(cuò)誤。