人工智能实验报告-八数码-(1)

《人工智能》实验一题目实验一启发式搜索算法1.实验内容：使用启发式搜索算法求解8数码问题。⑴编制程序实现求解8数码问题A算法，采用估价函数wnfndnpn，其中：dn是搜索树中结点n的深度；wn为结点n的数据库中错放的棋子个数；pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。⑵分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是pn的上界的hn的定义，并测试使用该估价函数是否使算法失去可采纳性。2.实验目的熟练掌握启发式搜索A算法及其可采纳性。3.数据结构与算法设计该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：typedefstructNode//棋盘{//节点结构体intdata[9];doublef,g;structNode*parent;//父节点}Node,*Lnode;intdata[9];数码数组：记录棋局数码摆放状态。structChess*Parent;父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下：（1）、把原棋盘压入队列；（2）、从棋盘取出一个节点；（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；（5）、跳到步骤（2）；3、算法的评价完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。!--[if!supportLists]--2、!--[endif]--内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；!--[if!supportLists]--3、!--[endif]--采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；源码：#includestdlib.h#includestdio.h#includemath.htypedefstructNode{//节点结构体intdata[9];doublef,g;structNode*parent;}Node,*Lnode;typedefstructStack{//OPENCLOSED表结构体Node*npoint;structStack*next;}Stack,*Lstack;Node*Minf(Lstack*Open){//选取OPEN表上f值最小的节点，返回该节点地址Lstacktemp=(*Open)-next,min=(*Open)-next,minp=(*Open);Node*minx;while(temp-next!=NULL){if((temp-next-npoint-f)(min-npoint-f)){min=temp-next;minp=temp;}temp=temp-next;}minx=min-npoint;temp=minp-next;minp-next=minp-next-next;free(temp);returnminx;}intCanslove(Node*suc,Node*goal){//判断是否可解inta=0,b=0,i,j;for(i=1;i9;i++)for(j=0;ji;j++){if((suc-data[i]suc-data[j])&&suc-data[j]!=0)a++;if((goal-data[i]goal-data[j])&&goal-data[j]!=0)b++;}if(a%2==b%2)return1;elsereturn0;}intEqual(Node*suc,Node*goal){//判断节点是否相等，相等，不相等for(inti=0;i9;i++)if(suc-data[i]!=goal-data[i])return0;return1;}Node*Belong(Node*suc,Lstack*list){//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstacktemp=(*list)-next;if(temp==NULL)returnNULL;while(temp!=NULL){if(Equal(suc,temp-npoint))returntemp-npoint;temp=temp-next;}returnNULL;}voidPutinto(Node*suc,Lstack*list){//把节点放入OPEN或CLOSED表中Stack*temp;temp=(Stack*)malloc(sizeof(Stack));temp-npoint=suc;temp-next=(*list)-next;(*list)-next=temp;}///////////////计算f值部分-开始//////////////////////////////doubleFvalue(Nodesuc,Nodegoal,intm){//计算f值switch(m){case1:{interror(Node,Node);intw=0;w=error(suc,goal);returnw+suc.g;}case2:{doubleDistance(Node,Node,int);doublep=0;for(inti=1;i=8;i++)p=p+Distance(suc,goal,i);returnp+suc.g;//f=h+g;}default:break;}}interror(Nodesuc,Nodegoal){//计算错位个数intw,i;w=0;for(i=0;i9;i++){if(suc.data[i]!=goal.data[i])w++;}returnw;}doubleDistance(Nodesuc,Nodegoal,inti){//计算方格的错位距离intk,h1,h2;for(k=0;k9;k++){if(suc.data[k]==i)h1=k;if(goal.data[k]==i)h2=k;}returndouble(fabs(h1/3-h2/3)+fabs(h1%3-h2%3));}///////////////计算f值部分-结束/////////////////////////////////////////////////////扩展后继节点部分的函数-开始/////////////////intBelongProgram(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,intm){//判断子节点是否属于OPEN或CLOSED表并作出相应的处理Node*temp=NULL;intflag=0;if((Belong(*suc,Open)!=NULL)||(Belong(*suc,Closed)!=NULL)){if(Belong(*suc,Open)!=NULL)temp=Belong(*suc,Open);elsetemp=Belong(*suc,Closed);if(((*suc)-g)(temp-g)){temp-parent=(*suc)-parent;temp-g=(*suc)-g;temp-f=(*suc)-f;flag=1;}}else{Putinto(*suc,Open);(*suc)-f=Fvalue(**suc,goal,m);}returnflag;}intCanspread(Nodesuc,intn){//判断空格可否向该方向移动，，，表示空格向上向下向左向右移inti,flag=0;for(i=0;i9;i++)if(suc.data[i]==0)break;switch(n){case1:if(i/3!=0)flag=1;break;case2:if(i/3!=2)flag=1;break;case3:if(i%3!=0)flag=1;break;case4:if(i%3!=2)flag=1;break;default:break;}returnflag;}voidSpreadchild(Node*child,intn){//扩展child节点的字节点n表示方向，，，表示空格向上向下向左向右移inti,loc,temp;for(i=0;i9;i++)child-data[i]=child-parent-data[i];for(i=0;i9;i++)if(child-data[i]==0)break;if(n==0)loc=i%3+(i/3-1)*3;elseif(n==1)loc=i%3+(i/3+1)*3;elseif(n==2)loc=i%3-1+(i/3)*3;elseloc=i%3+1+(i/3)*3;temp=child-data[loc];child-data[i]=temp;child-data[loc]=0;}voidSpread(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,intm){//扩展后继节点总函数inti;Node*child;for(i=0;i4;i++){if(Canspread(**suc,i+1))//判断某个方向上的子节点可否扩展{child=(Node*)malloc(sizeof(Node));//扩展子节点child-g=(*suc)-g+1;//算子节点的g值child-parent=(*suc);//子节点父指针指向父节点Spreadchild(child,i);//向该方向移动空格生成子节点if(BelongProgram(&child,Open,Closed,goal,m))//判断子节点是否属于OPEN或CLOSED表并作出相应的处理free(child);}}}///////////////////////扩展后继节点部分的函数-结束//////////////////////////////////Node*Process(Lnode*org,Lnode*goal,Lstack*Open,Lstack*Closed,intm){//总执行函数while(1){if((*Open)-next==NULL)returnNULL;//判断OPEN表是否为空，为空则失败退出Node*minf=Minf(Open);//从OPEN表中取出f值最小的节点Putinto(minf,Closed);//将节点放入CLOSED表中if(Equal(minf,*goal))returnminf;//如果当前节点是目标节点，则成功退出Spread(&minf,Open,Closed,**goal,m);//当前节点不是目标节点时扩展当前节点的后继节点}}intShownum(Node*result){//递归显示从初始状态到达目标状态的移动方法if(result==NULL)return0;else{intn=Shownum(result-parent);printf(第%d步：,n);for(inti=0;i3;i++){printf(\n);for(intj=0;j3;j++){if(result-data[i*3+j]!=0)printf(%d,result-data[i*3+j]);elseprintf(0);}}printf(\n);returnn+1;}}voidCheckinput(Node*suc){//检查输入i