人工智能大作业学生：021151* 021151*时间：2013年12月4号一启发式搜索解决八数码问题1. 实验目的问题描述：现有一个3*3的棋盘，其中有0-8一共9个数字，0表示空格，其他的数字可以和0交换位置（只能上下左右移动）。给定一个初始状态和一个目标状态，找出从初始状态到目标状态的最短路径的问题就称为八数码问题。例如：实验问题为283104765123804765到目标状态：从初始状态： 要求编程解决这个问题，给出解决这个问题的搜索树以及从初始节点到目标节点的最短路径。2. 实验设备及软件环境利用计算机编程软件Visual C+ 6.0，用C语言编程解决该问题。3. 实验方法(1).算法描述：.把初始节点S放到OPEN表中，计算，并把其值与节点S联系起来。.如果OPEN表是个空表，则失败退出，无解。.从OPEN表中选择一个值最小的节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一节点作为节点。.把节点从OPEN表中移出，并把它放入CLOSED的扩展节点表中。.如果是目标节点，则成功退出，求得一个解。.扩展节点，生成其全部后继节点。对于的每一个后继节点： a.计算。 b.如果既不在OPEN表中，也不在CLOSED表中，则用估价函数把它添加入OPEN表。从加一指向其父辈节点的指针，以便一旦找到目标节点时记住一个解答路径。 c.如果已在OPEN表或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;/指向链表中下一个节点的指针;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)/检验该节点状态是否出现过的子程序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) | (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=head;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 *)malloc(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 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=0)/情况3,0向左移 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