人工智能-八数码游戏问题

实验:八数码游戏问题(a)初始状态(a)初始状态图(b)目标状态八数码游戏一、八数码游戏问题简介九宫排字问题(乂称八数码问题)是人工智能当中有名的难题之一。问题是在3X3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。(a)初始状态(a)初始状态(b)目标状态二、实验目的.熟悉人工智能系统中的问题求解过程；.熟悉状态空间的盲目搜索和启发式搜索算法的应用；.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验的思路八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如:图1八数码问题示意图数码结构体数码结构体typedefstnictnode(intfonn[N][N];intevalue;intudirec;右stmctnode"parent;}Graph;Graph*Qu[MAX];〃队歹ljGraph*St[MAX];〃堆栈.启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。.搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；f、跳到步骤2；四、数据结构的设计//八数码结构体〃数码组〃评估值，差距〃所屏蔽方向，防止往回推到上一状态,1上2下3左4〃父节点起始五、实验过程及代码#mclude<stdio.h>} 〃设计了搜索深度范闱，防止队列内存越界#include<stdlib.h>#include<tiine.h>defineN3〃数码组大小defineMax_Step50〃最大搜索深度defineMAX50typedefstinctnode//八数码结构体(intform[N][N];〃数码组intevahie〃评估值intudirect;〃所屏蔽方向，防止往回推到上已状态，1上2下3左4右strnctnode*parent;〃父节点}Graph;Giaph*Qu[MAX];//队歹ijGiaph*St[MAX];〃堆栈〃/〃〃〃打印数码组voidPrint(Graph*The_graph)(mtij;if(The_giaph=NULL)printf(“图为空\n");else(pnntfC 3)for(i=0;i<N;i++)(prin—for(j=0;j<N;j++)(piintf("％d\t\The_graph->form国Ij]);〃遍历打印}pniitf(n\t|\nH);}pniitf(n|\t\t\t差距:％d\t|\n,The_graph->evalue);//差距显示pnntfC 3)/〃/〃/〃评价函数mtEvaluate(Graph*The_gi-aph,Graph*End_graph)(intvalute=O;//差E巨数mtij;fbr(i=O;i<N;i-H-)(for(j=0;j<N;j++)(if(The_graph->fbi-m[i]|j]!=End_gi-apli->fonn[i][j])(valute++;))}The_giaph->evalue=xralute;returnvalute;}〃//〃/〃移动数码组Giaph*Move(Giaph*Tlie_gi-aph,mtDirect,intCreatNew_graph)(Graph*New_graph;mtHasGetBlank=O;〃是否获取空格位置intAbleMove=1是否可移动intfor(i=0;i<N;i++)〃获取空格坐标ij(for(j=0;j<N;j++)(if(The_graph->fbnn[i][j]=0)(HasGetBlaiik=l;break;))if(HasGetBlank=l)break;}〃printf("空格位S：%d,%d\nH,i,j);t_EU=J；〃移动空格switch(Direct)(case1://_Etj-sif(t_i<0)AbleMove=0;break;case2://Ft_i++;if(t_i>=N)AbleMove=0;break;case3://左if(tJ<0)AbleMove=0;break;case4:〃右tj++;if(tj>=N)AbleMove=0;break;)if(AbleMove==0)〃不能移动则返回原节点(returnThe_graph;}if(CreatNew_gi'aph=1)(New_graph=(Graph*)malloc(sizeof(Graph));//生成节点for(x=0;x<N;x-H-)(fdr(y=O;y<N;y-H-)(New_gi,aph->fbnn[x][y]=The_graph->fonn[x][y]y/fi制数码组))}elseNew_graph=Tlie_gi-aph;)〃移动后New_graph->fbmi[i][j]=New_gi-aph->fbnn[t_i][tj];New_graph->fdmi[t_i][tJ]=0;//pnntf("移动产生的新图M");〃Print(New_graph);returnNew_graph;)///〃〃〃搜索函数Gi-aph*Search(Graph*Begm,Graph*End){Graph*gl,*g2,*g;intStep=O〃深度intDirect=O;〃方向inti;intfront,rear;fiont=i-eai--l-J/队列初始化g=NULL;rear++;〃入队Qu[rear]=Begin;while(rear!=fi*ont)〃队列不空{fh)nt++；//出队gl=Qu[front];//printf("开始第％d个图M:fixmt);//Pimt(gl);for(i=1;iv=4;i++)〃分别从四个方向推导出新子节点(Direct=i;if(Du-ect=g1-Xidirect)〃跳过屏蔽方向continue;g2=Move(gl,Direct,1)；〃移动数码组if(g2!=gl)〃数码组是否可以移动(〃可以移动Evahiate(g2,End);〃评价新的节点〃prmtf("开始产生的第％d个图//Piiiit(g2);if(g2->evalue<=gl->evalue+1)〃是优越节点g2->pai-ent=gl;〃移动空格switch(Direct)〃设置屏蔽方向，防止往回推(case1://Jtg2->udii'ect=2;break;case2:〃下g2->udii'ect=l;break;case3:〃左g2->udiiect=4;break;case4:〃右g2->udii'ect=3;break;)rear4-+;Qu[rear]=g2;〃存储节点到待处理队列if(g2->evalue==0)〃为0则搜索完成(g=g2；//i=5;break;)}else{fiee(g2);//抛弃劣质节点g2=NULL;})}if(g!=NULL)〃为0则搜索完成(if(g->evalue==O)break;Step++〃统计深度if(Step>Max_Step)(break;}}retunig;}mtmam(mtargc,constchar*argv口)(//insertcodehere...GraphBegm_graph={{{2,8,3},{1,6,4},{7,0,5}},0ANULL)；/*9GraphBegm_graph={{{2,8,3},{l,0,4},{7,6,5}},0ANULL)；GraphBegm_graph={{{2,0,l},{4,6,5},{3,7,8}},0ANULL)；*/〃目标数码组GraphEnd_graph={{{1,2,3},{8,O,4},{7,6,5}},OANULL)；Evaluate(&Begin_gi,aph,&End_graph);〃对初始的数码组评价pnntf("初始数码组:\n”)；Pnnt(&Begm_graph);pnntf("目标数码组:\n”)；Pnnt(&End_graph);Graph*G?*P:inttop=-l;〃图搜索G=Search(&Begm_graph,&End_graph);〃打印if(G){〃把路径倒序P=G;〃压栈while(P!=NULL)(top++;St[top]=P;P=P->parent;)pnntf(yvvvvvvvvvvvvvv搜索结^»»»»»»»»\iiH);〃弹栈打印while(top>-l)(P=St[top];top--;Prmt(P);)pniitf(,,<««««««««^Mc»»»>»»»»»>\iin);}else{prmtf("搜索不到结果，深度为％d'uV,Max_Step);〃设计搜索深度范围主要是防止队列内存越界)retiim0;六、实验结果C-O227863860fi3803721721717071f86137342.345差距：4342.345313453434□差距：eex