“爬山”算法和“贪心”算法有什么区别？

Question

29

请解释“爬山算法”和“贪心算法”的区别。它们看起来很相似，我怀疑“爬山算法”是一种算法；它似乎是一种优化。这正确吗？

- Yabert Yanuar

2个回答

7

是的，您说得对。爬山算法是一种常见的数学优化技术（请参阅：http://en.wikipedia.org/wiki/Hill_climbing）。贪心算法是指任何只选择当前看到的最佳选择并采取它的算法。

一个例子是在最小化硬币数量的情况下找零（至少在美元的情况下）。您首先拿最高面额的硬币，然后拿次高的，直到达到所需金额。

这样，爬山算法就是一种贪心算法。

- jli

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- RobertR · Accepted Answer

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

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

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

一个优化问题的很好示例是0-1背包。在这个问题中，有一个带有特定重量限制的背包，以及一堆要放入背包中的物品。每件物品都有重量和价值。目标是在保持重量限制的情况下，最大化背包中物品的价值。

贪婪算法将选择具有最高密度的物品，并将其放入背包中，直到装满为止。例如，与砖块相比，钻石具有较高的价值和较小的重量，因此我们会首先把钻石放入其中。

这里是一个贪婪算法失败的例子：假设您有一个容量为100的背包。你有以下物品：

- 钻石，价值1000，重量90（密度= 11.1） - 5个金币，价值210，重量20（每个密度= 10.5）

贪婪算法将放入钻石然后结束，从而得到价值1000。但最优解决方案是包括5个金币，从而获得价值1050。