#创作灵感#

人工智能导论课，要求用代码，实现八数码问题的求解。由于算法基础不扎实，除了课上老师的讲解，还去B站，搜集了相关资源，最后顺利完成课程实验。在这里做个分享，也是梳理一遍求解思路。

空格可以往四个方向移动，给定初始状态、目标状态，求两个状态的最短路径、最短路径的长度。无法到达，则输出-1。空格上的数字，用0表示。

用一维数组，表示一个盘面，需要进行上下左右移动时，转换为二维数组，操作完成后，再转换为一维数组。一维数组下标，与二维数组下标的关系：A[6] = A[6//3][6%3]，A[1][2] = A[1*3+2]。

每次空格只能往四个方向移动一格，移动后的状态数组，与之前的状态数组，只有两个元素不同。四个方向的移动，对二维坐标的影响：

用两个数组，来记录X、Y的改变量，方便快速计算空格的二维新坐标：

 另外，如果不加以管控，八数码问题的状态空间是图，因为可能会出现重复结点，并进入死循环，求无权图的最短路径更适合BFS，找到目标状态就可以退出循环：

为避免死循环，需要对新入队结点，进行排重，可以定义查找列表。如果当前结点，在查找表中没有出现过，插入查找列表并入队，如果已经出现过，则不入队。没有重复结点产生，八数码的状态空间就可以看成树。

A*是用结点的估价函数值，决定访问的优先次序。估价函数为：f(x) = p(x) +s(x)。p(x)代表前半段距离(从初始状态，到该节点的距离，即结点深度)。s(x)代表后半段距离(从当前节点，到目标状态的估计距离)。s(x)设计的是否合理，决定搜索效率，这里用3倍当前结点到目标状态的曼哈顿距离，作为后半段距离s(x)的估计值。(两个盘面的曼哈顿距离，等于0除外的每个元素的曼哈顿距离之和，每个元素的曼哈顿距离，等于两个盘面中，该元素的横坐标之差+纵坐标之差，具体可以看一下这个视频：A*算法的书面求解步骤）

为了方便求曼哈顿距离，可以对目标状态”打表“，把每个数字的坐标打成二维形式,比如目标状态为goal = "436708125",那么可以定义列表x，y,就可以快速查到目标状态中相应数字的X、Y坐标：

大致的求解思路：先计算初始状态、目标状态的逆序数，如果奇偶性不相同，那么无解，返回-1( 相关的理论证明，在这个链接里：深入理解逆序数+八数码原理)。奇偶性相同，那么计算初始状态的代价f，并入队，进入循环，循环条件：如果队列不空。循环体为：

取队首元素，判断是否为目标状态，如果是，返回队首结点与初始状态的距离(即结点深度）。否则，按照上、下、左、右，依次循环扩展该结点，并计算新结点的估价值f。如果移动合法，产生新节点入队。四个方向搜索结束，队首结点出队，根据剩余结点的估价值f，对队列中所有结点排序，最后进入下一循环。

一个结点st_state，包括两个数据项：估价值f、盘面state。估价值f为int类型，而盘面state的保存，用python字符串实现。最后用二元组，来存储这两个数据项。

所有的结点，用列表st来保存。当前结点与初始状态的距离，用列表dist存储。当前结点的父节点索引，用列表fu保存。最后从逻辑上看，应该是这样：

单个数据元素的结构：

数据元素间的关系(队列)：

入队出队操作：

从字符串的角度看，移动前后，其实就是置换两个字符的位置。其中一个字符是0，另一个字符，是某个相邻滑块。

如果找到两个字符的索引，交换位置是非常高效的。字符0的索引，通过for循环遍历得到。而相邻滑块的索引，可以通过字符0的索引，计算得到，方法如下：

先将0的索引，转换为二维坐标。如果state[z] = '0'，那么‘0’的二维坐标就是state[z//3][z%3]。

再根据上下左右移动，对坐标的影响，计算出空格的二维新坐标，例如state[X][Y]往i方向移动：

， 

此时将state[newX][newY]转换成一维坐标：

，

这样，就能够得知，与0交换位置的，相邻滑块的索引。从逻辑上看，应该是这样的：

先找到0的索引：

转换为二维坐标：

往i方向移动，以i=1(下移)为例，计算移动后的二维新坐标：

转换为一维坐标，就能够知道，索引为5、8指向的字符，交换位置,就是下移后的状态数组：