貪心演算法 啟發式演算法 近似演算法 區別？

個人理解貪心演算法和啟發式演算法均為近似演算法，但貪心演算法和啟發式演算法有什麼區別呢？謝謝！

---

近似演算法是一個大類。所有對於有確切最優解但是並不能保證得到最優解的演算法都可以稱之為近似演算法。

貪心演算法不一定就是近似演算法，如果可以證明決策既不受之前決策的影響，也不影響後續決策，則貪心演算法就是確定的最優解演算法。除此之外都不可以保證貪心演算法是最優的。（這裡有個很有意思的事情是，某種意義上動態規劃方法就是將原問題變形為貪心可解的問題，因此對於每個狀態只需要保留最優決策既）

啟發式演算法則是一個折中。我們知道對於大多數問題而言純粹的遍歷所有狀態總比貪心來的慢，但是貪心得到確切解的前提很苛刻，因此很有可能會得到很爛的解。啟發式演算法則是通過一個啟發函數對下一階段狀態進行粗略評估，這個評估是預計結果（並不確信）；在遍歷狀態的過程中，我們優先去看可能可以得到好結果的情況，並且如果發現一個狀態的理想估計比當前確實遍歷過的解中最好的要差則可以放棄，這就叫啟發式演算法，這裡我們叫確定性啟發式演算法或者啟發式搜索。然而啟發式搜索的本質仍舊是遍歷所有狀態，要保證確定最優解，它仍舊是個遍歷，耗時仍然有可能很大。這個情況下加入一條限制：如果計算時間已經到達可承受的極限，則放棄剩下部分的搜索直接以當前找到的最好結果為結果，這樣的啟發式演算法自然是非確定性的，於是可以算作近似演算法。

---

對於優化問題的解決方法， 有2類， 分別是 確定方式和近似方式（ Exact Method， Approximate Method）

對於優化問題. 根據條件，和限制， 可以描繪出一個解集空間（Solution Space）， 確定演算法， 只可用在解集空間很小的問題， 但對於NP hard 問題， 可行時間內在個空間中找到 全局最優解（Global Optimum ） 的可能性很小 （ 幾乎不可能）。 故需要使用近似演算法（Approximate Method） 在有限時間內來尋找一個近似最優解。 近似方法分為兩種 分別為 近似演算法（Approximate Algorithms） 和啟發式演算法（ Heuristic Algorithms)。 近似演算法通常可得到一個有質量保證的解。 然而 啟發式演算法通常可找到在傳統解決問題的經驗中找到尋求一種面向問題的策略， 之後用這種策略來在可行時間內尋找一個相對比較好的解，但對解的質量沒有保證。

再說貪心演算法（ Greedy Algorithms） 。

貪心演算法通常用來在生成初始解時使用， 貪心演算法的確屬於啟發式演算法的一種形式和應用。 使用貪心演算法的方式： 把優化問題劃分成一個元素集， 每一步使用每種貪心啟發（ Greedy Heuristic) 來尋找下一個生成部分解說用的元素或者方法。 循環進行， 知道生成一個可行解。

另外。 目前沒有找到相關文獻指明 Hill Climbing 等優化搜索演算法（Local Search ） 屬於貪心演算法。

參考： 《 Metaheuristic from Design to Implement》 2009 Talbi

---

貪心演算法是一種啟發式演算法，它企圖尋求局部最優解，容易陷入局部最優的困境。所以後來有了元啟發式演算法，如蟻群演算法，模擬退火演算法，禁忌演算法等等，這類演算法通過一些策略，某種程度上可以跳出局部最優解，從而尋求更好的全局最優解。但所有啟發式演算法都有缺陷，要視具體問題而定。

---

推薦閱讀：