C语言实现8数码问题

1、实验目的(1)熟悉人工智能系统中的问题求解过程；(2)熟悉状态空间中的盲目搜索策略；(3)掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。2、实验要求用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解8数码问题3、实验内容（1）采用宽度优先算法，运行程序，要求输入初始状态假设给定如下初始状态S0283164705和目标状态Sg216408753验证程序的输出结果，写出心得体会。（2）对代码进行修改（选作），实现深度优先搜索求解该问题提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，找一个没有被扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。4源代码及实验结果截图#includestdio.h#includestdlib.h#includemath.h//八数码状态对应的节点结构体structNode{ints[3][3];//保存八数码状态，0代表空格intf,g;//启发函数中的f和g值structNode*next;structNode*previous;//保存其父节点};intopen_N=0;//记录Open列表中节点数目//八数码初始状态intinital_s[3][3]={2,8,3,1,6,4,7,0,5};//八数码目标状态intfinal_s[3][3]={2,1,6,4,0,8,7,5,3};//------------------------------------------------------------------------//添加节点函数入口，方法：通过插入排序向指定表添加//------------------------------------------------------------------------voidAdd_Node(structNode*head,structNode*p){structNode*q;if(head-next)//考虑链表为空{q=head-next;if(p-fhead-next-f){//考虑插入的节点值比链表的第一个节点值小p-next=head-next;head-next=p;}else{while(q-next)//考虑插入节点x，形如a=x=b{if((q-fp-f||q-f==p-f)&&(q-next-fp-f||q-next-f==p-f)){p-next=q-next;q-next=p;break;}q=q-next;}if(q-next==NULL)//考虑插入的节点值比链表最后一个元素的值更大q-next=p;}}elsehead-next=p;}//------------------------------------------------------------------------//删除节点函数入口//------------------------------------------------------------------------voiddel_Node(structNode*head,structNode*p){structNode*q;q=head;while(q-next){if(q-next==p){q-next=p-next;p-next=NULL;if(q-next==NULL)return;//free(p);}q=q-next;}}//------------------------------------------------------------------------//判断两个数组是否相等函数入口//------------------------------------------------------------------------intequal(ints1[3][3],ints2[3][3]){inti,j,flag=0;for(i=0;i3;i++)for(j=0;j3;j++)if(s1[i][j]!=s2[i][j]){flag=1;break;}if(!flag)return1;elsereturn0;}//------------------------------------------------------------------------//判断后继节点是否存在于Open或Closed表中函数入口//------------------------------------------------------------------------intexit_Node(structNode*head,ints[3][3],structNode*Old_Node){structNode*q=head-next;intflag=0;while(q)if(equal(q-s,s)){flag=1;Old_Node-next=q;return1;}elseq=q-next;if(!flag)return0;}//------------------------------------------------------------------------//计算p(n)的函数入口//其中p(n)为放错位的数码与其正确的位置之间距离之和//具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和//------------------------------------------------------------------------intwrong_sum(ints[3][3]){inti,j,fi,fj,sum=0;for(i=0;i3;i++)for(j=0;j3;j++){for(fi=0;fi3;fi++)for(fj=0;fj3;fj++)if((final_s[fi][fj]==s[i][j])){sum+=fabs(i-fi)+fabs(j-fj);break;}}returnsum;}//------------------------------------------------------------------------//获取后继结点函数入口//检查空格每种移动的合法性，如果合法则移动空格得到后继结点//------------------------------------------------------------------------intget_successor(structNode*BESTNODE,intdirection,structNode*Successor)//扩展BESTNODE，产生其后继结点SUCCESSOR{inti,j,i_0,j_0,temp;for(i=0;i3;i++)for(j=0;j3;j++)Successor-s[i][j]=BESTNODE-s[i][j];//获取空格所在位置for(i=0;i3;i++)for(j=0;j3;j++)if(BESTNODE-s[i][j]==0){i_0=i;j_0=j;break;}switch(direction){case0:if((i_0-1)-1){temp=Successor-s[i_0][j_0];Successor-s[i_0][j_0]=Successor-s[i_0-1][j_0];Successor-s[i_0-1][j_0]=temp;return1;}elsereturn0;case1:if((j_0-1)-1){temp=Successor-s[i_0][j_0];Successor-s[i_0][j_0]=Successor-s[i_0][j_0-1];Successor-s[i_0][j_0-1]=temp;return1;}elsereturn0;case2:if((j_0+1)3){temp=Successor-s[i_0][j_0];Successor-s[i_0][j_0]=Successor-s[i_0][j_0+1];Successor-s[i_0][j_0+1]=temp;return1;}elsereturn0;case3:if((i_0+1)3){temp=Successor-s[i_0][j_0];Successor-s[i_0][j_0]=Successor-s[i_0+1][j_0];Successor-s[i_0+1][j_0]=temp;return1;}elsereturn0;}}//------------------------------------------------------------------------//从OPen表获取最佳节点函数入口//------------------------------------------------------------------------structNode*get_BESTNODE(structNode*Open){returnOpen-next;}//------------------------------------------------------------------------//输出最佳路径函数入口//------------------------------------------------------------------------voidprint_Path(structNode*head){structNode*q,*q1,*p;inti,j,count=1;p=(structNode*)malloc(sizeof(structNode));//通过头插法变更节点输出次序p-previous=NULL;q=head;while(q){q1=q-previous;q-previous=p-previous;p-previous=q;q=q1;}q=p-previous;while(q){if(q==p-previous)printf(八数码的初始状态：\n);elseif(q-previous==NULL)printf(八数码的目标状态：\n);elseprintf(八数码的中间态%d\n,count++);for(i=0;i3;i++)for(j=0;j3;j++){printf(%4d,q-s[i][j]);if(j==2)printf(\n);}printf(f=%d,g=%d\n\n,q-f,q-g);q=q-previous;}}//------------------------------------------------------------------------//A*子算法入口:处理后继结点//------------------------------------------------------------------------voidsub_A_algorithm(structNode*Open,structNode*BESTNODE,structNode*Closed,structNode*Successor){structNode*Old_Node=(structNode*)malloc(sizeof(structNode));Successor-previous=BESTNODE;//建立从successor返回BESTNODE的指针Successor-g=BESTNODE-g+1;//计算后继结点的g值//检查后继结点是否已存在于Open和Closed表中，如果存在：该节点记为old_Node，比较后继结点的g值和表中old_Node节点//g值，前者小代表新的路径