貪婪算法和最陡峭算法有什麼區別？

我有幻燈片，其中2個版本的本地搜索算法進行比較：貪婪和最陡。貪婪算法和最陡峭算法有什麼區別？

貪婪：生成解決方案x; 重複 { 爲在N-以隨機順序每個y（X） { 如果 F（Ý）> F（X）然後 X = y; } } 直到沒有更好的溶液發現

最速：生成溶液X; 重複 { 找到最好溶液ý在N（X）; 如果 F（Ý）> F（X）然後 X = ÿ; } 直到沒有更好的解決辦法發現

但是無論在互聯網上，我讀了最好貪心方法搜索（而不是先找到更好的）解決方案。那麼區別是什麼呢？並且：哪個版本是真的？

來源

2011-10-24 Marcin Robaszyński

我同意貪婪也意味着最陡峭，因爲它試圖使locally optimal choice。對我而言，區別在於最速下降/梯度下降的概念與函數優化密切相關，而在組合優化的情況下經常會聽到貪婪。然而，兩者都描述了相同的「策略」。

在我看來，這些概念不太適合描述你想要描述的行爲。我更喜歡術語最佳改進和第一次改進本地搜索。貪婪的本地搜索和最陡峭的下降方法都是本地搜索方法的最佳改進。

使用正則表達式，貪婪具有類似的含義：考慮與通配符表達式最大可能的匹配。說出貪婪的匹配會匹配第一種可能性也是錯誤的。

來源

2011-10-24 17:52:43 Andreas

http://en.wikipedia.org/wiki/Hill_climbing：「在簡單的爬山中，選擇了第一個較近的節點，而在最陡峭的爬坡爬坡中，所有的後繼者都進行了比較，並且選擇了最靠近解決方案」 http://en.wikipedia.org/wiki/Local_search_%28constraint_satisfaction%29（爬山是貪婪算法）。看起來最陡峭的是某種貪婪。 –

貪婪算法和最陡峭算法有什麼區別？

回答

相關問題