的深度depth，h(x)为当前节点每个数字位与目标节点数字位间距离和dist，进一步考虑当前结点与 目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距
离和（不考虑中 间路径），满足h ( n ) <= h * ( n )， 且对于目标节点有 h ( t ) = 0，对于结
点m和n （n 是m的子结点） 有h ( m ) – h ( n ) <= 1满足单调限制条件。 3）open和closed表的数据结构表示 对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点。closed表存储已扩展的结点间的扩展关系，主要用于输出路径。closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置，可以用数组实现。每个结点记录８数码格局和它的前驱结点的下标。 4）问题分析
首先，八数码问题包括一个初始状态(src) 和 目标状态(dest)，所谓解八数码 问题就是在两个状态间寻找一系列可过渡状态。这个状态是否存在就是我们要解决的第
一个问题。 解决八数码问题，主要面临的问题有： q1）开始状态s到目标状态d是否可解； q2）扩展节点的选择；
q3）扩展待扩展节点，该节点是否已扩展过； q4）判断是否已达目标节点d； 问题q 1）通过逆序数的奇数偶数来判断。因为在空白移动过程中，数码的逆序数不改变。左右移动，数码序列不变。上下移动，数码序列中某个数字则移动了两位。问题的实质就是：如果是n*n的数码盘的话，左右移动，数码序列不变；上下移动则数码序列变动n-1位。若n为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵，3为奇数，故逆序数不作改变。故可通过判断当前状态s的逆序数以及目标状态sd的数字序列的逆序数
的奇偶性是否相同来判断该问题是否可解。 问题q2）扩展节点的选择通过getmin函数，根据估价函数f来获得代价最小的节点。 问题q3）扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去，要判断是
否扩展过，只要跟之前的状态做比较即可。 问题q4）是否达到目标节点，将当前节点和目标节点进行比较。 算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程） 输入：初始状态，目标状态 输出：从初始状态到目标状态的一系列过程 算法描述：
begin： 读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； if(问题可解) 把初始状态假如open表中； while（未找到解
&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点； ②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点， 并计算新扩展结点的评价值f并记录其父节点； ④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中； ⑤把当前结点从open表中移除；
end while end if 输出结果； end
算法流程如下： 3 系统实现 （2）a*算法搜索开始，设置while循环，直到找到目标状态或者open表为空或者无解
的情况下结束。 （3）不同的八数码初始状态和目标状态不一定有解，所以要根据两种状态下的奇偶性是
否一致来判断（详见实验思想的问题分析）。 篇五：c语言解八数码问题之人工智能实验报告 人工智能》上机实验 《 基于人工智能的状态空间搜索策略研究 ——八数码问题求解 （一）实验软件
tc2.0 或 vc6.0 编程语言或其它编程语言 （二）实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、
求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉tc2.0 或 vc6.0 编程语言或者其它编程语言； 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法； 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤 1. 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操
作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（a 算法或 a* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 2. 实验步骤
（1）分析算法基本原理和基本流程； 程序采用宽度优先搜索算法，基本流程如下： （2）确定对问题描述的基本数据结构，如 open 表和 closed 表等； （3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调；
（6）撰写实验报告。 （五）实验报告要求 所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现； 3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出
参数意义和与其它模块联系等； 4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论；
7. 提供全部源程序及软件的可执行程序。