algorithm - "hill climbing"和 "greedy"算法有什么区别？

Question

请解释“爬山”和“贪心”算法的区别。

看起来两者很相似，我怀疑“爬山”是一种算法；这似乎是一种优化。这是正确的吗？

Answer 1

爬山算法和贪心算法都是可用于优化问题的启发式算法。在优化问题中，我们通常寻求问题元素的某种最佳组合或排序。给定的组合或排序是一个解决方案。在任何一种情况下，都可以评估解决方案以将其与其他解决方案进行比较。

在爬山启发式中，您从初始解决方案开始。生成一个或多个相邻的解决方案。选择最好的并继续，直到没有更好的相邻解决方案。这通常会产生一个解决方案。在爬山中，我们需要知道如何评估一个解决方案，以及如何生成一个“邻居”。

在贪婪启发式中，我们需要了解手头问题的一些特殊信息。贪心算法使用信息来生成单个解决方案。

优化问题的一个很好的示例是 0-1 背包。在这个问题中，有一个有一定重量限制的背包，以及一堆要放在背包里的元素。每个项目都有一个重量和一个值。目的是在保持重量不超过限制的情况下，使背包中元素的值(value)最大化。

贪婪算法会挑选密度最高的物体并将它们放入背包中，直到背包装满。比如，钻石相对于砖头来说，值(value)高，重量小，所以我们会把钻石放在第一位。

这里有一个贪心算法失败的例子:假设你有一个容量为 100 的背包。你有以下元素:

• 钻石，值(value) 1000，重量 90(密度 = 11.1)
• 5枚金币，值(value)210，重量20(每枚密度=10.5)

贪心算法会放入钻石然后完成，给出1000的值(value)。但最佳解决方案是包括5个金币，给出1050的值(value)。

爬山算法会生成一个初始解决方案——只是随机选择一些项目(确保它们在重量限制之下)。然后评估解决方案——即确定值(value)。生成相邻解。例如，尝试将一件元素换成另一件(确保您仍在重量限制之内)。如果它具有更高的值，请使用此选择并重新开始。

爬山不是贪心算法。