「爬山」和「貪婪」算法有什麼區別？

Question

請解釋「爬山」和「貪婪」算法的區別。

看起來兩者都是相似的，我懷疑「爬山」是一種算法;它似乎是一個優化。它是否正確？

Answer 1

爬山和貪婪算法都可以用於優化問題的啓發式算法。在優化問題中，我們通常尋求問題元素的一些最佳組合或排序。給定的組合或排序是一種解決方案。無論哪種情況，都可以評估解決方案，將其與其他解決方案進行比較

在爬山啓發式，你從一個初始的解決方案開始。生成一個或多個相鄰的解決方案。挑選最好的並繼續，直到沒有更好的鄰居解決方案。這通常會產生一個解決方案。在爬山時，我們需要知道如何評估解決方案，以及如何生成「鄰居」。

在貪心啓發式，我們需要知道一些特殊的問題在眼前。貪婪算法使用信息來生成單個解決方案。

好的例子的一個優化問題是0-1揹包。在這個問題中，有一個有一定重量限制的揹包，以及一堆放在揹包裏的物品。每個項目都有一個權重和一個值。目標是在保持重量低於極限的同時最大化揹包中物體的價值。

一個貪婪的算法會選擇密度最高的物體，並將它們放入，直到揹包滿了。例如，與磚相比，鑽石具有很高的價值和很小的重量，所以我們會先把鑽石放在第一位。

這裏是哪裏貪心算法會失敗的例子：假設你有能力100.你必須包含下列項目的揹包：

• 鑽石，價值1000，重量90（密度= 11.1）
• 5金幣，值210，重量20（密度=每10.5）

貪婪算法將放於金剛石，然後進行，得到的1000值，但最佳的解決辦法是包括5金幣，價值1050.

爬山算法會產生一個初始解 - 只是隨機選擇一些項目（確保它們在重量限制之下）。然後評估解決方案 - 即確定價值。生成相鄰的解決方案。例如，嘗試交換一個項目（確保您仍然在重量限制之下）。如果此值較高，請使用此選項並重新開始。

爬山不是貪心算法。

Answer 2

是的你是對的。爬山是一種通用的數學優化技術（請參閱：http://en.wikipedia.org/wiki/Hill_climbing）。貪婪算法是任何算法，它只是選擇它在當時看到的最佳選擇並採取它。

這方面的一個例子是在最小化硬幣數量的同時進行更改（至少使用美元）。你把硬幣的最高面額，然後是最高的面額，直到你達到所需的金額。

這樣，爬山是的一種貪心算法。