0

有哪些示例导致简单爬山遇到局部最大值、山脊和小巷以及高原问题等问题？我试过搜索：

  • 链接一：它给出了一个很好的例子，即简单爬山在块布置中陷入局部最大值问题。但是，它没有显示步骤。
  • 链接二：它提供了在 SHC 中找到解决方案的步骤。但是，我不明白当只有四个块并且其中四个块放错位置时，h(1) 怎么可能是-6，因此只产生-4。它也没有显示 SHC 遇到的问题。
  • 链接三：我了解达到状态“g”的概念如何使您的算法达到局部最大值并卡住。但是，状态是什么是相当模棱两可的，我不知道状态“g”和最终状态指的是什么。

从我阅读的讲义中，我得到了 TSP 问题。该图是具有四个节点的完整图：A、B、C 和 D。我们同时使用了 Simple Hill Climbing 和 Steepest-Ascent Hill Climbing 来解决问题。用于解决该问题的启发式值是每个状态的总距离。我们可以通过使用 6 种不同的组合（第一个字母 <-> 第二个、第二个 <-> 第三个等）切换字符“ABCD”的位置来探索其他相邻状态。但是，在给出的示例中，它并没有显示“陷入局部最大值”究竟是什么。它既没有显示山脊和小巷问题，也没有显示高原问题。

有人可以给我一个例子，说明我们如何解决这些问题以及这些问题在示例中实际上是什么（我理解每个问题的定义：here和here）？作为参考，下面是我提到的 TSP 问题的图像： TSP 地图

4

1 回答 1

1

当你简单的爬山走这个山脊寻找上升时，它会是低效的，因为它会沿着 x 或 y 方向行走，即沿着这张图片中的线走。它导致锯齿形运动。

为了达到这个状态，给定一个随机的起始位置，算法评估 4 个位置 (x+1,y) (x-1,y) (x, y+1) (x, y-1)（对于1）和图片最高。所以它将开始向山脊移动。

让我们用上一张图片来说明这种行为。给定从原点 (0,0) 开始，步长为 1。与表面相交的细暗线是单位点 ((0,1),(0,2),...,(1, 0),...) 图像通过函数。该算法在这些点中进行选择，但仅在那些直接相邻的点中进行选择（因为它沿轴移动）。这是它将采取的道路。（原谅我糟糕的绘画技巧）。

在链接 2 中，为了计算启发式函数，您评估每个块，如果该块放错位置（也就是不在堆上的正确索引处），它下面的每个块都加 -1，否则，它下面的每个块都加 +1。h(1) = -3 -2 -1（A 放错了位置，它下面有 3 个方块，所以 -3，B 也一样，但有 2 个方块，所以 -2，C -1 和 D 在它下面没有方块，所以不加任何事物）

对于高原问题，如果到达平坦或几乎平坦的表面，算法将无法找到更好的位置。

我希望我理解你的问题。

于 2019-03-28T13:06:10.807 回答