http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html
1.基本概念
所謂貪心算法是指，在對(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ú)后效性**镜会。
2.貪心算法的基本思路
- 建立數(shù)學(xué)模型來(lái)描述問(wèn)題
- 把求解的問(wèn)題分解成若干個(gè)子問(wèn)題
- 對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解
- 把子問(wèn)題的解局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解
3.貪心法適用的問(wèn)題
** 貪心策略適用的前提是：局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解终抽。**
實(shí)際上戳表，貪心算法適用的情況很少。一般昼伴，對(duì)一個(gè)問(wèn)題分析是否適用于貪心算法匾旭，可以先選擇該問(wèn)題下的幾個(gè)實(shí)際數(shù)據(jù)進(jìn)行分析坦刀，就可做出判斷弦赖。
4.貪心算法的實(shí)現(xiàn)框架
從問(wèn)題的某一初始解出發(fā)
while(能吵給定總目標(biāo)前進(jìn)一步)
{
利用可行的決策，求出可行解的一個(gè)解元素
}
由所有解元素組合成問(wèn)題的可行解
5.貪心策略的選擇
因?yàn)橛秘澬乃惴ㄖ荒芡ㄟ^(guò)解局部最優(yōu)解得策略來(lái)達(dá)到全局最優(yōu)验烧，因此持舆，一定要注意判斷問(wèn)題是否適合用貪心算法飒泻，找到的解是否一定是問(wèn)題的最優(yōu)解
