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

人工智能实验报告基于启发式搜索算法A*问题求解方法实验姓名：王鑫学号：12349021日期：2016.1.3摘要本篇报告的所介绍的内容是使用A*算法解决八数码问题。包括介绍A*算法的流程，如何使用A*算法来解决八数码问题，本文依照A*算法的流程，详细的介绍了A*算法的每一步的实现方法。最后输入数据对A*算法的性能作出评估，通过与BFS算法的对比，总结了A*算法的优势体现在哪里，并且反思了A*算法存在的不足。1导言本次试验我准备使用A*算法解决八数码问题。八数码问题也称为九宫问题，是在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。八数码问题一般使用搜索法来解。广度优先搜索是解决八数码问题常用的一种方法，但是使用广度优先搜索有很大的缺陷，虽然广度优先搜索法在有解的情形总能保证搜索到最短路经，也就是移动最少步数的路径，但广度优先搜索法的最大问题在于搜索的结点数量太多。因为在广度优先搜索法中，每一个可能扩展出的结点都是搜索的对象。随着结点在搜索树上的深度增大，搜索的结点数会很快增长，并以指数形式扩张，从而所需的存储空间和搜索花费的时间也会成倍增长。所以本次实验我选用A*算法来解决八数码问题，A*算法是一种启发式的搜索算法，与1属于盲搜索算法的广度优先算法不同的是，A*算法从open表中选取的是启发式函数值最优的节点来生成后继节点。所以A*算法可以大大减少搜索无关节点的数目，从而提高搜索效率。2实验过程2.1A*算法的流程（1）定义两个表，一个是open表，用来存放已经生成，并且已用启发式函数做过估计或评价，但尚未产生他们的后继节点的那些节点。另一个是close表，用来存放，已经生成，并且已经用启发式函数做过估计且已经产生后继节点的那些节点。（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，分别作两类处理：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来记录当前节点的状态；包含多个指针，这些指针的作用是把同一个节点链接在不同的数据结构中。例如，指针Tparent的作用是把该节点链接到搜索树中。在该节点被接入搜索树中时对Tparent赋值，使得Tparent指向该节点在树中的前驱节点，如果该节点尚未被接入搜索树，则Tparent的值为空。同理，如果该节点在open表中，则opennext指向该节点在open表中的下一个节点。其余指针类似也是类似的道理。//定义算法中用到的链表，图，树的节点的结构。structNode{intstatue[size][size];//记录当前节点的状态structNode*Tparent;//用来构成搜索树，该树由搜索图的反向指针构成structNode*opennext;//用来构成open表，该指针指向该节点在open表中的下一个节点structNode*closenext;//用来构成open表，该指针指向该节点在close表中的下一个节点structNode*brothernext;//构成兄弟链表，该指针指向该节点在兄弟链表中的下一个节点intf;//记录当前节点的f函数值intg;//记录当前节点的g函数的值inth;//记录当前节点的h函数的值};定义表头类型，用来定义表头变量。例如，定义一个变量head_o来作为open表的表头，指向open表的第一个节点。//定义表头结构structhead{structNode*next;};32.2.2定义启发式函数试验中选择的启发式函数是：𝑓𝑓(𝑛𝑛)=𝑑𝑑(𝑛𝑛)+ℎ(𝑛𝑛)其中𝑑𝑑(𝑛𝑛)表示节点n到搜索树根节点的距离。ℎ(𝑛𝑛)是估计的放错位置的数字的个数。可以看出ℎ(𝑛𝑛)的值必定小于等于实际的从当前节点到达目标节点的最小耗费//得到当前节点的f值voidget_f(Node*n){intfvalue;//计算h(n);inthvalue=0;for(inti=0;isize;++i){for(intj=0;jsize;++j){if(n-statue[i][j]!=statueg[i][j]){hvalue++;}}}n-h=hvalue;n-f=hvalue+n-g;}2.2.3定义两张表和搜索树并初始化如下所示，我们直接定义head类型的三个变量，head_o作为open表的表头；head_c作为close表的表头；Troot的next属性指向搜索树的根。headhead_o;headhead_c;headTroot;初始化open表，将初始状态S0接入open表中；初始化close表为空；初始化搜索树，将S0作为搜索树的根节点。//初始化两张表,和树head_o.next=S0;4head_c.next=NULL;Troot.next=S0;2.2.4判断open表是否为空如果open表为空，则搜索失败，退出。if(head_o.next==NULL){cout查找失败！endl;return;}2.2.5在open表中取出最优节点我们定义一个指针bestNode。利用get_bestNode函数，让bestNode指向open表中启发式函数值最优的节点。并将该节点的opennext属性置空，即从open表中移除该节点。将该节点利用move_to_close函数添加进close表中。Node*bestNode;//定义f值最小的节点bestNode=get_bestNode(&head_o);//选择f值最小的节点bestNode，并从open表中移除该节点move_to_close(&head_c,bestNode);//将bestNode添加进close表中。2.2.6判断bestNode所指节点是不是属于目标状态使用ifequal函数判断bestNode是不是属于目标状态。如果属于，就成功找到目标状态，利用get_bestroute函数输出最佳路径并退出。if(boolequal=ifequal(bestNode,Sg)){cout找到目标状态！endl;cout请按任意键，输出最佳路径...endl;system(pause);5get_bestroute(bestNode);return;}2.2.7生成bestNode所指节点的后继节点定义一个后继节点链表，表头为head_b，将bestNode所指节点的不是前驱节点的后继节点，链接到后继及诶单链表中。getchild函数可以实现这个功能。//产生bestNode的一切后继节点。。headhead_b;//定义bestNode的后继节点表head_b.next=NULL;getchild(&head_b,bestNode);//产生bestNode的子节点，将不是bestNode的父节点的子节点放入后继节点表中2.2.8对后继节点链表中的节点分类处理利用getbrother函数从后继节点链表中取得一个节点，并将该节点从后继节点中移除。对该节点依照条件，作下面的处理：利用atopen函数判断该节点是否在open表中，如果在，则比较该节点与open表中状态相同的节点到搜索树根的距离，即g(𝑥𝑥)的值，如果前者小于后者，则更新搜索树，并用前者替换掉后者。利用atclose函数判断该节点时候在close表中，如果在，则比较该节点与close表中状态相同的节点到搜索树根的距离，即g(𝑥𝑥)的值，如果前者小于后者，则更新搜索树，以及用前者替换掉后者。如果上面的两种条件都不满足，即该节点之前在搜索图中没有出现过，则将该节点连接到搜索树中，并用move_to_open函数将该节点连接到open表尾部。while(head_b.next!=NULL){Node*tmp=getbrother(&head_b);//从后继节点表中取出一个节点记为tmp，并从6后继节点表中删除该节点Node*atposion;//如果在open表中或在close表中，则返回true，并将atposion指向该节点if(boolat1=atopen(&head_o,tmp,&atposion)){if(atposion-gtmp-g){atposion-Tparent=tmp-Tparent;atposion-f=tmp-f;atposion-g=tmp-g;atposion-h=tmp-h;}}elseif(boolat2=atclose(&head_c,tmp,&atposion)){if((atposion-g)(tmp-g)){atposion-Tparent=tmp-Tparent;atposion-f=tmp-f;atposion-g=tmp-g;atposion-h=tmp-h;}}else{tmp-Tparent=bestNode;move_to_open(&head_o,tmp);continue;}}2.2.9转到2.2.4继续执行。3结果分析3.1程序运行情况示例实验在DEVC++平台上进行，采用C++语言实现算法。实验的完整代码可参见文件myA_star.cpp。实验的输入数据为：初始状态和目标状态，其中以0代替八数码中的空格。实验的输出可由用户进行选择，以输入初始状态283164705，输出状态123804765为例：选择手动搜索，则我们可以看到A*算法的决策过程，即每一次从open表中拿出的节点，以7及该节点生成的最优节点的非前驱的后继节点都是什么。部分截图如下所示：选择自动搜索，则程序自动运行，直到找到目标状态才会暂停，用户按任意键便会生成从初始状态到目标状态的最佳路径。部分截图如下图所示：83.2算法性能分析利用time.h头文件中的clock()函数进行计时，输入一些数据进行运行测试。计时范围为开始搜索，到找到目标状态。下面输入的目标状态均为：123804765对于输入723810654，从初始状态到目标状态需要13步，搜索到最佳路径用时0S。对于输入425701386，从初始状态到目标状态需要20步，搜索到最佳路径用时0S。9对于输入873160542，从初始状态到目标状态需要21步，搜索到最佳路径用时1S。对于输入156274038，从初始状态到目标状态需要22步，搜索到最佳路径用时3S。可以看出当从初始状态到目标状态所用步数增加时，搜索用时会增加。当步数越大时，步数的增加会造成搜索用时急剧上升。下面是一张输入为723810654时的算法性能分析表：3.3与其他算法对比对比BFS算法，可以看出在初始状态到目标状态的步数在5步以内时，BFS