mathematical-optimization - 贪心算法和最陡算法有什么区别？

Question

我有幻灯片比较了两种版本的本地搜索算法:贪婪算法和最陡算法。

贪心: 生成解决方案x； 重复 { 对于 N(x) 中的每个 y 以随机顺序 { 如果 f(y) > f(x) 那么 x = y; } } 直到没有找到更好的解决方案

最陡: 生成解决方案x； 重复 { 在 N(x) 中找到 最佳 解决方案 y； 如果 f(y) > f(x) 那么 x = y; } 直到没有找到更好的解决方案

但是在 Internet 上到处我都读到贪心法搜索最佳(而不是首先找到更好的)解决方案。那么区别是什么呢？并且:哪个版本是正确的？

Answer 1

我同意贪婪也意味着最陡，因为它试图使 locally optimal choice .对我来说，不同之处在于最速下降/梯度下降的概念与函数优化密切相关，而在组合优化的背景下经常听到贪心。然而，两者都描述了相同的“策略”。

在我看来，这些概念不太适合描述您想要描述的行为。我更喜欢术语最佳改进 和第一次改进 本地搜索。贪心局部搜索和最速下降法都是局部搜索的最佳改进方法。

对于正则表达式，贪婪具有类似的含义:考虑与通配符表达式的最大可能匹配。说贪婪匹配会匹配第一种可能性也是错误的。