《人工智能》实验报告

《人工智能》实验报告学生班级网络工程学生姓名学号201030570048实验时间2012-09-17实验地点C5-713实验名称八数码问题实验成绩一、实验目的实现八数码问题：在3X3九宫格棋盘上摆有8个将牌，每一个将牌都可有1-8数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称为初始状态）和一个目标布局（称为目标状态），问如何移动将牌实现从初始状态到目的状态的转变，问题的解答就是给出一个合法的走步序列。设评价函数f(n)=d(n)+W(n),其中d(n)表示结点的深度，W(n)表示不在位的将牌数，f(n）可估计出通向目标结点的希望程度。二、实验过程八数码问题的关键在于求出每个状态估计函数的大小并刷新open表将open表按评价函数值的大小从小到大进行排序。由于要避免结点在之前是否被搜索过，所以要对链表进行for循环判断。每一次刷新open表时都需要将最小的元素置顶，相同的元素较前出现的置前，每个节点都有一个指向父节点的指针一遍最后得出最终路径。数据结构：structNode{intarray[3][3];intquanzhi;Node*parent;Node*next;intlevel;};下面是设置的各函数：//复制数组voidcopyArray(intc[3][3],intd[3][3])//初始化结点voidInitNode(node&l)/确认插入的位置intLocate(nodea,Nodeb)/插入结点intInsertNode(nodea,inti,Nodeb)/删除结点intDeleteNode(nodea,inti)//判断两数组是否相同，相同返回trueboolisSame(intc[3][3],intd[3][3])//在链表中查找结点，找到返回trueboolisfind(nodea,Nodeb)//在链表中查找结点，若找到返回该节点的深度intfind(AndGetLevelnodea,Nodeb)//在链表中查找结点并返回该节点在链表中的位置。intfindAndGetIndex(nodea,Nodeb)//计算不在位的将牌数intcomputeF(intc[3][3],intd[3][3])//输出该节点的数组voidprint(intw[][3],inti,intj)//根据父节点返回路径并输出路径voidshuchu(nodea)三、实验结果开始结点：283164705目标结点：123804765初始结点：123804765目标结点：123804765初始结点283064175目标结点123804765四、讨论与分析实现过程由以下伪代码：读入初始状态和目标状态，并计算初始状态评价函数值f；把初始状态假如open表中；While（未找到解&&状态表非空）①在open表中找到评价值最小的节点，作为当前结点；②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③；③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；⑤把当前结点从open表中移除；Endwhile五、实验总结与思考本次实验主要是考察对A*算法的了解，通过这次作业我更加了解了图搜索的方法并且在脑海里形成了一定的思维方法，做题目时有了一定的步骤和想法，但是作业过程中由于对链表指针操作的不熟悉导致了很多错误，指向父节点的parent指针总会在经过一系列操作后消失不见，导致最后午饭从目标结点沿路返回，不过经过一系列调试后最终解决。六、附录：关键代码#includeiostream#includemalloc.h#includemath.husingnamespacestd;structNode{intarray[3][3];intquanzhi;//不在位的将牌数Node*parent;Node*next;//在open表中指向下一个元素intlevel;};typedefNode*node;//复制数组voidcopyArray(intc[3][3],intd[3][3]){for(inti1=0;i1=2;i1++){for(intj1=0;j1=2;j1++){c[i1][j1]=d[i1][j1];}}}//初始化结点voidInitNode(node&l){l=(node)malloc(sizeof(Node));if(!l)exit(1);l-parent=NULL;l-next=NULL;}//确认插入的位置intLocate(nodea,Nodeb)//a为open表的首头结点{inti=0;nodep=a-next;while(p){i++;if((p-quanzhi+p-level)(b.quanzhi+b.level))//判断双方估计函数值大小returni;if((p-quanzhi+p-level)==(b.quanzhi+b.level)){intj=i+1;returnj;}p=p-next;}return(i+1);}//插入结点intInsertNode(nodea,inti,Nodeb){intj=0;nodes,p=a;while(p&&ji-1){//找到位置j++;p=p-next;}s=(node)malloc(sizeof(Node));copyArray(s-array,b.array);//复制数组s-level=b.level;s-parent=b.parent;s-quanzhi=b.quanzhi;s-next=p-next;p-next=s;return1;}//删除结点intDeleteNode(nodea,inti){intj=0;nodeq,p=a;while(p&&ji-1){j++;p=p-next;}if(!p-next||ji-1)return0;q=p-next;p-next=q-next;return1;}//判断两数组是否相同，相同返回trueboolisSame(intc[3][3],intd[3][3]){for(inti1=0;i1=2;i1++){for(intj1=0;j1=2;j1++){if(d[i1][j1]!=c[i1][j1])returnfalse;}}returntrue;}//在链表中查找结点，找到返回trueboolisfind(nodea,Nodeb){nodep=a-next;while(p){if(compare1(p-array,b.array)==1)returntrue;p=p-next;}returnfalse;}//在链表中查找结点并返回该节点的深度intfind(AndGetLevelnodea,Nodeb){inti=0;nodep=a-next;while(p){i++;if(compare1(p-array,b.array)==1)returnp-level;p=p-next;}return1000;}//在链表中查找结点并返回该节点在链表中的位置。intfindAndGetIndex(nodea,Nodeb){inti=0;nodep=a-next;while(p){i++;if(compare1(p-array,b.array)==1)returni;p=p-next;}}//计算估计函数intcomputeF(intc[3][3],intd[3][3]){intcount=0;for(inti=0;i3;i++)for(intj=0;j3;j++)for(intk=0;k3;k++)for(intl=0;l3;l++)if(c[i][j]==d[k][l]&&c[i][j]!=0)count+=abs(i-k)+abs(j-l);returncount;}//输出该节点的数组voidprint(intw[][3],inti,intj){for(inti0=0;i0=i;i0++){coutendl;for(intj0=0;j0=j;j0++)coutw[i0][j0];}}//根据父节点返回路径并输出路径voidshuchu(nodea){Nodesolutionlist[100];nodeb=a-next;intu=0;while(b){u=u+1;copyArray(solutionlist[u].array,b-array);b=b-parent;}for(inti=u;i=1;i--){print(solutionlist[i].array,2,2);coutendl;coutendl;}}intmain(){inta[3][3];inti;intj;inti0;intj0;inttop=1;//输入数据coutinputthedata:endl;for(i=0;i=2;i++){for(j=0;j=2;j++)cina[i][j];coutendl;}//设置目标结点intgoalNode[3][3]={{1,2,3},{8,0,4},{7,6,5}};intd[3][3];//空格往上下左右移动之后的数组intarr1[3][3],arr2[3][3],arr3[3][3],arr4[3][3];noder;InitNode(r);nodel;InitNode(l);Nodea0;copyArray(a0.array,a);a0.level=0;//计算初始点的估计函数值a0.quanzhi=computeF(a0.array,goalNode);a0.parent=NULL;a0.next=NULL;InsertNode(l,1,a0);//入链表staticinth=1;while(compare1(l-next-array,goalNode)!=1)//当前结点与目标结点不一致时进行while循环{nodeaa=l-next;Nodebb=*aa;InsertNode(r,h,bb);h++;intm,m0;copyArray(d,aa-array);copyArray(arr1,aa-array);copyArray(arr2,aa-array);copyArray(arr3,aa-array);copyArray(arr4,aa-array);//找出当前点的空格位置for(i=0;i=2;i++){for(j=0;j=2;j++){if(d[i][j]==0){i0=i;j0=j;break;}}}//分别考虑空格往上下左右移动的情况if(i0-1=0)//向左移动{arr1[i0][j0]=arr1[i0-1][j0];arr1[i0-1][j0]=0;Nodenode;copyArray(node.array,arr1);node.parent=aa;node.level=(aa-level)+1;node.quanzhi=computeF(node.array,goalNode);node.next=NULL;if(!isfind(l,node)){if(!isfind(r,node)){m=Locate(l,node);InsertNode(l,m,node);}else{inty=findAndGetLevel(r,node);if(node.levely){m0=Locate(l,node);InsertNode(l,m0,node);}}}else{intx=findAndGetLevel(l,node);if(x=node.level){}else{intk=findAndGetIndex(l,node);Del