基本介紹
- 中文名：貪心周期
- 外文名：greedy algorithm
- 別稱：貪心算法
- 性質：一種改進了的分級處理方法
- 核心：根據題意選取一種量度標準
- 學科：計算機技術
基本要素,貪心選擇,最優子結構,基本思路,思想,過程,算法特性,
基本要素
貪心選擇
貪心選擇是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規划算法的主要區別。貪心選擇是採用從頂向下、以疊代的方法做出相繼選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題。對於一個具體問題，要確定它是否具有貪心選擇的性質，我們必須證明每一步所作的貪心選擇最終能得到問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步貪心選擇，最終可得到問題的一個整體最優解。
最優子結構
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。運用貪心策略在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動態規划算法求解的關鍵特徵。貪心算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。動態規劃主要運用於二維或三維問題，而貪心一般是一維問題。
基本思路
思想
貪心算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個最佳化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部最佳化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加算法停止。
過程
1.建立數學模型來描述問題；
2.把求解的問題分成若干個子問題；
3.對每一子問題求解，得到子問題的局部最優解；
4.把子問題的解局部最優解合成原來解問題的一個解。
算法特性
貪婪算法可解決的問題通常大部分都有如下的特性：
2.有一個函式來檢查一個候選對象的集合是否提供了問題的解答。該函式不考慮此時的解決方法是否最優。
3.還有一個函式檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函式一樣，此時不考慮解決方法的最優性。
4.選擇函式可以指出哪一個剩餘的候選對象最有希望構成問題的解。
5.最後，目標函式給出解的值。
6.為了解決問題，需要尋找一個構成解的候選對象集合，它可以最佳化目標函式，貪婪算法一步一步的進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函式，算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那么該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優的。
