貪心演算法的組成部分
演算法旨在為給定問題找到最優解。在貪心演算法方法中，從給定的解空間中做出決策。由於貪婪，選擇最接近看起來提供最優解的解。
貪心演算法試圖找到區域性最優解，這最終可能導致全域性最優解。但是，通常貪心演算法不會提供全域性最優解。
貪心演算法的組成部分
貪心演算法具有以下五個組成部分：
候選集 - 從此集合中建立解決方案。
選擇函式 - 用於選擇要新增到解決方案中的最佳候選者。
可行性函式 - 用於確定候選者是否可以用於為解決方案做出貢獻。
目標函式 - 用於為解決方案或部分解決方案分配值。
解決方案函式 - 用於指示是否已達到完整解決方案。
應用領域
貪心方法用於解決許多問題，例如
使用 Dijkstra 演算法查詢兩個頂點之間的最短路徑。
使用 Prim/Kruskal 演算法等在圖中找到最小生成樹。
貪心方法在哪裡失敗
在許多問題中，貪心演算法無法找到最優解，此外它可能產生最差的解。旅行商問題和揹包問題等問題無法使用這種方法解決。
計算硬幣
此問題是透過選擇儘可能少的硬幣來計算到期望值，貪心方法強制演算法選擇儘可能大的硬幣。如果我們提供了 1、2、5 和 10 元的硬幣，並且我們被要求計算 18 元，那麼貪婪過程將是。
選擇一枚 10 元硬幣，剩餘計數為 8。
然後選擇一枚 5 元硬幣，剩餘計數為 3。
然後選擇一枚 2 元硬幣，剩餘計數為 1。
最後，選擇一枚 1 元硬幣解決了這個問題。
雖然看起來工作正常，但對於此計數，我們只需要選擇 4 枚硬幣。但是，如果我們稍微更改問題，則相同的方法可能無法產生相同的最優結果。
對於我們有 1、7、10 值硬幣的貨幣系統，計算 18 值的硬幣將是絕對最優的，但對於像 15 這樣的計數，它可能使用的硬幣多於必要。例如，貪心方法將使用 10 + 1 + 1 + 1 + 1 + 1，總共 6 枚硬幣。而相同的問題可以透過僅使用 3 枚硬幣 (7 + 7 + 1) 來解決
因此，我們可以得出結論，貪心方法選擇一個立即的最優解，並且在全域性最佳化是主要關注點的地方可能會失敗。