1、关于A算法实现的8数码问题人工智能 基于A*算法解决把数码问题 人工智能 专 业： 信息与计算科学 班 级： 101001 学 号： 101001102 姓 名： 陈 斌 指导老师： 时 华 日 期：2013年10月14日一、问题描述8数码问题又称9宫问题，与游戏“华容道”类似。意在给定的棋格的8个格子内分别放一个符号，符号之间互不相同，余下的一格为空格。并且通常把8个符号在棋格上的排列顺序称作8数码的状态。开始时，规则给定一个初始状态和一个目标状态，并要求被试者对棋格内的符号经过若干次移动由初始状态达到目标状态，这个过程中只有空格附近的符号可以朝空格的方向移动，且每次只能移动一个符号。为方便
2、编程和表示，本文中8个格子内的符号分别取18的8个数字表示，空格用0表示。并给定8数码的初始状态和目标状态分别如图1、2所示。 图1 初始状态 图2 目标状态则要求以图1为初始状态，通过交换0和0的上、下、左、右四个方位的数字（每次只能和其中一个交换），达到图2所示目标状态。二、算法设计根据任务要求，本文采用A*搜索算法。但要在计算机上通过编程解决该问题，还应当解决该问题在计算机上表示的方式，并设计合适的启发函数，以提高搜索效率。状态的表示在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，必须要有能指向下一个扩展
3、节点的指针，以完成对open表中元素的索引。从这一点上看，open表中的元素相互间即构成了一个线性表，因此初步选定使用结构体表示问题的状态。如图3所示，表示问题的结构体包括表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。图3 结构体现在进一步考虑DATA中包括的内容：如图1、2所示，8数码问题的提出是以一个数表表示的，因此本文中采用一个的二维数组s33表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针father，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优
4、路径。另一方面，A*搜索算法是通过考察节点的代价值来决定open表的排序的，因此在表示当前状态的DATA中还应该有对当前节点代价值的描述。根据A*算法的定义，当前节点的代价值由估价函数给出，即：其中：表示当前节点n在搜索树中的深度； 是启发函数。因此，在DATA还应包括表示当前节点代价、深度和启发信息的、。最后，为提高程序的运行效率，减少程序扩展节点时搜索量，将当前0所处位置(i_0：0在s33中所处行号，j_0：0在s33中所处列号)也存储在DATA中。综上所述，问题状态的表示如下图所示。图4 问题的状态表示启发函数的设计根据A*算法的定义，启发函数应满足：。其中：表示从当前节点n到目标节点
5、s_g的最优路径的实际代价。并且，在满足的条件下，的值越大它所携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。在8数码问题中，常用的启发函数为： “不在位”数码个数，或数码“不在位”的距离和。显然，后者的不小于前者，因此本文中采用数码“不在位”的距离和作为启发函数。规则库设计0在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到
6、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_0father; if(temp!=NULL&temp-i_0=p-i_0&temp-j_0+1=p-j_0) ; /新节点与其祖父节点相同
7、，无操作 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_0father; if(temp!=NULL&temp-i_0=p-i_0+1&tem
8、p-j_0=p-j_0) ; /新节点与其祖父节点相同，无操作 else /新节点与其祖父节点不同，或其父节点为起始节点 (扩展新节点，并判断是否加入open表)/详细代码见源程序 /end下移程序流程主程序流程图：其中，扩展节点n的具体步骤如下：a) 首先判断其是否在closed表已经出现过, 如果出现过，并且新节点的代价值比其小，则应将其从closed表删除，同时将新节点加入到open表；如果没有出现过，则转b。b) 判断其是否已经存在于open表中待扩展，如果出现过，并且新节点的代价值比其小，则应将其从open表删除，同时将新节点加入到open表；如果没有出现过，则说明该节点为一个全新的
9、节点，转c。c) 将该节点加入open表。3、程序代码#include Stdio.h#include Conio.h#include stdlib.h#include math.hvoid Copy_node(struct node *p1,struct node *p2);void Calculate_f(int deepth,struct node *p);void Add_to_open(struct node *p);void Add_to_closed(struct node *p);void Remove_p(struct node *name,struct node *p);i
10、nt Test_A_B(struct node *p1,struct node *p2);struct node * Solution_Astar(struct node *p);void Expand_n(struct node *p);struct node * Search_A(struct node *name,struct node *temp);void Print_result(struct node *p);/* 定义8数码的节点状态 */typedef struct node int s33; /当前8数码的状态 int i_0; /当前空格所在行号 int j_0; /当前
11、空格所在列号 int f; /当前代价值 int d; /当前节点深度 int h; /启发信息，采用数码“不在位”距离和 struct node *father; /指向解路径上该节点的父节点 struct node *next; /指向所在open或closed表中的下一个元素;struct node s_0=3,8,2,1,0,5,7,6,4,1,1,0,0,0,NULL,NULL; /定义初始状态struct node s_g=1,2,3,8,0,4,7,6,5,1,1,0,0,0,NULL,NULL; /定义目标状态struct node *open=NULL; /建立open表指针
12、struct node *closed=NULL; /建立closed表指针int sum_node=0; /用于记录扩展节点总数int main(void) struct node s,*target; Copy_node(&s_0,&s); Calculate_f(0,&s); /拷贝8数码初始状态，初始化代价值 target=Solution_Astar(&s); /求解主程序 if(target) Print_result(target); /输出解路径 else printf(问题求解失败！); getch(); return 0;/*/* A*算法 */*/struct node
13、* Solution_Astar(struct node *p) struct node *n,*temp; Add_to_open(p); /将s_0放入open表 while(open!=NULL) /只要open表中还有元素，就继续对代价最小的节点进行扩展 n=open; /n指向open表中当前要扩展的元素 temp=open-next; Add_to_closed(n); open=temp; if(Test_A_B(n,&s_g) /当前n指向节点为目标时，跳出程序结束；否则，继续下面的步骤 return n; Expand_n(n); /扩展节点n return NULL;/*/
14、* 生成当前节点n通过走步可以得到的所有状态 */*/void Expand_n(struct node *p) struct node *temp,*same; 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 /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(p,temp); /拷贝p指向的
15、节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0temp-j_0-1; /空格左移 temp-stemp-i_0temp-j_0-1=0; temp-j_0-; temp-d+; Calculate_f(temp-d,temp); /修改新节点的代价值 temp-father=p; /新节点指向其父节点 if(same=Search_A(closed,temp) /在closed表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 Remove_p(closed,same);
16、 /从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else; else if(same=Search_A(open,temp) /在open表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 Remove_p(open,same); /从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else ; else /新节点为完全不同的新节点，加入open表 Add_to_open(temp
17、); sum_node+; /end左移 if(p-j_0father; if(temp!=NULL&temp-i_0=p-i_0&temp-j_0+1=p-j_0) /新节点与其祖父节点相同 ; else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(p,temp); /拷贝p指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0temp-j_0+1; /空格右移 temp-stemp-i_0temp-j_0+1=0;
18、temp-j_0+; temp-d+; Calculate_f(temp-d,temp); /修改新节点的代价值 temp-father=p; /新节点指向其父节点 if(same=Search_A(closed,temp) /在closed表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 Remove_p(closed,same); /从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else; else if(same=Search_A(
19、open,temp) /在open表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 Remove_p(open,same); /从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else ; else /新节点为完全不同的新节点，加入open表 Add_to_open(temp); sum_node+; /end右移 if(p-i_0=1) /空格所在列号不小于1,上移 temp=p-father; if(temp!=NULL&temp-i_0=p-
20、i_0-1&temp-j_0=p-j_0) /新节点与其祖父节点相同 ; else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)malloc(sizeof(struct node); /给新节点分配空间 Copy_node(p,temp); /拷贝p指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0-1temp-j_0; /空格上移 temp-stemp-i_0-1temp-j_0=0; temp-i_0-; temp-d+; Calculate_f(temp-d,temp); /修改新节点的代价值 temp-
21、father=p; /新节点指向其父节点 if(same=Search_A(closed,temp) /在closed表中找到与新节点状态相同的节点 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表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比op
22、en表中相同状态节点代价小，加入open表 Remove_p(open,same); /从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else ; else /新节点为完全不同的新节点，加入open表 Add_to_open(temp); sum_node+; /end上移 if(p-i_0father; if(temp!=NULL&temp-i_0=p-i_0+1&temp-j_0=p-j_0) /新节点与其祖父节点相同 ; else /新节点与其祖父节点不同，或其父节点为起始节点 temp=(struct node *)ma
23、lloc(sizeof(struct node); /给新节点分配空间 Copy_node(p,temp); /拷贝p指向的节点状态 temp-stemp-i_0temp-j_0=temp-stemp-i_0+1temp-j_0; /空格下移 temp-stemp-i_0+1temp-j_0=0; temp-i_0+; temp-d+; Calculate_f(temp-d,temp); /修改新节点的代价值 temp-father=p; /新节点指向其父节点 if(same=Search_A(closed,temp) /在closed表中找到与新节点状态相同的节点 if(temp-ff) /
24、temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表 Remove_p(closed,same); /从closed表中删除与temp指向节点状态相同的节点 Add_to_open(temp); sum_node+; else; else if(same=Search_A(open,temp) /在open表中找到与新节点状态相同的节点 if(temp-ff) /temp指向的节点,其代价比open表中相同状态节点代价小，加入open表 Remove_p(open,same); /从open表中删除与temp指向节点状态相同的节点 Add_to_open(temp);
25、 sum_node+; else ; else /新节点为完全不同的新节点，加入open表 Add_to_open(temp); sum_node+; /end下移/*/* 添加p指向的节点到open表中 */*/void Add_to_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!=NULL&p-fp1-f) p2=p1; /p2始终指向p1指向的前一个元素 p1=p1-next; if(p2=NULL) /待插入节点为当前open表最小 p-next=open; open=p; else if(p1=NULL) /待插入节点为当前open表最大 p-next=NULL; p2-next=p; else /待插入节点介于p2、p1之间 p2-next=p; p-next=p1; /*/* 添加p指向的节点到closed表中 */*/void Add_to_closed(struct node
