又稱：貪心算法

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

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

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

圖片來源： 視覺中國

【延伸閱讀】

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

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

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

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

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

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