问“爬山”和“贪婪”算法的区别是什么？

EN

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

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

在贪婪启发式中，我们需要知道一些关于手头问题的特殊信息。贪婪算法使用信息来产生单一的解决方案。

优化问题的一个很好的示例是0-1背包。在这个问题中，有一个有一定重量限制的背包，以及一堆要放在背包里的物品。每一项都有一个权重和一个值。目标是最大化背包中物体的价值，同时将重量保持在限制之下。

贪心算法会挑选密度最高的物体，并将它们放入背包中，直到背包装满为止。例如，与砖块相比，钻石具有高价值和小重量，因此我们将钻石放在第一位。

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

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

贪婪算法将放入菱形，然后完成，给出的值为1000。但是最好的解决方案是包括5个金币，给出1050的价值。

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

爬山不是贪婪的算法。

是的，你是对的。爬山是一种通用的数学优化技术(参见：http://en.wikipedia.org/wiki/Hill_climbing)。贪婪算法是任何算法，它只是简单地选择它当时看到的最好的选择并采取它。

这方面的一个例子是在最小化硬币数量的同时进行更改(至少使用USD)。你取最高面额的硬币，然后取最高面额的硬币，直到你达到所需的数额。

在这种情况下，爬山是一种贪婪的算法。