Simple Hill Climbing 算法中的问题示例
Example of problems in Simple Hill Climbing algorithm
导致简单爬山达到局部最大值、山脊和小巷以及高原问题等问题的例子有哪些?我试过搜索:
- Link one:这给出了块排列中简单爬山陷入局部最大值问题的一个很好的例子。但是,它没有显示步骤。
- Link two:它给出了在 SHC 中找到解决方案的步骤。但是,我不明白当只有四个块并且其中四个放错了位置时,h(1) 怎么会是 -6,因此只能产生 -4。它也没有显示 SHC 遇到的问题。
- Link three:我理解达到状态 'g' 的概念如何使您的算法达到局部最大值并卡住。但是,状态是什么相当模糊,我不知道状态 'g' 和最终状态指的是什么。
从我读的讲义中,我得到了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 下面没有方块所以不添加任何东西)
对于高原问题,如果你到达一个平面或者几乎是平面,算法将无法找到更好的位置。
希望我理解你的问题。
导致简单爬山达到局部最大值、山脊和小巷以及高原问题等问题的例子有哪些?我试过搜索:
- Link one:这给出了块排列中简单爬山陷入局部最大值问题的一个很好的例子。但是,它没有显示步骤。
- Link two:它给出了在 SHC 中找到解决方案的步骤。但是,我不明白当只有四个块并且其中四个放错了位置时,h(1) 怎么会是 -6,因此只能产生 -4。它也没有显示 SHC 遇到的问题。
- Link three:我理解达到状态 'g' 的概念如何使您的算法达到局部最大值并卡住。但是,状态是什么相当模糊,我不知道状态 'g' 和最终状态指的是什么。
从我读的讲义中,我得到了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 下面没有方块所以不添加任何东西)
对于高原问题,如果你到达一个平面或者几乎是平面,算法将无法找到更好的位置。
希望我理解你的问题。