爬山算法简单示例 [英] Hill climbing algorithm simple example

问题描述

我对爬坡算法有些困惑. 我想运行"算法，直到在树中找到第一个解决方案为止("a"是初始状态，h和k是最终状态)，并且说状态附近的数字是启发式值.这是树:

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:

我的问题: 我正在尝试在树上进行爬山，所以好吧，我们先启动a-> f-> g，然后完成??(没有结果)，但是我读到爬山不能回去并做出新的选择(示例j或e)?这是正确的吗 ? 如果我可以回去，那怎么办?我的意思是，在我们更改初始选择示例的地方，我们选择e代替g或j代替f

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 .

推荐答案

使用Hill Climbing避免陷入局部最大值的一种常见方法是使用随机重启.在您的示例中，如果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.

这篇关于爬山算法简单示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！