关于A算法实现的8数码问题(人工智能)VIP免费

基于A星算法解决8数码问题的编程实现基于A*算法解决把数码问题《人工智能》专业：信息与计算科学班级：101001学号：101001102姓名：陈斌指导老师：时华日期：2013年10月14日一、问题描述8数码问题又称9宫问题，与游戏“华容道”类似。意在给定的棋格的8个格子内分别放一个符号，符号之间互不相同，余下的一格为空格。并且通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的符号经过若干次移动由初始状态达1基于A星算法解决8数码问题的编程实现到目标状态，这个过程中只有空格附近的符号可以朝空格的方向移动，且每次只能移动一个符号。为方便编程和表示，本文中8个格子内的符号分别取1—8的8个数字表示，空格用0表示。并给定8数码的初始状态和目标状态分别如图1、2所示。2基于A星算法解决8数码问题的编程实现图1初始状态图2目标状态则要求以图1为初始状态，通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图2所示目标状态。二、算法设计根据任务要求，本文采用A*搜索算法。但要在计算机上通过编程解决该问题还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。①状态的表示在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。从这一点上看，open表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。如图3所示，表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。3基于A星算法解决8数码问题的编程实现图3结构体现在进一步考虑DATA中包括的内容：如图1、2所示，8数码问题的提出是以一个数表表示的，因此本文中采用一个的二维数组s[3][3]表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针father，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优路径。另一方面，A*搜索算法是通过考察节点的代价值来决定open表的排序的，因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。根据A*算法的定义，当前节点的代价值由估价函数给出，即：其中：表示当前节点n在搜索树中的深度；是启发函数。因此，在DATA还应包括表示当前节点代价、深度和启发信息的、、。最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s[3][3]中所处行号，j_0：0在s[3][3]中所处列号)也存储在DATA中。综上所述，问题状态的表示如下图所示。4基于A星算法解决8数码问题的编程实现图4问题的状态表示②启发函数的设计根据A*算法的定义，启发函数应满足：。其中：表示从当前节点n到目标节点s_g的最优路径的实际代价。并且，在满足的条件下，的值越大它所携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。在8数码问题中，常用的启发函数为：“不在位”数码个数，或数码“不在位”的距离和。显然，后者的不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。③规则库设计0在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到open表中。这一段的具体过程可以参考程序流程部分。因此移动的规则库可以写成如下形式：5基于A星算法解决8数码问题的编程实现左移：if(p->j_0>=1)//空格所在列号不小于1,可左移{temp=p->father;if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0-1==p->j_0);//新节点与其祖父节点相同，无操作else//新节点与其祖父节点不同，或其父节点为起始节点{……(扩展新节点，并判断是否加入open表)//详细代码见源程序}}//end左...