1、但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。状态的表示在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。从这一点上看，open表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。如图3所示，表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。图3 结构体现在进一步考虑DATA中包括的内容：如图1、2所示，8数码问题的
2、提出是以一个数表表示的，因此本文中采用一个的二维数组s33表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针father，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优路径。另一方面，A*搜索算法是通过考察节点的代价值来决定open表的排序的，因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。根据A*算法的定义，当前节点的代价值由估价函数给出，即：其中：表示当前节点n在搜索树中的深度；是启发函数。因此，在DATA还应包括表示当前节点代价、深度和启发信息的、。最后，为提高程序的
3、运行效率，减少程序扩展节点时搜索量，将当前0所处位置（i_0：0在s33中所处行号，j_0：0在s33中所处列号）也存储在DATA中。综上所述，问题状态的表示如下图所示。图4 问题的状态表示启发函数的设计根据A*算法的定义，启发函数应满足：表示从当前节点n到目标节点s_g的最优路径的实际代价。并且，在满足的条件下，的值越大它所携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。在8数码问题中，常用的启发函数为： “不在位”数码个数，或数码“不在位”的距离和。显然，后者的不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。规则库设计0在某一位置时，能选择向左、向右、向
4、上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到open表中。这一段的具体过程可以参考程序流程部分。因此移动的规则库可以写成如下形式：左移：if（p-j_0=1） /空格所在列号不小于1,可左移 temp=p-father; if（temp!=NULL&temp-i_0=p-i_0&j_0-1=p-j_0） ; /新节点与其祖父节点相同，无操作 else /新节点与其祖父节点不同
5、，或其父节点为起始节点 （扩展新节点，并判断是否加入open表）/详细代码见源程序 /end左移右移：j_0 /end右移上移：i_0=1） /空格所在列号不小于1,可上移i_0-1&j_0=p- /end上移下移：i_0next; Add_to_closed（n）; open=temp; if（Test_A_B（n,&s_g） /当前n指向节点为目标时，跳出程序结束；否则，继续下面的步骤 return n; Expand_n（n）; /扩展节点n return NULL;/*/* 生成当前节点n通过走步可以得到的所有状态 */void Expand_n（struct node *p） str
6、uct node *temp,*same; if（p-j_0） /新节点与其祖父节点相同 ; temp=（struct node *）malloc（sizeof（struct node）; /给新节点分配空间 Copy_node（p,temp）; /拷贝p指向的节点状态 temp-stemp-i_0temp-j_0=temp-j_0-1; /空格左移j_0-1=0;j_0-;d+; Calculate_f（temp-d,temp）; /修改新节点的代价值father=p; /新节点指向其父节点 if（same=Search_A（closed,temp） /在closed表中找到与新节点状态相同
7、的节点 if（temp-ff） /temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 Remove_p（closed,same）; /从closed表中删除与temp指向节点状态相同的节点 Add_to_open（temp）; sum_node+; else; else if（same=Search_A（open,temp） /在open表中找到与新节点状态相同的节点f） /temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 Remove_p（open,same）; /从open表中删除与temp指向节点状态相同的节点 else ; else
8、 /新节点为完全不同的新节点，加入open表 Add_to_open（temp）; sum_node+; temp=（struct node *）malloc（sizeof（struct node）; Copy_node（p,temp）; temp-j_0+1; /空格右移j_0+1=0;j_0+; Calculate_f（temp- /新节点指向其父节点=1） /空格所在列号不小于1,上移i_0-1temp-j_0; /空格上移j_0=0;i_0-;=1） /空格所在列号不大于1,下移i_0+1temp- /空格下移i_0+;/* 添加p指向的节点到open表中 */void Add_to_
9、open（struct node *p） struct node *p1,*p2; p1=open; /初始时p1指向open表首部 p2=NULL; if（open=NULL） /open表为空时，待插入节点即为open表第一个元素，open指向该元素 p-next=NULL; open=p; else /open表不为空时，添加待插入节点，并保证open表代价递增的排序 while（p1!p-fp1-f） p2=p1; /p2始终指向p1指向的前一个元素 p1=p1- if（p2=NULL） /待插入节点为当前open表最小next=open; else if（p1=NULL） /待插入节点为当前open表最大 p2-next=p; else /待插入节点介于p2、p1之间next=p1;/* 添加p指向的节点到closed表中 */void Add_to_closed（struct node
