-
貪心算法
鎖定
貪心算法算法思路
貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行,根據某個優化測度,每一 步都要確保能獲得局部最優解。每一步只考慮一 個數據,其選取應該滿足局部優化的條件。若下 一個數據和部分最優解連在一起不再是可行解時, 就不把該數據添加到部分解中,直到把所有數據枚舉完,或者不能再添加算法停止。
[9]
貪心算法是一種對某些求最優解問題的更簡單、更迅速的設計技術。貪心算法的特點是一步一步地進行,常以當前情況為基礎根據某個優化測度作最優選擇,而不考慮各種可能的整體情況,省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪心算法採用自頂向下,以迭代的方法做出相繼的貪心選擇,每做一次貪心選擇,就將所求問題簡化為一個規模更小的子問題,通過每一步貪心選擇,可得到問題的一個最優解。雖然每一步上都要保證能獲得局部最優解,但由此產生的全局解有時不一定是最優的,所以貪心算法不要回溯
[2]
。
貪心算法算法特性
貪心算法使用條件
1、貪心選擇性質
一個問題的整體最優解可通過一系列局部的最優解的選擇達到,並且每次的選擇可以依賴以前作出的選擇,但不依賴於後面要作出的選擇。這就是貪心選擇性質。對於一個具體問題,要確定它是否具有貪心選擇性質,必須證明每一步所作的貪心選擇最終導致問題的整體最優解
[4]
。
2、最優子結構性質
當一個問題的最優解包含其子問題的最優解時,稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心法求解的關鍵所在。在實際應用中,至於什麼問題具有什麼樣的貪心選擇性質是不確定的,需要具體問題具體分析
[4]
。
貪心算法解題策略
貪心算法不從整體最優上加以考慮,所做出的僅是在某種意義上的局部最優選擇。使用貪心策略要注意局部最優與全局最優的關係,選擇當前的局部最優並不一定能推導出問題的全局最優。貪心策略解題需要解決以下兩個問題:
[5]
要確定一個問題是否適合用貪心算法求解,必須證明每一步所作的貪心選擇最終導致問題的整體最優解。證明的大致過程為:首先考察問題的一個整體最優解,並證明可修改這個最優解,使其以貪心選擇開始,做了貪心選擇後,原問題簡化為規模更小的類似子問題。然後用數學歸納法證明通過每一步做貪心選擇,最終可得到問題的整體最優解
[5]
。
貪心算法存在問題
貪心算法應用實例
例如,平時購物找零錢時,為使找回的零錢的硬幣數最少,不要求找零錢的所有方案,而是從最大面值的幣種開始,按遞減的順序考慮各面額,先儘量用大面值的面額,當不足大面值時才去考慮下一個較小面值,這就是貪心算法
[7]
。
- 參考資料
-
- 1. 康桂花主編,計算概論,中國鐵道出版社,2016.08,第123頁
- 2. 謝翌,江渝川主編,大學計算機 計算思維與應用,重慶大學出版社,2017.01,第58頁
- 3. 劉寶芹著,鋼結構設計軟件模型、算法及應用研究,知識產權出版社,2013.04,第66頁
- 4. 補錄,計算機算法設計與分析研究,新華出版社,2015.09,第88頁
- 5. 甘勇,李曄,盧冰編著,C語言程序設計,中國鐵道出版社,2015.09,第331頁
- 6. 陳業綱著,計算機算法基礎,西南交通大學出版社,2015.02,第62頁
- 7. 陳鋭編著,c/c++函數與算法速查手冊,中國鐵道出版社,2012.01,第682頁
- 8. “學習強國”學習平台 .全國科學技術名詞審定委員會[引用日期2022-04-23]
- 9. 常友渠,肖貴元,曾敏.貪心算法的探討與研究[J].重慶電力高等專科學校學報,2008,13(3):40-4247