artificial-intelligence - Hill climbing algorithm simple example

Question

I am a little confused with Hill Climbing algorithm. I want to "run" the algorithm until i found the first solution in that tree ( "a" is initial and h and k are final states ) and it says that the numbers near the states are the heuristic values. Here's the tree:

My question : i am trying to run hill climbing on the tree, so ok we start a-> f-> g and then what ??finish(without result) , but I read that hill climbing can't go back and make a new choice(example j or e) ? Is this right ? If i can go back then how ? i mean where we change our initial choice example we choose e instead of g or j instead of f

Sorry if my question is too simple .

Answer 1

避免在爬山时陷入局部最大值的一种常见方法是使用随机重启。在您的示例中，如果 G 是局部最大值，则算法将停在那里，然后选择另一个随机节点重新启动。因此，如果选择了 J 或 C（或者可能是 A、B 或 D），您会在 H 或 K 中找到全局最大值。冲洗并重复足够多的时间，您会找到全局最大值或类似的东西；取决于时间/资源限制和问题空间。

请注意，像爬山这样的本地搜索并不完整，不能保证找到全局最大值。当然，好处是它只需要一小部分资源。在实践中并应用于正确的问题，这是一个非常有效的解决方案。

Answer 2

您可以尝试使用一种称为模拟退火的技术来防止您的搜索陷入局部最小值。本质上，在模拟退火中，有一个参数T可以控制您转向次优邻域状态的可能性。如果T是高，您更有可能做出次优移动到邻近状态，因此可能会在卡在那里时逃脱局部最小值，如果您使用正常的爬山，您就不会这样做。

Answer 3

爬山并不能保证不会陷入局部最小值/最大值。然而，只有最纯粹的爬山形式不允许你回溯。

一个简单的关于爬山的即兴表演，可以避免局部最小值问题（以更多的时间和记忆为代价）是禁忌搜索，你可以记住以前的坏结果并有目的地避免它们。

Answer 4

爬山的问题之一是卡在局部最小值，这就是当你到达 F 时发生的情况。爬山的改进版本（实际上已实际使用）是通过在搜索树并再次继续寻找最佳解决方案。如果您再次陷入某个局部最小值，则必须使用其他一些随机节点再次重新启动。一般来说，数量是有限制的。您有时可以重新执行此过程以找到最佳解决方案。达到此限制后，您在此过程中达到的所有局部最小值中选择最少的。虽然它仍然不完整，但这个有更好的机会找到全局最优解。

Answer 5

这是解决方案：

A -> F，成本最低 F -> G，成本为 3，但没有路径。

从 G 以外的最低成本重新开始，它是 E，因为 E 已经插入到队列/堆栈/优先级队列或您使用的任何数据结构中。

因此 E -> I 但我的成本比 E 高，因此你被卡住了：S

从除 FE 和 G 之外的最低成本重新开始，因此我们选择 J，因为 J 的成本低于 B，差异为 2 即 J = 8 B = 10

J->K，成本为 0，因此 K 是目标

注意：建议的爬山变体随机选择一个点，但选择除了已经访问过的节点之外的成本最低的节点比随机选择要好。

另一个注意事项：当节点 E 没有访问 I 因为我的值比 E 高时，算法已经将它插入到数据结构中，因此选择除了已经访问过的成本之外的最小成本将从 I 创建一条新路径，因为我从未访问过，因此它的价值低于 J，这是我跳过的唯一路径。

Answer 6

实际上，在爬山中，您通常不会回溯，因为您没有跟踪状态（这是本地搜索）并且您将远离最大值。回溯或禁忌搜索都不能帮助回答这个问题：前者只会让你远离局部最大值，而后者会让你无法重新访问相同的局部最大值。两者都不会帮助您达到全局最大值。– 泰森 2012 年 10 月 16 日 22:59

“你记得以前的坏结果并有目的地避免它们”我不能同意，你标记为禁忌也是好的解决方案，但你不想再走同样的路。–

Answer 7

根据纯爬山的路径将是 a-> J -> k 如果你从左到右扩展孩子，如果你从右到左扩展他们，那么你将进入这个局部最小值 A -> F -> G，但是一般我们从左到右展开。