局部最大值问题会导致简单爬山算法陷入无限循环吗？

Question

例如，我有以下问题：

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

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

我有一个启发式功能：

• 如果块正确放置，则每个支撑块的h（n）= +1;如果块放置不正确，则为每个支撑块的-1。

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

现在基于算法here，算法将仅在达到其目标状态时退出，并且如果它产生更好的启发式值，它将仅选择下一个状态作为其当前状态。但是，我不再可能继续上述情况。从结构中放下A将产生-1的启发值，这比前一个值（+2）更差。

为什么我要修改这个例子？我想在Simple Hill Climbing算法中遇到局部最大值问题时显示，这是一个局部最大值问题，对吗？另一个问题，因为算法说它只会在达到目标状态时退出[它]，它永远不会退出。或者我认为当其他邻国不再给出更好的结果时它也会退出，这是正确的吗？

Answer 1

Hill Climbing是一个本地搜索，保证找到凸问题的最佳解决方案。对于非凸问题，它可能会陷入（终止）局部最优。

有一个名为Enforced Hill Climbing (EHC)的Hill Climbing的“替代版本”，它执行广度优先搜索，直到一个更有希望的状态被发现“逃脱”当地的最佳状态。 EHC通常用于非最佳（满意）计划，因为只有在无法达到目标时才会停止搜索。