# 八数码实验报告
# 一、编程语言及环境
语言C++
环境:Visual Studio 2019
# 二、实验原理算法说明
## 2.1 问题说明:
八数码问题是指这样一种游戏:将分别标有数字 1,2,3,…,8 的八块正方形数码牌任意地放在一块 3 * 3 的数码盘上。放牌时要求不能重叠。于是,在 3*3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列。
## 2.2 问题分析:
八数码问题包括一个初始状态和目标状态,所谓解八数码问题就是在两个状态间寻找一系列可过渡状态。从一个状态出发,找到空位后有最多四种变换方式,一层一层创建树形结构。
这个状态可以有很多种表示方法。第一种是使用 int 表示,这种方法的好处是可以压缩空间,但是这仅使用于八数码问题,如果扩展到 15 数码将无法表示。第二种是使用一维数组,一维数组是较好的一种兼顾空间和时间的表示方法,但是在扩展 15 数码时需要重新对位置转换进行计算。第三种是使用多维数组表示,这种表示方法的好处是简单明了,易于扩充,且可以很方便地看出运行过程,弊端就是时间和空间上的消耗。在本次实验中我选择使用构造节点进行搜索,一个节点就是一个二维数组及其他属性,因此可以清晰地观测搜索顺序及运行结果。
其次要解决的问题是如何判断初始状态到目标状态是否是可达的。两个状态之间是否可达,可以通过计算两者的逆序值,若两者奇偶性相同则可达,不然两个状态不可达。从 3*3 棋盘上可知,移动方式分为上下左右四种,左右移动不会改变逆序数,而上下移动增加 2 或减少 2。因此,如果初始排列和目标排列逆序数奇偶性相同,就认为是有解的。除了使用逆序数判断还可以通过判断 Open 表是否为空来判断。如果状态是可达的,那么最终在 Open 表一定有一个与目标节点相同的节点,此为该题的解,若无解,运行结束后 Open 表为空。这里选择使用搜索前先进行判断即逆序数方法。
在搜索中还有一个需要解决的问题是避免重复搜索,否则有可能进入循环状态。每次得到的新节点与已经搜索过的节点做比较,如果均不相同就说明是可行的,否则就是重复的。
## 2.3 准备工作:
1. 用逆序数同奇偶判断是否有解。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/16635946e9178cc94c3a9d32f6b0c4f3.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/aed22924f5471c9abfcca2a5e09e4e53.writebug)
2. 判断是否为重复搜索节点。使用 is_expandable()和 is_equal()两个函数达到目的。所有搜索过的节点均存储在容器 node_v 中,依次与容器中的节点比较,如果均不相同说明可扩展。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/cf402ff7278b9f74fccdd8f87a198b2e.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/a46c2379b74cfb291d9549d585ac34fe.writebug)
3. 为了较好的输出格式,重写<<。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/26136997e7f4180505e723a38301e3d7.writebug)
4. 回溯法输出路径。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/8dcaddf08c316e186548c251c06c461a.writebug)
## 2.4 核心算法:
### 广度优先搜索(BFS)
广度搜索是以接近起始节点的程度一次扩展节点,逐层搜索,在对下一层节点搜索前必须搜索完本层的所有节点。
广度搜索在八数码问题中的应用如下:将新节点放入 Open 表,然后寻找当前节点的空位,并进行上下左右移动,得到的新节点放入 Open 表,将当前节点放入 Close 表。
首次定义为节点定义一个结构体,其中 index 是父节点在 vector 中的下标。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/920cad56452e2fe63d835ef349b876a8.writebug)
Open 表使用 vector 动态数组实现,若扩展得到的新节点和目标节点相同,就返回当前该节点在 vector 中的下标,即最后一个位置;若和目标节点不同,返回 -1。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/bedae569f295fc91a6b8ae7ac0d8d9a0.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/7d91a42181d28f1414b1e594a9b9b2ca.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/38436c4ff2e81468729246ac90a078d7.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/3ca704979f7bbc723e26ef6744dfd66e.writebug)
### 深度优先搜索(DFS)
深度搜索是扩展最深的节点,这使得搜索沿着状态空间的某条单一路径从起始节点向下进行,只有当搜索到叶节点的状态时才考虑另外一条路径。为了避免考虑太长的路径,防止搜索过程沿着无益的路径扩展下去,往往给出一个扩展的最大深度界限。任何节点如果达到了深度界限都将作为没有后继节点处理。
深度搜索在八数码问题上的应用如下:考察当前节点是否为目标节点,若不是目标节点则将新节点放入 Open 表前端,这里可以使用栈来辅助运行;若是得到的节点与目标节点相同,使用回溯法打印查询路径。
为一个节点定义一个结构体,self 为当前节点在 vector 中的位置,设置 bool 变量维护搜索状态,初始均未被搜索。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/ce53082cc83c93c945e8acca8a915680.writebug)
设置深度限度为 7(根节点深度为 0)。未到达深度限度且栈顶元素未被搜索过,将栈顶元素作为当前节点进行搜索,该节点的空位向上下左右四个方向移动后,将可扩展节点依次放入栈和容器中,如果与目标节点相同,返回该节点在容器中的位置,回溯打印路径;否则返回-1。已到达最大深度或栈顶元素已被搜索过,直接弹出,考虑新的栈顶元素。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/77d1f1eef5b9a0ba7c1096883e35e7fe.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/92e2aa29353ca759efcb7a71bb1135a3.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/897f50cc72179ba4177aa12ce415e82b.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/7/12/905bb45ac74aa241be4503c7b5d58535.writebug)
### 启发式搜索(A*)
启发式搜索是在路径搜索问题中很使用的搜索方式,通过设计一个好的启发式函数来计算状态的优先级,优先考虑优先级高的状态,可以提早搜索到达目标态的时间。
A*算法的核心是启发式函数 f=g+h,g 是初始节点到节点 n 的一条最佳路径的实际代价,可以用节点所在层数来表示;h 是节点 n 与目标节点的预测距离,可以使用曼哈顿距离计算,每移动一步相当于移动一个数字,如果每次移动都是完美的,那么从初始态到目标态的距离就是曼哈顿距离,也是最少要走的步数。Open 表使用 vector 动态数组,Close 表通过将 h 标记为MAXNUM 达到已搜索过的效果。
首先为一个节点定义一个结构体,src 为初始状态节点,dest 为最终状态节点。
![](https://www.writebug.com/myres/static/uploads/2022/7/12/d2756e60e4f28d37e796e01f5fe821c0.writebug)
获取 Open 表中估价值最小的节点并将其作为可扩充节点继续向下搜索子节点,每次搜索需要计算估价值。Distance 用于计算 h(n),g(n)深度递增 1。直到得到目标节点,按照父节点标记向上回溯打印变换过程。
将节点放入 Open 表的过程分别是先查找空位,向上、下、左、右移动判断�