又稱：貪心算法

定義：一種不追求全局最優(yōu)解，只在每一步求得局部最優(yōu)解的算法。

學(xué)科：計(jì)算機(jī)科學(xué)技術(shù)_理論計(jì)算機(jī)科學(xué)_算法設(shè)計(jì)與分析

相關(guān)名詞：算法 最優(yōu)子結(jié)構(gòu)性

圖片來(lái)源： 視覺(jué)中國(guó)

【延伸閱讀】

貪婪算法是一種用于優(yōu)化問(wèn)題的簡(jiǎn)單、直觀的算法。該算法在每個(gè)步驟進(jìn)行最優(yōu)選擇，試圖找到解決整個(gè)問(wèn)題的總體最優(yōu)方法。貪婪算法每做一次貪婪選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，在一些最優(yōu)解問(wèn)題的求解上表現(xiàn)得更簡(jiǎn)單、更迅速。

如果求解問(wèn)題具有貪婪選擇屬性與最優(yōu)子結(jié)構(gòu)屬性，則可以使用貪婪算法解決。貪婪選擇屬性是指通過(guò)在每個(gè)步驟中選擇最優(yōu)選擇，可以得到一個(gè)全局（總體）最優(yōu)解。最優(yōu)子結(jié)構(gòu)是指如果整個(gè)問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解，那么問(wèn)題就有最優(yōu)子結(jié)構(gòu)。

想象我們要進(jìn)行一場(chǎng)徒步旅行，目標(biāo)是到達(dá)可能的最高峰。在開(kāi)始之前我們已經(jīng)有了地圖，但是地圖上顯示了多條可能的路徑。我們沒(méi)有時(shí)間去評(píng)估每條路徑，就采取貪婪算法，只選擇坡度最大的路徑。這似乎是一個(gè)很好的遠(yuǎn)足策略，但它總是最好的嗎？旅行結(jié)束后，我們?cè)俅尾榭催h(yuǎn)足地圖，可能會(huì)發(fā)現(xiàn)那里有一條泥濘的河，穿過(guò)它就能更容易到達(dá)峰頂。這意味著貪婪算法總是選擇最好的即時(shí)路徑，而不一定是最終的最佳路徑。在優(yōu)化解決方案方面，這意味著貪婪的解決方案在嘗試尋找局部最優(yōu)解時(shí)，可能錯(cuò)過(guò)了一個(gè)全局最優(yōu)解。

有很多經(jīng)典的應(yīng)用，比如霍夫曼編碼，普利姆和克魯斯卡爾最小生成樹(shù)算法，還有迪杰斯特拉單源最短路徑算法，都是使用了這種思維。然而，在許多問(wèn)題中，貪婪算法并不會(huì)產(chǎn)生最優(yōu)解，因?yàn)樨澙匪惴](méi)有考慮到所有的數(shù)據(jù)，當(dāng)前結(jié)果都是基于它前一步的數(shù)據(jù)而計(jì)算出的局部最優(yōu)結(jié)論，缺乏瞻前顧后和統(tǒng)籌全局的能力。所以在貪婪算法失敗的問(wèn)題中，動(dòng)態(tài)規(guī)劃可能會(huì)是更好的選擇。

（延伸閱讀作者：大連理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院教授 楊鑫）

責(zé)任編輯：張鵬輝