爬山算法简单例子
我对爬山算法有点困惑。 我想“运行”该算法，直到我找到该树中的第一个解决方案（“a”是初始状态，h 和 k 是最终状态），并且它表示状态附近的数字是启发值。这是树：
我的问题： 我正在尝试在树上爬山，所以好吧，我们开始 -> f-> g然后什么？完成（没有结果），但我读到爬山不能回去并做出新的选择（例如j或e）？这是对的吗？ 如果我可以回去的话怎么办？我的意思是，在我们更改初始选择的示例中，我们选择 e 而不是 g 或 j 而不是 f
抱歉，如果我的问题太简单了。
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 .
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
避免爬山时陷入局部最大值的常见方法是使用随机重新启动。在您的示例中，如果 G 是局部最大值，算法将在那里停止，然后选择另一个随机节点重新启动。因此，如果选择 J 或 C（或者可能是 A、B 或 D），您将在 H 或 K 中找到全局最大值。冲洗并重复足够多次，您将找到全局最大值或接近的值；取决于时间/资源限制和问题空间。
请注意，像爬山这样的本地搜索并不完整，不能保证找到全局最大值。当然，好处是它只需要一小部分资源。在实践中并应用于正确的问题，这是一个非常有效的解决方案。
A common way to avoid getting stuck in local maxima with Hill Climbing is to use random restarts. In your example if G is a local maxima, the algorithm would stop there and then pick another random node to restart from. So if J or C were picked (or possibly A, B, or D) you would find the global maxima in H or K. Rinse and repeat enough times and you'll find the global maxima or something close; depending on time/resource limitations and the problem space.
Note that Local Search like Hill Climbing isn't complete and can't guarantee to find the global maxima. The benefit, of course, is that it requires a fraction of the resources. In practice and applied to the right problems, it's a very effective solution.
您可以尝试使用一种名为模拟退火的技术来防止您的搜索陷入局部最低限度。本质上，在模拟退火中，有一个参数 T 控制着移动到次优邻域状态的可能性。如果 T 较高，您更有可能做出次优移动到相邻状态，从而在卡在那里时可能会逃脱局部最小值，如果您使用正常的爬山，则不会出现这种情况。
You could try to use a technique called simulated annealing to prevent your search to get stuck on to local minimums. Essentially, in simulated annealing, there is a parameter
Tthat controls your likelihood to make a move to sub-optimal neighborhood states. IfTis high, you are more likely to make a sub-optimal move to a neighboring state and thereby might escape a local minimum when stuck there, which you wouldn't if you used normal hill climbing.爬山并不能保证不会陷入局部最小值/最大值。
然而，只有最纯粹的爬山形式才不允许您走回头路。
一个简单的爬山即兴演奏可以避免局部最小值问题（以更多的时间和内存为代价）是禁忌搜索，您可以记住以前的不良结果并有目的地避免它们。
Hill climbing has no guarantee against getting stuck in a local minima/maxima.
However, only the purest form of hill climbing doesn't allow you to either backtrack.
A simple riff on hill climbing that will avoid the local minima issue (at the expense of more time and memory) is a tabu search, where you remember previous bad results and purposefully avoid them.
爬山的问题之一是陷入局部最小值和最小值。这就是当你到达 F 时会发生的情况。 爬山的改进版本（实际上已实际使用）是通过在搜索树中选择一个随机节点并重新开始整个过程。再次继续寻找最佳解决方案。如果您再次陷入某个局部最小值，则必须使用其他随机节点重新启动。一般来说，数量是有限制的。有时间你可以重新执行这个寻找最佳解决方案的过程。达到此限制后，您可以在该过程中达到的所有局部最小值中选择最小的一个。虽然它仍然不完整，但它有更好的机会找到全局最优解。
one of the problems with hill climbing is getting stuck at the local minima & this is what happens when you reach F. An improved version of hill climbing (which is actually used practically) is to restart the whole process by selecting a random node in the search tree & again continue towards finding an optimal solution. If once again you get stuck at some local minima you have to restart again with some other random node. Generally there is a limit on the no. of time you can re-do this process of finding the optimal solution. After you reach this limit, you select the least amongst all the local minimas you reached during the process. Though it is still not complete but this one has better chances of finding the global optimal solution.
实际上，在爬山中，您通常不会回溯，因为您没有跟踪状态（这是本地搜索），并且您将远离最大值。回溯和禁忌搜索都无法回答这个问题：前者只会让你远离局部最大值，而后者会让你无法重新访问相同的局部最大值。两者都不会帮助你达到全局最大值。 – 泰森，2012 年 10 月 16 日，22:59
“你记住以前的坏结果并有目的地避免它们”我不同意，你将好的解决方案标记为禁忌，但你不想再次遵循同样的道路。 –
Actually in Hill Climbing you don't generally backtrack, because you're not keeping track of state (it's local search) and you would be moving away from a maxima. Neither backtracking or Tabu Search help answer the question either: the former just moves you away from a local maxima and the latter keeps you from revisiting the same local maxima. Neither would help you hit a global maxima. – Tyson Oct 16 '12 at 22:59
"where you remember previous bad results and purposefully avoid them" I can't agree, you mark as taboo also good solutions, but You don't want to follow same path again. –
解决方法如下：
A-> F，以尽可能最小的成本F-> G 的成本为 3，但没有路径。
从除 G 之外的最低可能成本重新开始，好吧，它是 E，因为 E 已经插入到队列/堆栈/优先级队列或您使用的任何数据结构中。
因此E-> I 但我的成本比 E 更高，因此你被困住了：S
从 FE 和 FE 之外的最低成本重新启动G，因此我们选择 J，因为 J 的成本比 B 低，差异为 2，即 J = 8 B = 10
J->K，成本为 0，因此 K 是目标
注意：建议的爬山选择点的变体随机，但选择除了已访问过的节点之外成本最低的节点比随机选择要好。
另一个注意事项：当节点 E 没有访问 I 时，因为 I 的值高于 E，算法已经将其插入数据结构中，因此选择除已访问的成本之外的最小成本将创建一条从 I 开始的新路径，因为 I从未被访问过，因此它的值低于 J，这是我跳过的唯一路径。
Here is the solution:
A -> F, with the least possible cost F -> G with cost 3 but there is no path.
Restart from the least possible cost other than G, well it's E because E was already inserted in the queue/stack/priority queue or whatever data structure you use.
Thus E -> I but I has higher cost than E thus you are stuck :S
Restart from the least cost other than F E & G, thus we pick J because J has lower cost than B with difference of 2 i.e. J = 8 B = 10
J->K with cost 0 thus K is the goal
NOTE: The proposed variation of hill-climbing to pick a point randomly, but picking the least cost other than the already visited nodes is better than picking randomly.
ANOTHER NOTE: is that when node E didn't visit I because I has higher value than E, the algorithm already inserted it in the data structure, thus picking the least cost other than the already visited would create a new path from I because I was never visited and thus it has lower value than J, this is the only path that i've skipped.
根据纯爬山的路径将是
一个-> J-> k
如果你把孩子们从左向右展开，
如果你从右向左展开它们，那么你将得到这个局部最小值 A -> F->格,
但一般我们是从左向右展开。
the path according to pure hill climb will be
a-> J -> k
if you expand children's from left to right,
if you expand them from right to left then you will get in this local minima A -> F -> G,
but generally we expand from left to right.