貪心算法

選擇目前最優(yōu)策略，不考慮全局最優(yōu)

三步走

第一步

明確最優(yōu)解

第二步

明確子問(wèn)題的最優(yōu)解

第三步

分別求出子問(wèn)題的最優(yōu)解再堆疊出全局最優(yōu)解

例子

背包問(wèn)題
有一個(gè)背包，最多能承載150斤的重量，現(xiàn)在有7個(gè)物品，重量分別為[35, 30, 60, 50, 40, 10, 25]，它們的價(jià)值分別為[10, 40, 30, 50, 35, 40, 30]，如何使背包背走最多價(jià)值的物品

方法一：

1.在重量限制范圍內(nèi)，價(jià)值最大的選擇是最優(yōu)解
2.每次盡量選擇當(dāng)前價(jià)值最高的物品，稱(chēng)為“局部最優(yōu)解”
3.選擇4 2 6 5；總重量130；總價(jià)值165；

方法二

1.質(zhì)量最輕為最優(yōu)解
2.選擇6 7 2 1 5；總重量：140；總價(jià)值：155；
方法一比較好

核心問(wèn)題

一、為何求局部最優(yōu)解
1.原問(wèn)題復(fù)雜度過(guò)高
2.求全局最優(yōu)解的數(shù)學(xué)模型難以建立；
3.求全局最優(yōu)解的計(jì)算量過(guò)大
4.沒(méi)有太大必要一定要求出全局最優(yōu)解，“比較優(yōu)即可”
二、如何分解為子問(wèn)題

按串行任務(wù)分
時(shí)間串行的任務(wù)，按子任務(wù)來(lái)分解，即每一步都是在前一步的基礎(chǔ)上再選擇當(dāng)前的最優(yōu)解。

按規(guī)模遞減分
規(guī)模較大的復(fù)雜問(wèn)題，可以借助遞歸思想，分解成一個(gè)規(guī)模小一點(diǎn)點(diǎn)的問(wèn)題，循環(huán)解決，當(dāng)最后一步的求解完成后就得到了所謂的“全局最優(yōu)解”。

按并行任務(wù)分
這種問(wèn)題的任務(wù)不分先后，可能是并行的，可以分別求解后，再按一定的規(guī)則（比如某種配比公式）將其組合后得到最終解。

三、如何判段貪心算法的結(jié)果逼近了全局最優(yōu)值

邏輯分析上不會(huì)超過(guò)忍受范圍即可