Simple Hill Climbing 算法中的问题示例

Example of problems in Simple Hill Climbing algorithm

导致简单爬山达到局部最大值、山脊和小巷以及高原问题等问题的例子有哪些?我试过搜索:

从我读的讲义中,我得到了TSP问题。该图是一个完整的图,有四个节点:A、B、C 和 D。我们使用简单爬山法和最速爬山法来解决这个问题。用于解决该问题的启发值是每个状态的总距离。我们可以通过使用 6 种不同的组合(第一个字母 <-> 第二个,第二个 <-> 第三个,等等)切换字符 "ABCD" 的位置来探索其他相邻状态。但是,在给出的示例中,它没有显示 "stuck at a local maximum" 到底是什么。既没有体现岭南问题,也没有体现高原问题。

谁能给我一个例子,说明我们是如何解决这些问题的,以及这些问题在示例中到底是什么(我理解每个问题的定义:here and here)?作为参考,下面是我提到的 TSP 问题的图像:

当您的简单爬山行走 Ridge 寻找上升点时,效率会很低,因为它会沿着 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),...) 图像通过函数。该算法选择那些点,但只选择那些直接相邻的点(因为它沿着轴移动)。 This 是它将采取的路径。 (原谅我拙劣的画功)

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

对于高原问题,如果你到达一个平面或者几乎是平面,算法将无法找到更好的位置。

希望我理解你的问题。