愛伊米

今日熱搜丨貪心演算法

貪心的意思

在於在作出選擇時,

每次都要選擇對自身

最為有利的結果,

保證自身利益的最大化。

貪心演算法就是利用

這種貪心思想而得出一種演算法。

關於貪心演算法,一起來了解!

什麼是貪心演算法

貪心演算法(greedy algorithm ,又稱貪婪演算法)是指,在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,該演算法在每個步驟進行最優選擇,試圖找到解決整個問題的總體最優方法。

貪心演算法不是對所有問題都能得到整體最優解,關鍵是貪心策略的選擇 。貪心演算法每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題,在一些最優解問題的求解上表現得更簡單、更迅速。

00:41

  (《科普中國·科學百科:貪心演算法》 來源:新華網)

演算法思路與特點

貪心演算法一般按如下步驟進行:

①建立數學模型來描述問題。

②把求解的問題分成若干個子問題。

③對每個子問題求解,得到子問題的區域性最優解。

④把子問題的區域性最優解合成原來問題的一個解。

貪心演算法的特點是一步一步地進行,常以當前情況為基礎根據某個最佳化測度作最優選擇,而不考慮各種可能的整體情況,省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心演算法採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇,就將所求問題簡化為一個規模更小的子問題,透過每一步貪心選擇,可得到問題的一個最優解。雖然每一步上都要保證能獲得區域性最優解,但由此產生的全域性解有時不一定是最優的,所以貪心演算法不要回溯。

存在問題

貪心演算法存在如下問題:

1。不能保證解是最佳的。

2。貪心演算法一般用來解決求最大或最小解。

3。貪心演算法只能確定某些問題的可行性範圍。

在許多問題中,貪心演算法並不會產生最優解,因為貪婪演算法沒有考慮到所有的資料,當前結果都是基於它前一步的資料而計算出的區域性最優結論,缺乏瞻前顧後和統籌全域性的能力。所以在貪婪演算法失敗的問題中,動態規劃可能會是更好的選擇。

應用例項

如果求解問題具有貪婪選擇屬性與最優子結構屬性,則可以使用貪心演算法解決。貪婪選擇屬性是指透過在每個步驟中選擇最優選擇,可以得到一個全域性(總體)最優解。最優子結構是指如果整個問題的最優解包含子問題的最優解,那麼問題就有最優子結構。

想象我們要進行一場徒步旅行,目標是到達可能的最高峰。在開始之前我們已經有了地圖,但是地圖上顯示了多條可能的路徑。我們沒有時間去評估每條路徑,就採取貪心演算法,只選擇坡度最大的路徑。這似乎是一個很好的遠足策略,但它總是最好的嗎?旅行結束後,我們再次檢視遠足地圖,可能會發現那裡有一條泥濘的河,穿過它就能更容易到達峰頂。這意味著貪心演算法總是選擇最好的即時路徑,而不一定是最終的最佳路徑。在最佳化解決方案方面,這意味著貪婪的解決方案在嘗試尋找區域性最優解時,可能錯過了一個全域性最優解。

有很多經典的應用,比如霍夫曼編碼,普利姆和克魯斯卡爾最小生成樹演算法,還有迪傑斯特拉單源最短路徑演算法,都是使用了這種思維。

再例如,平時購物找零錢時,為使找回的零錢的硬幣數最少,不要求找零錢的所有方案,而是從最大面值的幣種開始,按遞減的順序考慮各面額,先儘量用大面值的面額,當不足大面值時才去考慮下一個較小面值,這就是貪心演算法。

01:11

  (節選自《貪心演算法基本原理》 來源:“學習強國”學習平臺)

(來源:綜合科普中國 · 科學百科、全國科學技術名詞審定委員會等)