Rob*_*rtR 42
爬山和贪婪算法都是可以用于优化问题的启发式算法.在优化问题中,我们通常寻求问题元素的一些最佳组合或排序.给定的组合或排序是一种解决方案.在任何一种情况下,都可以评估解决方案,将其与其他解决方案进
在爬山启发式游戏中,您将从初始解决方案开始.生成一个或多个相邻解决方案.选择最好的并继续,直到没有更好的邻居解决方案.这通常会产生一种解决方案.在爬山时,我们需要知道如何评估解决方案,以及如何生成"邻居".
在贪婪的启发式中,我们需要了解手头的问题.贪心算法使用信息来生成单个解决方案.
优化问题的一个很好的例子是0-1背包.在这个问题中,有一个具有一定重量限制的背包,以及一堆放入背包的物品.每个项目都有一个权重和一个值.目的是最大化背包中物体的价值,同时保持重量在极限之下.
一个贪婪的算法会选择密度最高的物体并将它们放入直到背包已满.例如,与砖相比,钻石具有较高的价值和较小的重量,因此我们将钻石放在首位.
以下是贪婪算法失败的示例:假设您有一个容量为100的背包.您有以下项目:
贪婪的算法将钻石然后完成,给出1000的值.但最佳的解决方案是包括5金币,给出1050的价值.
爬山算法将生成初始解决方案 - 只需随机选择一些项目(确保它们在重量限制之下).然后评估解决方案 - 即确定值.生成相邻解决方案.例如,尝试将一个项目换成另一个项目(确保您仍然在重量限制内).如果它具有更高的值,请使用此选择并重新开始.
爬山不是一种贪婪的算法.
是的，你是对的。爬山是一种通用的数学优化技术（参见：http : //en.wikipedia.org/wiki/Hill_climbing）。贪心算法是任何一种算法，它只是简单地选择它当时看到的最佳选择并接受它。
这方面的一个例子是在最小化硬币数量的同时进行更改（至少是美元）。您使用最高面额的硬币，然后使用次高面额的硬币，直到达到所需的金额。
这样，爬山就是一种贪心算法。
| 归档时间： |
|
| 查看次数： |
22019 次 |
| 最近记录： |