1

例如,我有以下问题:

初始状态和目标状态

我可以申请的唯一运营商是:

  • 从结构向下放置最上面的块
  • 将不在结构中的块放置到结构的最上面位置

我有一个启发式函数:

  • h(n) = 如果正确放置块,则为每个支撑块 +1,如果放置不正确,则为每个支撑块 -1。

在此示例中,“A”块放置正确,因此 A 下面的每个支撑块得到 +3。“D”放置不正确,因此得到 -2。C放置正确,我得到另一个+1。因此,我的启发式函数现在返回值 3 + 1 - 2 = +2。

现在基于这里的算法,算法只有在达到它的目标状态时才会退出,并且如果它产生更好的启发式值,它只会选择下一个状态作为它的当前状态。但是,在我上面提出的情况下,不再可能继续进行。从结构中放下 A 将产生一个比前一个值 (+2) 更差的启发式值 -1。

为什么我要修改示例?我想展示当我们在简单爬山算法中遇到局部最大值问题时,这是一个局部最大值问题,对吧?另一个问题,正如算法所说,它只会在达到其目标状态时退出,它永远不会退出。或者我认为当其他邻国不再给出更好的结果时它也会退出是正确的吗?

4

1 回答 1

0

Hill Climbing 是一种局部搜索,可以保证找到凸问题的最佳解决方案。对于非凸问题,它可能会陷入(终止)局部最优。

爬山有一个“替代版本”,称为强制爬山 (EHC),它执行广度优先搜索,直到找到更有希望的状态来“逃避”局部最优。EHC 通常用于非最优(令人满意的)计划,因为只有在无法达到目标时才停止搜索。

于 2019-04-01T07:28:00.410 回答