人工智能-八数码游戏

实验一：八数码游戏问题一、八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。2831231648475765（a）初始状态（b）目标状态图八数码游戏二、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验的思路八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a)初始状态(b)目标状态图1八数码问题示意图1.启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。2.搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；f、跳到步骤2；四、数据结构的设计数码结构体typedefstructnode//八数码结构体{intform[N][N];//数码组intevalue;//评估值，差距intudirec;//所屏蔽方向,防止往回推到上一状态,1上2下3左4右structnode*parent;//父节点}Graph;Graph*Qu[MAX];//队列Graph*St[MAX];//堆栈起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是五、实验过程及代码#includestdio.h}//设计了搜索深度范围，防止队列内存越界#includestdlib.h#includetime.h#defineN3//数码组大小#defineMax_Step50//最大搜索深度#defineMAX50typedefstructnode//八数码结构体{intform[N][N];//数码组intevalue;//评估值intudirect;//所屏蔽方向，防止往回推到上已状态，1上2下3左4右structnode*parent;//父节点}Graph;Graph*Qu[MAX];//队列Graph*St[MAX];//堆栈/////////打印数码组voidPrint(Graph*The_graph){inti,j;if(The_graph==NULL)printf(图为空\n);else{printf(---------------------\n);for(i=0;iN;i++){printf(|\t);for(j=0;jN;j++){printf(%d\t,The_graph-form[i][j]);//遍历打印}printf(\t|\n);}printf(|\t\t\t差距:%d\t|\n,The_graph-evalue);//差距显示printf(---------------------\n);}}/////////评价函数intEvaluate(Graph*The_graph,Graph*End_graph){intvalute=0;//差距数inti,j;for(i=0;iN;i++){for(j=0;jN;j++){if(The_graph-form[i][j]!=End_graph-form[i][j]){valute++;}}}The_graph-evalue=valute;returnvalute;}/////////移动数码组Graph*Move(Graph*The_graph,intDirect,intCreatNew_graph){Graph*New_graph;intHasGetBlank=0;//是否获取空格位置intAbleMove=1;//是否可移动inti,j,t_i,t_j,x,y;for(i=0;iN;i++)//获取空格坐标i,j{for(j=0;jN;j++){if(The_graph-form[i][j]==0){HasGetBlank=1;break;}}if(HasGetBlank==1)break;}//printf(空格位置:%d,%d\n,i,j);t_i=i;t_j=j;//移动空格switch(Direct){case1://上t_i--;if(t_i0)AbleMove=0;break;case2://下t_i++;if(t_i=N)AbleMove=0;break;case3://左t_j--;if(t_j0)AbleMove=0;break;case4://右t_j++;if(t_j=N)AbleMove=0;break;}if(AbleMove==0)//不能移动则返回原节点{returnThe_graph;}if(CreatNew_graph==1){New_graph=(Graph*)malloc(sizeof(Graph));//生成节点for(x=0;xN;x++){for(y=0;yN;y++){New_graph-form[x][y]=The_graph-form[x][y];//复制数码组}}}else{New_graph=The_graph;}//移动后New_graph-form[i][j]=New_graph-form[t_i][t_j];New_graph-form[t_i][t_j]=0;//printf(移动产生的新图:\n);//Print(New_graph);returnNew_graph;}/////////搜索函数Graph*Search(Graph*Begin,Graph*End){Graph*g1,*g2,*g;intStep=0;//深度intDirect=0;//方向inti;intfront,rear;front=rear=-1;//队列初始化g=NULL;rear++;//入队Qu[rear]=Begin;while(rear!=front)//队列不空{front++;//出队g1=Qu[front];//printf(开始第%d个图:\n,front);//Print(g1);for(i=1;i=4;i++)//分别从四个方向推导出新子节点{Direct=i;if(Direct==g1-udirect)//跳过屏蔽方向continue;g2=Move(g1,Direct,1);//移动数码组if(g2!=g1)//数码组是否可以移动{//可以移动Evaluate(g2,End);//评价新的节点//printf(开始产生的第%d个图:\n,i);//Print(g2);if(g2-evalue=g1-evalue+1){//是优越节点g2-parent=g1;//移动空格switch(Direct)//设置屏蔽方向，防止往回推{case1://上g2-udirect=2;break;case2://下g2-udirect=1;break;case3://左g2-udirect=4;break;case4://右g2-udirect=3;break;}rear++;Qu[rear]=g2;//存储节点到待处理队列if(g2-evalue==0)//为0则搜索完成{g=g2;//i=5;break;}}else{free(g2);//抛弃劣质节点g2=NULL;}}}if(g!=NULL)//为0则搜索完成{if(g-evalue==0){break;}}Step++;//统计深度if(StepMax_Step){break;}}returng;}intmain(intargc,constchar*argv[]){//insertcodehere...GraphBegin_graph={{{2,8,3},{1,6,4},{7,0,5}},0,0,NULL};/*GraphBegin_graph={{{2,8,3},{1,0,4},{7,6,5}},0,0,NULL};GraphBegin_graph={{{2,0,1},{4,6,5},{3,7,8}},0,0,NULL};*///目标数码组GraphEnd_graph={{{1,2,3},{8,0,4},{7,6,5}},0,0,NULL};Evaluate(&Begin_graph,&End_graph);//对初始的数码组评价printf(初始数码组:\n);Print(&Begin_graph);printf(目标数码组:\n);Print(&End_graph);Graph*G,*P;inttop=-1;//图搜索G=Search(&Begin_graph,&End_graph);//打印if(G){//把路径倒序P=G;//压栈while(P!=NULL){top++;St[top]=P;P=P-parent;}printf(搜索结果\n);//弹栈打印while(top-1){P=St[top];top--;Print(P);}printf(完成\n);}else{printf(搜索不到结果，深度为%d\n,Max_Step);//设计搜索深度范围主要是防止队列内存越界}return0;}六、实验结果