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

Question

我有幻灯片，比较了 2 个版本的本地搜索算法：贪婪和最陡。

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

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

但是我在互联网上到处都读到贪婪的方法会寻找最好的（不是第一个更好的）解决方案。那么区别是什么呢？并且：哪个版本是真的？

Answer 1

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

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

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