我对爬山算法有点困惑。 我希望能够“运行”该算法，直到在树中找到第一个解（“a”是初始状态，“h”和“k”是最终状态），并且标示在状态旁边的数字是启发式值。下面是这棵树：
我的问题是： 我试图在树上运行爬山算法，所以我们从a开始->f->g，然后呢？结束(没有结果)，但我读过爬山算法不能回溯并做出新的选择（例如j或e）？这是正确的吗？ 如果我可以回溯，那么怎么办？我的意思是，在哪里更改我们的初始选择，例如我们选择e而不是g或j而不是f
如果我的问题太简单，请见谅。
爬山算法简单示例
16
- Iakob Fokas
2
http://zh.wikipedia.org/wiki/%E5%B1%B1%E5%BD%A2%E6%90%9C%E7%B4%A2 - 有趣 - jon
爬山算法是一种局部搜索。您需要在状态之间定义某种邻居关系。通常，这种关系是对称的。您有一个有向树，它让我想起了搜索树。这个问题把事情搞混了。 - ziggystar
7个回答
14
常用的避免Hill Climbing算法陷入局部最大值的方法是使用随机重启。例如，在你的例子中，如果G是一个局部最大值，算法会在那里停止，然后选择另一个随机节点重新开始。因此，如果选择J或C（或可能是A、B或D），则可以找到H或K的全局最大值。反复进行足够多的随机重启，就可以找到全局最大值或接近全局最大值；这取决于时间和资源限制以及问题空间。
请注意，像Hill Climbing这样的局部搜索算法并不完全，不能保证找到全局最大值。当然，好处是它只需要少量的资源。实践证明，在适合的问题上，它是一个非常有效的解决方案。
请注意，像Hill Climbing这样的局部搜索算法并不完全，不能保证找到全局最大值。当然，好处是它只需要少量的资源。实践证明，在适合的问题上，它是一个非常有效的解决方案。
- Tyson
2
你可以尝试使用一种叫做模拟退火的技术来防止搜索陷入局部最小值。在模拟退火中，有一个参数
T来控制你向次优邻域状态移动的可能性。如果T较高，你更有可能进行次优移动并从局部最小值中逃脱，而如果使用普通的爬山算法，则无法实现这一点。- adijo
1
山峰爬升法的一个问题是会陷入局部最小值，当你到达F时就会发生这种情况。改进版的山峰爬升法（实际上已经被实际使用）是通过在搜索树中选择一个随机节点重新启动整个过程，并继续朝着寻找最优解的方向前进。如果再次陷入某些局部最小值，您必须使用其他随机节点重新开始。通常，您可以重新执行此寻找最优解的过程的次数有限制。达到此限制后，您将从整个过程中到达的所有局部最小值中选择最小值。虽然它仍然不完整，但这个方法有更好的机会找到全局最优解。
- kriti gupta
1
爬山算法无法保证不会陷入局部最小值/最大值。然而，只有最纯粹的爬山算法才不允许你回溯。
一种简单的爬山算法变体是禁忌搜索，它可以避免局部最小值问题（但需要更多时间和内存），其中你记住以前的坏结果并有意避免它们。
一种简单的爬山算法变体是禁忌搜索，它可以避免局部最小值问题（但需要更多时间和内存），其中你记住以前的坏结果并有意避免它们。
- Novak
2
3在爬山算法中，通常不会回溯，因为它是局部搜索，不会跟踪状态，回溯会使你远离最大值。回溯和禁忌搜索都不能回答这个问题：前者只会将您移动到局部最大值处，后者则会阻止您重新访问同一局部最大值。两者都无法帮助您达到全局最大值。 - Tyson
“你记得之前的不良结果并有意避免它们的地方。”我不能同意，你把好的解决方案也标记为禁忌，但你不想再走同样的路。 - Kasper Ziemianek
0
实际上，在爬山算法中，通常不会回溯，因为您没有跟踪状态（它是局部搜索），并且您将远离最大值。回溯和禁忌搜索都无法回答这个问题：前者只会使您远离局部最大值，而后者会防止您重新访问相同的局部最大值。两者都无法帮助您达到全局最大值。-泰森2012年10月16日22:59
“您记住以前的坏结果并有意避免它们”的说法我不能同意，您还将好的解决方案标记为禁忌，但您不想再次遵循相同的路径。
“您记住以前的坏结果并有意避免它们”的说法我不能同意，您还将好的解决方案标记为禁忌，但您不想再次遵循相同的路径。
- vikas sharma
0
这里是解决方案：
A->F，成本最小为 F->G 成本为3，但没有路径。
从除 G 以外最小的成本重新开始，很好，它是 E，因为 E 已经插入队列/堆栈/优先级队列或您使用的任何数据结构。
因此，E->I，但 I 的成本更高，因此您卡住了：S
从 F，E 和 G 之外的最小成本重新开始，因此我们选择 J，因为 J 的成本比 B 低 2，即 J = 8，B = 10。
J->K 成本为 0，因此 K 是目标。
注意：建议的变化是随机选择一个点，但选择除已访问节点以外的最小成本比随机选择更好。
另一个注意事项是当节点 E 没有访问 I 因为 I 比 E 更高时，算法已将其插入数据结构中，因此选择除已访问节点以外的最小成本将创建来自 I 的新路径，因为从未访问过 I，因此它的值比 J 低，这是我跳过的唯一路径。
A->F，成本最小为 F->G 成本为3，但没有路径。
从除 G 以外最小的成本重新开始，很好，它是 E，因为 E 已经插入队列/堆栈/优先级队列或您使用的任何数据结构。
因此，E->I，但 I 的成本更高，因此您卡住了：S
从 F，E 和 G 之外的最小成本重新开始，因此我们选择 J，因为 J 的成本比 B 低 2，即 J = 8，B = 10。
J->K 成本为 0，因此 K 是目标。
注意：建议的变化是随机选择一个点，但选择除已访问节点以外的最小成本比随机选择更好。
另一个注意事项是当节点 E 没有访问 I 因为 I 比 E 更高时，算法已将其插入数据结构中，因此选择除已访问节点以外的最小成本将创建来自 I 的新路径，因为从未访问过 I，因此它的值比 J 低，这是我跳过的唯一路径。
- Mohamed Horani
-1
根据纯爬山算法，路径将是a-> J -> k， 如果您从左到右展开子节点， 如果您从右到左展开它们，则会得到此局部最小值A -> F -> G， 但通常我们从左到右展开。
- sanjay negi
1
在纯爬山算法中，扩展顺序并不重要。每一步都选择最小成本的动作。 - ReZa
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接