资源下载地址：https://download.csdn.net/download/sheziqiong/85883976
资源下载地址：https://download.csdn.net/download/sheziqiong/85883976
在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有4个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。
例如：
初始状态 目标状态
八数码问题示意图
形式化定义● 状态：状态指定了8个棋子中的每一个以及空位在棋盘的9个方格上的分步。
● 初始状态：任何状态都可以被指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为开始。
● 后继函数：用来产生通过四个行动（把空位向Left，Right，Up或Down移动）能够达到的合法状态。
● 目标测试：用来检测状态是否能匹配到目标布局。
● 路径耗散：每一个耗散值为1，因此整个路径的耗散值是路径中的步数。
实验目的和环境 实验目的熟悉人工智能系统中的问题求解过程；
熟悉状态空间的启发式搜索算法的应用；
熟悉对八数码问题的建模、求解及编程语言的应用。
实验环境硬件环境：
-
计算机型号：惠普Pavilion M4
-
内存：4.00GB
-
CPU：Intel Core i5 2.6GHz
软件环境：
-
操作系统：Windows10版本
-
IDE：Dev-C++ 5.10版
-
实现语言：C++（C++11标准）
A*算法是一种常用的启发式搜索算法。
在A * 算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n) f'(n)是估价函数； g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价）； h'(n)是n到目标的最短路经的启发值；
由于f’(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：
f(n) = g(n) + h(n)
g(n)是从初始结点到节点n的实际代价；
h(n)是从结点n到目标结点的最佳路径的估计代价；
在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f’(n)的近似，也就是用g(n)代替g’(n)，h(n)代替h’(n)。这样必须满足两个条件：
（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且 f 必须保持单调递增。 （2）h 必须小于等于实际的从当前节点到达目标节点的最小耗费 h(n)<=h'(n)。
必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h’(n)。
第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。
本次实验相应的具体估价函数、代价函数、启发值函数：
g(n)：本次试验中该状态的耗费值自然是从初始状态到达该状态的最少步数；
h(n)：启发值可以选用不再目标状态的数码个数，也可以选用曼哈顿距离（及当前状态中每个数码到达相应位置所需最少步数），但是曼哈顿距离更适合，所以选用曼哈顿距离作为启发值。
0 1 2 1 2 3 2 3 4 1 0 1 2 1 2 3 2 3 2 1 0 1 2 1 2 3 2 1 2 1 0 1 2 1 2 3 2 1 2 1 0 1 2 1 2 3 2 1 2 1 0 1 2 1 2 3 2 1 2 1 0 1 2 3 2 3 2 1 2 1 0 1 4 3 2 3 2 1 2 1 0
上述矩阵第i行第j列表示数字i-1在八数码中第j位置的曼哈顿距离。
算法伪代码算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）
输入：初始状态，目标状态
输出：从初始状态到目标状态的一系列过程
算法描述：
Begin：
根据八数码奇偶排列的性质，判断初始状态是否可解；
If(问题可解)
计算初始状态评价函数值f，g，h；
将初始状态加入优先队列Q，该节点的父节点为空；
While（优先队列非空）
①将优先队列Q中评价值最小的节点qn作为当前结点并出队；
②如果qn节点状态已经扩展过，跳转到①；
③判断当前结点状态和目标状态是否一致，若一致，跳出循环；
④对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，计算新扩展结点的评价值f，g，h，记录其父节点为该节点，将新扩展节点加入Q；
End while
End if
从目标状态依次寻找父节点直到初始状态，输出结果；
End
注：
算法中所用的优先队列是一种数据结构（堆结构）。按照A*算法需要每次对队列中的待扩展节点进行排序，如果有n个节点，则每次排序最快时间复杂度为O(nlogn)，这样效率较低。事实上，我们只需每次得到待扩展队列中fn值最小元素，小顶堆式的优先队列的顶端是fn最小的节点，每次插入或提取优先队列中的一个节点的时间复杂度为O(logn)，效率得到提升。
算法流程图 实现优化
初始状态 目标状态
在具体记录每个状态时，我们可以用一维数组或者二维数组记录相应位置的数字，但是这样效率不高，我们可以用一个32位整型数来表示每一个状态。因为数字只有8个，可以用3个bit完全表示，最高位的32-3*9=5个bit来记录空格位置。这样算法的效率可以提升一个数量级。
初始状态用int数来表示时具体描述：
如上：
初始状态为：0x205E88CE（0010 0000 0101 1110 1000 1000 1100 1110）
目标状态为：0x07D63440（0000 0111 1101 0110 0011 0100 0100 0000）
结果验证用逆向广度优先搜索可以知道，八数码最多解的步数不会超过31步，选取最多步数的解来进行验证，如下截图：
求解记录：
效果展示：
文件中求解过程：
解的步数为：31
无解验证：
当输入为非法输入或者不能到达目标状态时不会有解：
资源下载地址：https://download.csdn.net/download/sheziqiong/85883976
资源下载地址：https://download.csdn.net/download/sheziqiong/85883976
