爬山算法简单的例子

Question

我对Hill Climbing算法有点困惑.我想"运行"算法,直到我找到该树中的第一个解决方案("a"是初始,h和k是最终状态),并且它表示状态附近的数字是启发式值.这是树:

我的问题:我正在尝试在树上爬山,所以我们可以开始 - > f-> g然后完成(没有结果),但我读到登山不能回去做一个新选择(例如j或e)？这是正确的吗 ？如果我可以回去怎么样？我的意思是我们改变我们的初始选择示例,我们选择e而不是g或j而不是f

对不起,如果我的问题太简单了.

Answer 1

使用Hill Climbing避免陷入局部最大值的常用方法是使用随机重启.在您的示例中,如果G是局部最大值,算法将停在那里,然后选择另一个随机节点重新启动.因此,如果选择J或C(或可能是A,B或D),您会发现H或K中的全局最大值.冲洗并重复足够的次数,您将找到全局最大值或接近的值; 取决于时间/资源限制和问题空间.

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

Answer 2

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

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