贪心算法

贪心算法（英語：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。^[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

一般人换零钱的時候也會應用到貪心算法。把$36換散︰$20 > $10 > $5 > $1

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码......对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情況，選擇最優的解，可能會導致辛普森悖論（Simpson's Paradox），不一定出現最優的解。

貪心算法在数据科学領域被广泛應用，特別是金融工程。其中一個貪心算法例子就是Ensemble method。

適用條件

一個問題要能用貪婪法解，必須同時具備以下兩個性質

貪婪選擇性質

表示在求解過程中，只要每一步都選擇當下看起來最好的選項，就能逐步導向整體的最佳解。貪婪演算法依循這種性質，會先做出一個局部最佳的選擇，接著再處理規模縮小後的子問題。這種方法的關鍵在於「一旦做出選擇，就不會回頭修改」，也不會檢查所有子問題的完整解答，只專注於當前狀態下的最優選擇。這正是它與動態規劃的根本差異：動態規劃會窮舉所有可能的決策路徑，並根據之前所有階段的結果決定後續行動，甚至可能回頭調整先前的決策，以保證能找到全域最優解。

最優子結構

表示它的整體最優解必定可以由各個子問題的最優解組合而成。這種性質也是動態規劃所依賴的基礎。

细节

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

实现该算法的过程：
从问题的某一初始解出发；while 能朝给定总目标前进一步 do，求出可行解的一个解元素；
最后，由所有解元素组合成问题的一个可行解。

應用

圖論的最小生成樹的算法如Prim算法、Kruskal算法就是應用的例子。(Prim演算法是对图上的节点贪心，Kruskal演算法是对图上的边贪心。)

但有兩點需要注意

• 對於大部分的問題，貪心法通常都不能找出最佳解（不過也有例外），因為他們一般沒有測試所有可能的解。貪心法容易過早做決定，因而沒法達到最佳解。例如，所有對圖著色問題。
• 贪心法在系统故障诊断策略生成乃至高校的排课系统中都可使用。^[1][2]

針對第一點的簡單例子，在陣列[1,49,50]求出最少組成98加法，貪婪法第一步會是50(當下最好選項)，這導致後面需要48個1，但最好情況是2個49，該問題不滿足貪婪選擇性質，當前選擇會導向壞結果

参见

• 动态规划
• 最长公共子序列
• Floyd-Warshall算法
• Viterbi算法