貪心演算法

出自 MBA智库百科(https://wiki.mbalib.com/)

　　貪心演算法（又稱貪婪演算法）是一種能夠得到某種度量意義下的最優解的分級處理方法，它總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優解演算法。

　　貪心演算法可解決的問題通常大部分都有如下的特性：

　　⑴隨著演算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。

　　⑵有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。

　　⑶還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。

　　⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。

　　⑸最後，目標函數給出解的值。

　　⑹為瞭解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第一個解通常是最優的。

　　貪心演算法是一種改進了的分級處理方法。用貪心法設計演算法的特點是一步一步的進行，根據某個優化測度(可能是目標函數，也可能不是目標函數)，每一步上都要保證能獲得局部最優解。每一步只考慮一個數據，它的選取應滿足局部優化條件。若下一個數據與部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加為止。這種能夠得到某種度量意義下的最優解的分級處理方法成為貪心法。