DSA 貪心演算法

貪心演算法

貪心演算法在每一步都只根據當前情況做出決策，而不考慮整個問題的整體情況。

換句話說，貪心演算法在每一步都做出區域性最優選擇，希望最終能找到全域性最優解。

例如，在 Dijkstra 演算法 中，下一步要訪問的頂點始終是當前到源點距離最短的未訪問頂點，這是從當前已訪問頂點組中看到的。

所以 Dijkstra 演算法是貪心的，因為它選擇下一個要訪問的頂點僅僅基於當前可用的資訊，而不考慮整體問題，或者這個選擇如何影響未來的決策或最終的最短路徑。

選擇貪心演算法是一種設計選擇，就像 動態規劃 是另一種演算法設計選擇一樣。

本教程中的大多數問題，例如排序陣列，或 在圖中找到最短路徑，都具有這些屬性，因此這些問題可以透過貪心演算法解決，例如 選擇排序 或 Dijkstra 演算法。

但是像 旅行商問題 或 0/1 揹包問題 這樣的問題不具備這些屬性，因此不能使用貪心演算法來解決。這些問題將在後面進一步討論。

此外，即使一個問題可以用貪心演算法解決，也可以用非貪心演算法解決。

非貪心演算法

以下是非貪心演算法，意味著它們不只依賴於每一步都做出區域性最優選擇

• 歸併排序：不斷地將陣列分成兩半，然後將陣列部分重新合併，從而得到一個已排序的陣列。這些操作不是貪心演算法那樣的一系列區域性最優選擇。
• 快速排序：選擇主元，圍繞主元排列元素，以及遞迴呼叫對主元左右兩側執行相同操作——這些操作不依賴於做出貪心選擇。
• BFS 和 DFS 遍歷：這些演算法在不透過每一步的區域性選擇來決定如何繼續遍歷的情況下遍歷圖，因此它們不是貪心演算法。
• 使用記憶化查詢第 n 個斐波那契數：此演算法屬於一種稱為 動態規劃 的問題解決方法，它解決重疊子問題，然後將它們重新組合起來。記憶化在每一步中用於最佳化整體演算法，這意味著在此演算法的每一步中，它不僅考慮區域性最優解是什麼，而且還考慮到在此步驟中計算出的結果可能會在後續步驟中使用。

0/1 揹包問題

如前所述，0/1 揹包問題 不能用貪心演算法解決，因為它不滿足貪心選擇性質和最優子結構性質。

這個問題不能用貪心演算法解決，因為每一步選擇價值最高、重量最輕或價值重量比最高的物品（區域性最優解，貪心）並不能保證得到最優解（全域性最優）。

假設您的揹包限重 10 公斤，而您面前有這三件寶物

透過先取價值最高的物品——價值 600 美元的馬雕，做出貪心選擇，意味著您不能再攜帶其他任何物品而不超過重量限制。

因此，透過貪婪的方式解決此問題，您最終得到一個價值 600 美元的金屬馬。

但在此情況下最佳解決方案是攜帶盾牌和陶罐，將揹包的總價值最大化為 800 美元，同時仍低於重量限制。

總是選擇重量最輕的寶物呢？或者總是選擇價值重量比最高的寶物呢？

雖然遵循這些原則實際上可以讓我們在特定情況下找到最佳解決方案，但我們不能保證這些原則在示例中的值和重量改變時也能奏效。

這意味著 0/1 揹包問題無法用貪心演算法解決。

在此處 閱讀更多關於 0/1 揹包問題的資訊。

旅行商問題

旅行商問題 是一個著名的問題，也不能用貪心演算法解決，因為它不滿足前面提到的貪心選擇性質和最優子結構性質。

旅行商問題陳述您是一名推銷員，需要拜訪若干個城市或城鎮進行銷售。

使用貪心演算法，您將總是前往離當前所在城市最近的下一個未訪問城市。但這種情況在大多數情況下並不能為您帶來最短總路徑的最優解。

下面的模擬顯示了當貪心演算法嘗試解決旅行商問題時的樣子。

執行模擬時，演算法的缺陷可能並非總是顯而易見，但您可能會注意到有時線條會交叉，形成更長的總距離，而這顯然是不必要的。

雖然執行旅行商問題的貪心方法有時可以提供最短路線的相當不錯的近似值，但貪心演算法通常無法解決旅行商問題。

旅行商問題不滿足貪心演算法可解所需的性質。

在此處 閱讀更多關於旅行商問題的資訊。