文档介绍：螇中国石油大学(北京)羄实 薁验艿报薆告羄实验课程:人工智能导论羂实验名称:搜索策略实验肁班级:自动化09-2学号:10姓名:何威慑虿实验台号:成绩:肄实验日期:年月日莃实验目的:蒈 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解。N数码难题,理解求解流程和搜索顺序。莈二、实验内容:膄根据任务要求,本文采用A*搜索算法。但要在计算机上通过编程解决该问题,还应当解决该问题在计算机上表示的方式,并设计合适的启发函数,以提高搜索效率。螄①状态的表示膀在A*算法中,需要用到open表和closed表,特别是在open表中,待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中,必须要有能指向下一个扩展节点的指针,以完成对open表中元素的索引。从这一点上看,open表中的元素相互间即构成了一个线性表,因此初步选定使用结构体表示问题的状态。膆如图3所示,表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。芄图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*算法的定义,启发函数应满足:。肃其中:表示从当前节点n到目标节点s_g的最优路径的实际代价。薀并且,在满足的条件下,的值越大它所携带的启发性信息越多,A*算法搜索时扩展的节点就越少,搜索效率就越高。蒆在8数码问题中,常用的启发函数为:“不在位”数码个数,或数码“不在位”的距离和。显然,后者的不小于前者,因此本文中采用数码“不在位”的距离和作为启发函数。薃③规则库设计蒄0在某一位置时,能选择向左、向右、向上、向下移动中的哪几种策略进行移动,主要是由当前0所处位置(更具体地说是当前位置的行列号)和其祖父节点(为提高搜索效率,新扩展的节点应当至少不为其祖父节点)所决定的。羈当然,按照A*算法的思想,每扩展出一个新节点,都要判断其是否为有效子节点,不为有效子节点的不能加入到open表中。这一段的具体过程可以参考程序流程部分。蕿因此移动的规则库可以写成如下形式:蚃左移: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左移蒃右移: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右移聿上移:if(p->i_0>=1)//空格所在列号不小于1,可上移蚇 {膃temp=p->father;莁if(temp!=NULL&&temp->i_0==p->i_0-1&&temp->j_0==p->j_0) ;//新节点与其祖父节点相同,无操作螁 else//新节点与其祖父节点不同,或其父节点为起始节点莆{蒆……(扩展新节点,并判断是否加入open表)//详细代码见源程序螂}艿 }//end上移葿下移:if(p->i_0<=1)//空格所在列号不大于1,可下移薆 {膃temp=p->father;羁if(temp!=NULL&&temp->i_0==p->i_0+1&&temp->j_0==p->j