八数码难题——AI算法求解_8puzzle bfs dfs

实验内容：

1. 利用至少一种无信息搜索算法实现八数码难题求解（可选多种）；
2. 设计至少两种启发式信息函数，利用A*搜索实现八数码难题求解，并对比分析搜索效果；

代码地址

1.代码整体框架

八数码问题的解决关键在于状态表示，状态转移，对状态的遍历搜索。在我的第一个文件eight_puzzle_problem.py中解决了这三个问题，其中搜索算法采用了BFS、DFS和两种不同启发式函数的A*。在该文件中我定义了两个类，Node类和EightPuzzleProblem类，第一个类用于相关状态的表示，第二个类用于节点状态的转移和搜索。为了直观地呈现出搜索的过程，我使用Python的PyQt5模块设计出了一个UI界面，运行第二个eppUI.py文件可以通过九宫格拼图（图片为网上找的深圳大学校徽）的形式展现出原有问题的解决路径。

2.状态空间的表示

我设计了一个Node类来表示一个节点的状态。Node的数据成员有state（列表形式，用数字0-8存放当前节点各图片的标号，从而记录其与九宫格的映射关系如图1所示）

图1 深大校徽九宫格图片

parent（记录该节点的父亲节点，方便后续回溯记录完整的移动步骤），depth（当前节点距离开始节点的深度），gCost（用于UCS、A对open表的维护），hCost（可用于A、A对open表的维护）。具体代码如图2所示：

图2 状态空间表示代码

3.状态的转移

状态转移代码如图3所示。EightPuzzleProblem类中的generate_substates函数实现了搜素当前节点可以到达的子节点并返回这些子节点组成的列表。我们可以将0位置（即空格图片的位置）与其可移动到的九宫格坐标一一映射做成一个字典（即代码中的变量sub_state_list），然后根据映射关系将当前状态可以达到的子状态加入到列表（即代码中的变量substates），最后返回。

图3 状态转移代码

4.判断问题可解性

按照八数码问题的游戏规则，在游戏过程中，棋局的棋子数列的逆序数的奇偶性不会发生变化。而最终的目标状态没有逆序存在，所以目标状态下棋局的逆序数为偶数（实际为0）。所以，对于任意一个初始状态，若其棋局的棋子数列的逆序数为奇数，则永远也不可能达到目标状态，即八数码问题无解；若其棋局的棋子数列的逆序数为偶数，则八数码问题有解。具体代码如图4所示。证明过程：https://blog.csdn.net/wonengxing/article/details/6869219

图4 判断问题可解性代码

5.BFS（宽度优先遍历搜索）

BFS算法代码如图5所示。首先若判断问题是否有解，若有解，则将当前节点的状态设为起始节点的状态，并将其放入open表中（由queue模块中的队列实现），再创建一个close表防止重复遍历（由set容器实现，原因后续介绍）。实现BFS的步骤即为不断对当前状态扩展，同时将生成的子状态入队open表（若子状态到达终状态则回溯收集状态到path_list内并返回退出搜索，若子节点在close表中则表示已访问过，无需放入open表）。同时不停将open表出队的元素设为当前节点，直到open表为空。

图5 BFS算法代码

6.DFS（深度优先遍历搜索）

DFS算法代码如图6所示。DFS索与BFS思想类似，只不过open表中的维护使用栈实现，再创建一个close表防止重复遍历（由set容器实现）。需要注意的是，为了防止在一条路径一直搜索的情况出现，我设置了一个搜索的最大深度的阈值（max_depth），超过这个阈值则放弃这条路径的搜索。然而这个阈值的设定很有技巧性，这直接关系到DFS的搜索效率与搜索结果。

图6 DFS算法代码

7.UCS（等代价一致算法）

由于节点的gCost为深度，所以UCS在此退化成BFS，因此并未编写相关代码。

8.贪婪算法

贪婪算法为A算法的弱化版，即只考虑hCost，不考虑gCost。由于贪婪算法只需要在A算法计算代价时稍作改动，在此也不赘述，下面直接介绍A*算法。

9.A*搜索

A*算法代码如下图7所示：

图7 A*算法代码
A*搜索的重点在于启发式信息函数的设计，我采用了欧式距离和曼哈顿距离两种方法来获得启发式信息函数。具体如下：

a)欧式距离版
计算欧式距离代码如图8所示，即计算除0以外当前节点的数距对应数的直线距离并求和，作为当前节点的hCost值，gCost则为当前节点深度。

图8 计算欧式距离代码

b)曼哈顿距离版
计算曼哈顿距离代码如图9所所示，即计算除0以外当前节点的数距对应数的坐标绝对值距离并求和，作为当前节点的hCost值，gCost则为当前节点深度。

图9 计算曼哈顿距离代码

A* 与无信息搜索算法本质区别在于对open表的维护不同，它利用一些信息和推理判断快速获得最优解，主要依赖于启发式代价评估函数，这里表现为在open表中节点状态的gCost+hCost按从小到大排序（通过重写节点__lt__()方法并使用优先级队列实现）。所以A*算法剩余部分情况与无信息搜索算法相似，在此不做赘述。