貪婪演算法

在所有演算法方法中，最簡單直接的方法是貪婪方法。在這種方法中，決策是基於當前可用的資訊做出的，而不考慮當前決策對未來的影響。

貪婪演算法逐部分構建解決方案，選擇下一部分的方式是，它能帶來直接的收益。這種方法永遠不會重新考慮之前做出的選擇。這種方法主要用於解決最佳化問題。貪婪方法易於實現，並且在大多數情況下都非常高效。因此，我們可以說貪婪演算法是一種基於啟發式的演算法正規化，它在每個步驟都遵循區域性最優選擇，希望找到全域性最優解。

在許多問題中，它雖然不能產生最優解，但在合理的時間內給出了一個近似（接近最優）的解。

貪婪演算法的組成部分

貪婪演算法具有以下五個組成部分：

• 候選集 - 從該集合中建立解決方案。

• 選擇函式 - 用於選擇要新增到解決方案中的最佳候選者。

• 可行性函式 - 用於確定候選者是否可以用於為解決方案做出貢獻。

• 目標函式 - 用於為解決方案或部分解決方案分配一個值。

• 解決方案函式 - 用於指示是否已達到完整解決方案。

應用領域

貪婪方法用於解決許多問題，例如

• 使用 Dijkstra 演算法查詢兩個頂點之間的最短路徑。

• 使用 Prim/Kruskal 演算法等查詢圖中的最小生成樹。

硬幣計數問題

硬幣計數問題是透過選擇最少的硬幣來計算到一個期望值，貪婪方法強制演算法選擇儘可能大的硬幣。如果我們提供 1、2、5 和 10 的硬幣，並要求我們計算 18，則貪婪過程將是：

• 1 - 選擇一枚 10 元硬幣，剩餘計數為 8

• 2 - 然後選擇一枚 5 元硬幣，剩餘計數為 3

• 3 - 然後選擇一枚 2 元硬幣，剩餘計數為 1

• 4 - 最後，選擇一枚 1 元硬幣解決了問題

雖然，這似乎工作正常，但對於此計數，我們只需要選擇 4 枚硬幣。但是，如果我們稍微更改一下問題，則相同的方法可能無法產生相同的最優結果。

對於我們有 1、7、10 值的硬幣的貨幣系統，計算 18 值的硬幣將是絕對最優的，但對於 15 這樣的計數，它可能使用的硬幣多於必要。例如，貪婪方法將使用 10 + 1 + 1 + 1 + 1 + 1，總共 6 枚硬幣。而同樣的問題可以用 3 枚硬幣（7 + 7 + 1）解決

因此，我們可以得出結論，貪婪方法選擇一個直接的最佳化解決方案，並且在全域性最佳化是一個主要問題的地方可能會失敗。

貪婪方法在哪裡失效

在許多問題中，貪婪演算法無法找到最優解，此外它可能會產生最差的解。旅行商和揹包等問題不能使用這種方法解決。

貪婪演算法的示例

大多數網路演算法都使用貪婪方法。以下列出其中的一些：

• 旅行商問題

• Prim 最小生成樹演算法

• Kruskal 最小生成樹演算法

• Dijkstra 最小生成樹演算法

• 圖 - 地圖著色

• 圖 - 頂點覆蓋

• DSA - 分數揹包問題

• DSA - 帶截止日期的作業排序

• DSA - 最佳合併模式演算法

我們將在本教程的後續章節中詳細討論這些示例。