基于启发式搜索算法A星解决八数码问题

《基于启发式搜索算法A星解决八数码问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能实验报告基于启发式搜索算法A*问题求解方法实验姓名：王鑫学号：12349021日期：2016.1.3摘要本篇报告的所介绍的内容是使用A*算法解决八数码问题。包括介绍A*算法的流程，如何使用A*算法来解决八数码问题，本文依照A*算法的流程，详细的介绍了A*算法的每一步的实现方法。最后输入数据对A*算法的性能作出评估，通过与BFS算法的对比，总结了A*算法的优势体现在哪里，并且反思了A*算法存在的不足。1导言本次试验我准备使用A*算法解决八数码问题。八数码问题也称为九宫问题，是在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。

2、棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。八数码问题一般使用搜索法来解。广度优先搜索是解决八数码问题常用的一种方法，但是使用广度优先搜索有很大的缺陷，虽然广度优先搜索法在有解的情形总能保证搜索到最短路经，也就是移动最少步数的路径，但广度优先搜索法的最大问题在于搜索的结点数量太多。因为在广度优先搜索法中，

3、每一个可能扩展出的结点都是搜索的对象。随着结点在搜索树上的深度增大，搜索的结点数会很快增长，并以指数形式扩张，从而所需的存储空间和搜索花费的时间也会成倍增长。所以本次实验我选用A*算法来解决八数码问题，A*算法是一种启发式的搜索算法，与1属于盲搜索算法的广度优先算法不同的是，A*算法从open表中选取的是启发式函数值最优的节点来生成后继节点。所以A*算法可以大大减少搜索无关节点的数目，从而提高搜索效率。2实验过程2.1A*算法的流程（1）定义两个表，一个是open表，用来存放已经生成，并且已用启发式函数做过估计或评价，但尚未产生他们的后继节点的那些节点。另一个是clo

4、se表，用来存放，已经生成，并且已经用启发式函数做过估计且已经产生后继节点的那些节点。（2）初始化两张表，将所有初始状态存放进open表中，将close表清空。（3）如果open表为空，失败退出（4）在open表中取出启发式函数??(??)值最小的节点n，把n放入close表中。（5）如果n∈????(目标状态)，则成功退出，此时解为Tree上从n到??0(初始状态)的路径。（6）产生n的一切后继，将后继中不是n的前驱点的一切点构成集合M，将装入G作为n的后继，这就除掉了既是n的前驱又是n的后继的节点，就避免了回路，节点之间有偏序关系存在。（7）对M中的任意一个元素P

5、，分别作两类处理：a.若P∉G，即P不在open表中，也不在close表中，则P根据一定原则加入到open表中，同时加入搜索图G中，对P进行估计放入Tree中。b.若P∈G，则决定是否更改Tree中P到n的指针。（8）转第（3）步。2.2A*算法解决八数码问题的步骤2.2.1定义节点类型在A*算法中我们会用到一张open表，一张close表，一棵搜索树，以及以个搜索图。这些数据结构中都是由节点彼此链接构成的。所以我们定义如下的节点结类型：2其包含一个二维数组statue来记录当前节点的状态；包含多个指针，这些指针的作用是把同一个节点链接在不同的数据结构中。例如，指针T

6、parent的作用是把该节点链接到搜索树中。在该节点被接入搜索树中时对Tparent赋值，使得Tparent指向该节点在树中的前驱节点，如果该节点尚未被接入搜索树，则Tparent的值为空。同理，如果该节点在open表中，则opennext指向该节点在open表中的下一个节点。其余指针类似也是类似的道理。//定义算法中用到的链表，图，树的节点的结构。structNode{intstatue[size][size];//记录当前节点的状态structNode*Tparent;//用来构成搜索树，该树由搜索图的反向指针构成structNode*opennext;//用来构

7、成open表，该指针指向该节点在open表中的下一个节点structNode*closenext;//用来构成open表，该指针指向该节点在close表中的下一个节点structNode*brothernext;//构成兄弟链表，该指针指向该节点在兄弟链表中的下一个节点intf;//记录当前节点的f函数值intg;//记录当前节点的g函数的值inth;//记录当前节点的h函数的值};定义表头类型，用来定义表头变量。例如，定义一个变量head_o来作为open表的表头，指向open表的第一个节点。//定义表头结构structhead{structNod