《西电人工智能大作业[资料教育]》由会员分享,可在线阅读,更多相关《西电人工智能大作业[资料教育](21页珍藏版)》请在金锄头文库上搜索。
1、人工智能大作业学生:021151* 021151*时间:2013年12月4号一启发式搜索解决八数码问题1. 实验目的问题描述:现有一个3*3的棋盘,其中有0-8一共9个数字,0表示空格,其他的数字可以和0交换位置(只能上下左右移动)。给定一个初始状态和一个目标状态,找出从初始状态到目标状态的最短路径的问题就称为八数码问题。例如:实验问题为283104765123804765到目标状态:从初始状态: 要求编程解决这个问题,给出解决这个问题的搜索树以及从初始节点到目标节点的最短路径。2. 实验设备及软件环境利用计算机编程软件Visual C+ 6.0,用C语言编程解决该问题。3. 实验方法(1).
2、算法描述:.把初始节点S放到OPEN表中,计算,并把其值与节点S联系起来。.如果OPEN表是个空表,则失败退出,无解。.从OPEN表中选择一个值最小的节点。结果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一节点作为节点。.把节点从OPEN表中移出,并把它放入CLOSED的扩展节点表中。.如果是目标节点,则成功退出,求得一个解。.扩展节点,生成其全部后继节点。对于的每一个后继节点: a.计算。 b.如果既不在OPEN表中,也不在CLOSED表中,则用估价函数把它添加入OPEN表。从加一指向其父辈节点的指针,以便一旦找到目标节点时记住一个解答路径。 c.如果已在OP
3、EN表或CLOSED表上,则比较刚刚对计算过的值和前面计算过的该节点在表中的值。如果新的值较小,则 I.以此新值取代旧值。 II.从指向,而不是指向它的父辈节点。 III.如果节点在CLOSED表中,则把它移回OPEN表。 转向,即GO TO 。 (2).流程图描述: (3).程序源代码:#include #includestruct nodeint number33;/用二维数组存放8数码 int W;/W表示与目标状态相比错放的数码数int Depth;/记录当前节点的深度struct node *parent;/指向父节点的指针struct node *next;/指向链表中下一个节点的
4、指针;int CounterW(int Number33)/函数说明:计算当前状态与目标状态的W值int i,j;int W=0;int Desnode33=1,2,3,8,0,4,7,6,5;for(i=0; i3; i+)for(j=0; j3; j+)if(Numberij != Desnodeij)W+; return W;void PrintNode(node *A)int i,j;for(i=0; i3; i+)for(j=0; jnumberij);printf(n);printf(n);int CheckNode(node *open, node *close, int a33
5、)/检验该节点状态是否出现过的子程序int CheckFlag=0;int flag1,flag2;node *p=open;node *q=close;while(p != NULL) flag1=0;for(int i=0; i3; i+)for(int j=0; jnumberij)flag1+;if(flag1 = 9)break;elsep=p-next;while(q != NULL)flag2=0;for(int i=0; i3; i+)for(int j=0; jnumberij)flag2+;if(flag2 = 9)break;elseq=q-next;if(flag1=9
6、) | (flag2=9)CheckFlag=1;/如果出现过,置标志位为1return CheckFlag;struct node *FindNextNode(node *Prenode, node *open, node *close) /扩展Prenode指向的节点,并将扩展所得结点组成一条单链表int i,j,m,n; /循环变量int temp; /临时替换变量int flag=0; int a33;/临时存放二维数组struct node *p, *q, *head; head=(node *)malloc(sizeof(node);/head指向该链表首结点,并且作为返回值p=h
7、ead;q=head;head-next=NULL;/初始化for(i=0;i3;i+)/找到二维数组中0的位置for(j=0;jnumberij=0)flag=1;break;if(flag=1)break;/根据0的位置的不同,对a进行相应的变换 for(m=0;mnumber赋给afor(n=0;nnumbermn; if(i+1=2)/情况1,0向下移temp=aij; aij=ai+1j; ai+1j=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)mal
8、loc(sizeof(node); for(m=0;mnumber for(n=0;nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1;/子结点的深度等于其父结点深度加1 q-W=CounterW(q-number); q-next=NULL; p-next=q;/扩展节点插入head链表 p=p-next; for(m=0;mnumber重新赋给afor(n=0;nnumbermn;if(i-1=0)/情况2,0向上移temp=aij; aij=ai-1j; ai-1j=temp;int CheckN
9、um=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0;mnumber for(n=0;nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1; q-W=CounterW(q-number); q-next=NULL; p-next=q; p=p-next; for(m=0; m3; m+)for(n=0; nnumbermn;if(j-1=0)/情况3,0向
10、左移 temp=aij; aij=aij-1; aij-1=temp;int CheckNum=CheckNode(open, close, a); if(CheckNum = 0)/若该结点未出现过则执行下面的操作 q=(node *)malloc(sizeof(node); for(m=0; mnumber for(n=0; nnumbermn=amn; PrintNode(q); q-parent=Prenode; q-Depth=q-parent-Depth+1; q-W=CounterW(q-number); q-next=NULL; p-next=q; p=p-next; for(m=0;m3;m+)for(n=0;nnumbermn;if(j+1=2)/情况4,0向右移temp=aij; aij