【爬山法、随机重启爬山法——八皇后问题、八数码问题】_8皇后问题爬山法

系列文章目录

前情回顾
搜索算法——爬山算法

---

---

前言

提示：这里可以添加本文要记录的大概内容：

前文介绍了搜索算法中的爬山算法，这篇文章我们来看一下爬山法的具体应用——八皇后问题和八数码问题

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、八皇后问题

问题描述

有一个8*8的棋盘，现在要将八个皇后放到棋盘上，要求满足：对于每一个皇后，在自己所在的行、列、两个对角线都没有其他皇后

求解——爬山法

搜索算法结题的过程，就是将问题转化为状态空间图，然后通过特定的遍历算法求出符合要求的解。关键在于状态的构造。
对于八皇后问题，我们将状态设置为皇后之间的碰撞度N。如果两个皇后之间不满足上面的规则，我们就说这一对皇后是冲突的。碰撞度N就是冲突的皇后对数。

图中为初始状态的摆放位置，一共有17对冲突的皇后，N=17
在达到合理的安放顺序之前，我们可以移动皇后，从而使得状态变化。容易得知，当N=0时的摆放方式，就是符合规则的解。所以我们追求的状态就是N越小越好，当N=0时就是状态最优解。
由于所有皇后都是一样的，而且每一列刚好一个皇后，我们不妨做个规定：皇后只能在当前列上下移动
有了这个规定，问题就稍微简单些了，接着便是搜索算法的应用：
我们列举每一个皇后移动后N的值：

按照爬山法的贪心策略，我们选取使得N为最小的选择，因为这样看起来有利于通往最优解。图中做出一步选择后最小是12，所以在众多12中随机选取一个，这里选的是第5列的皇后移动到第2行（还是第5列）。做出选择后，我们更新下一次选择引起的N的变化。

此时N最小是7，随机选取7中一个。这里选取了第二列皇后移动到第2行（还是第二列），更新。

此时N最小是4，随机选取4中一个。这里选取了第七列皇后移动到第1行（还是第七列），更新。

此时N最小是3，随机选取3中一个。这里选取了第6列皇后移动到第5行（还是第6列），更新。

此时N最小是1，只有一个1。选取第1列皇后移动到第8行（还是第1列），更新。

此时怎么移动皇后，得到的N都将大于现值1，我们无路可走了，及时止损，直接返回，得到的是局部优解。
这种情况体现了爬山法的局限性——容易陷入局部优解。因此，我们需要改进爬山法。

随机重启爬山法

首先要明确一点，爬山法不是不能得到最优解，只是爬山法有时候会陷入局部优解的泥潭。所以，当我们陷入泥潭的时候，不妨重开一把。通过重新设置初始状态再次尝试，我们可以在这种方式中找到最优解。换言之，就是走入一片没有沼泽的森林。

二、八数码问题

问题描述

3*3九宫棋盘，放置8个棋牌，只能通过棋牌向空格的移动来改变布局。根据给定的初始布局和目标布局，能够找到合法的移动序列？

爬山法求解

我们将状态设置为处于错误位置上的方块个数D，当D=0时，就是最优解。我们贪心选择使得D最小的，直到没有更小的D（陷入局部优解）或者D=0（最优解）

D最小可以为3。随机选择一个，这里选择左边的3，移动空格后更新。

此时D最小为2，移动空格，更新

此时D最小为1，移动空格，更新

此时存在选择使得D=0，选择它，得到最优解，返回。

随机重启算法不适用性

这里的初始状态是给定的，不能自定义初始状态，因此不能直接使用随机重启算法

---

总结

以上是关于爬山法求解八皇后和八数码问题的过程。那么在求解八数码问题的过程中，假如遇到了爬山法陷入局部优解的情况，此时不能使用随机重启爬山法，爬山法也不能回头，那么该如何解决呢？我们下次为你详细带来Best-First算法（最佳优先算法），敬请期待。