我对爬山算法有点困惑。我想“运行”算法,直到我在该树中找到第一个解( "a“是初始状态,h和k是最终状态),它说状态附近的数字是启发式的值。这是这棵树:
我的问题是:我正试着在树上爬山,所以我们开始a-> f-> g,然后呢??结束(没有结果),但我读到爬山不能返回并做出新的选择(例如j或e)?是这样的吗?如果我能回到过去,那该怎么做呢?我的意思是,在我们改变初始选择示例的地方,我们选择e而不是g,或者j而不是f
如果我的问题太简单了,很抱歉。
发布于 2012-10-17 08:21:03
避免陷入局部最大值爬山的一种常见方法是使用随机重新启动。在您的示例中,如果G是一个局部最大值,则算法将在此处停止,然后选择另一个随机节点重新启动。因此,如果选择了J或C(也可能是A、B或D),您将在H或K中找到全局最大值,并重复足够多的次数,根据时间/资源限制和问题空间,您将找到全局最大值或更接近的值。
请注意,像爬山这样的局部搜索是不完整的,并且不能保证找到全局最大值。当然,好处是它只需要很少的资源。在实践中,并应用于正确的问题,这是一个非常有效的解决方案。
发布于 2015-03-09 01:13:35
您可以尝试使用一种名为simulated annealing的技术来防止搜索陷入局部最小值。本质上,在模拟退火中,有一个参数T
控制您移动到次优邻域状态的可能性。如果T
很高,你更有可能做出次优的移动到邻近的州,因此当你停留在那里时可能会逃脱局部最小值,如果你使用普通的爬山,你就不会。
发布于 2012-01-21 07:58:39
爬山不能保证不会陷入局部最小值/最大值。然而,只有最纯粹的爬山形式才不允许你倒退。
一个简单的爬山即兴小品,可以避免局部最小值问题(以更多的时间和内存为代价)是禁忌搜索,在这种搜索中,你可以记住以前的坏结果,并有目的地避免它们。
https://stackoverflow.com/questions/8946719
复制相似问题