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

1、实验八数码游戏问题一、八数码游戏问题简介九宫排字问题(乂称八数码问题)是人工智能当中有名的难题之一。问题是在3X3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。(a)初始状态图(b)(a)初始状态图(b)目标状态八数码游戏二、实验目的.熟悉人工智能系统中的问题求解过程；.熟悉状态空间的盲目搜索和启发式搜索算法的应用;.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验的思路八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

2、例如:图1八数码问题示意图数码结构体数码结构体typedefstnictnode(intfonnNN;intevalue;intudirec;右stmctnodeparent;Graph;Giaph*QuMAX;队歹ljGraph*StMAX;堆栈.启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。.搜索过程：（搜索采用广度搜索方式，利用待处理队列

3、辅助，逐层搜索（跳过劣质节点）a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；f、跳到步骤2；四、数据结构的设计/八数码结构体数码组评估值，差距所屏蔽方向，防止往回推到上一状态,1上2下3左4父节点起始)五、实验过程及代码#mclude设计了搜索深度范围，防止队列内存越界#include#includedefineN3数码组大小defineMa

4、x_Step50最大搜索深度defineMAX50typedefstinctnode/八数码结构体intformNN;数码组intevahie;/评估值intudirect;所屏蔽方向，防止往回推到上已状态，1上2下3左4右stiuctnode*parent;父节点Graph;Graph*QuMAX;/队歹ijGi-aph*StMAX;堆栈/打印数码组voidPrint(Graph*The_graph)mtij;if(The_gi-aph=NULL)pnntf(”图为空n)elsepnntffnM);for(i=0;iN;i+)(pmitf(n|tH);for(j=0;jfbrmij);遍历打

5、印pinitfC,t|nn);pniitf(n|ttt差距:%dt|ir：The_graph-evahie);/差距显示pnntffnM);/评价函数mtEvaluate(Graph*The_giaph,Graph*End_graph)intTalute=O;/差E巨数mtij;fbr(i=O;iN;i-H-)for(j=0;jfbmii|j!=End_giaph-fonnij)(valute+;The_giaph-evalue=xralute;returnvalute;/移动数码组Graph*Move(Graph*Tlie_giaph,mtDirect,intCreatNew_graph)G

6、raph*New_graph;intHasGetBlank=O;是否获取空格位置intAbleMove=1;是否可移动intfor(i=0;iN;i+)获取空格坐标ijfor(j=0;jfbimij=0)(HasGetBlaiik=l;break;if(HasGetBlank=l)break;prin氓”空格位置:%d,%dn”,i,j);t户U=J；移动空格switch(Direct)case1:/_Etj-sif(t_i=N)AbleMove=0;break;case3:/左if(U=N)AbleMove=0;break;if(AbleMove=0)不能移动则返回原节点returnThe_

7、graph;)if(CreatNew_gi,aph=1)New_graph=(Graph*)malloc(sizeof(Graph);/生成节点for(x=0;xN;x+)(fbr(yO;yfbnnxy=The_graph-fomixy;/目制数码组)elseNew_graph=The_graph;移动后New_graph-fdmiij=New_gi-aph-fbnnt_itj;New_graph-fbnnt_it_j=O;/pnntf(移动产生的新图:n);/Print(New_graph);retiimNew_graph;/搜索函数Graph*Search(GraphBegin,Graph

8、*End)Graph*gl,*g2,*g;intStep=O;深度intDirect=O;方向inti;intfront,rear;fiont=i-eai-l-Jf队列初始化g=NULL;reai+;入队Qurear=Begin;while(rear!=fixmt)队列不空fhmHT;出队gl=Qufront;“printf(开始第d个图ont);/Pimt(gl);for(i=1;iv=4;i+)分别从四个方向推导出新子节点(Duect=i;if(Du-ect=g1-udirect)跳过屏蔽方向contmue;g2=Move(gl,Direct,1)；移动数码组if(g2!=gl)数码组是否

9、可以移动(可以移动Evahiate(g2,End);评价新的节点pnntf(开始产生的第d个图:/Print(g2);if(g2-evalueevalue+1)是优越节点g2-parent=gl;移动空格switch(Direct)设置屏蔽方向，防止往回推(case1:/Jtg2-udirect=2;break;case2:下g2-udu,ect=l;break;case3:左g2-udkect=4;break;case4:右g2-udirect=3;break;)rear4-+;Qurear=g2;存储节点到待处理队列if(g2-evalue=0)为0则搜索完成(g=g2；/i=5;brea

10、k;)else(丘ee(g2);抛弃劣质节点g2=NULL;)if(g!=NULL)为0则搜索完成(if(g-evalue=O)break;Step+;统计深度if(StepMax_Step)break;retiinig;mtmam(mtargc?constchar*argv口)/insertcodehere.GraphBegm_graph=2,8,3,1,6,4,7,0,5,0,0,NULL)；/*IGraphBegm_graph=2,8,3,1,0,4,7,6,5,0,0,NULL)；GraphBegm_graph=2,0,1,4,6,5,3,7,8,0,0,NULL)；*/目标数码组Gr

11、aphEnd_graph=1,2,3,8,0,4,7,6,5,0,0,NULL)；Evaluate(&Begin_gi,aph,&End_graph);/对初始的数码组评价pnntf(初始数码组:n”)；Pnnt(&Begm_graph);pnntf(目标数码组An)；Pnnt(&End_giaph);Graph*G,*P:inttop=-l;图搜索G=Search(&Begm_graph,&End_graph);打印if(G)把路径倒序P=G;压栈while(P!=NULL)(top+;Sttop=P;P=P-parent;pnntf(yv-l)(P=Sttop;top-;Prmt(P);pniitf(nin);elseprmtf(搜索不到结果，深度为dW,Max_Step);设计搜索深度范围主要是防止队列内存越界)retiim0;六、实验结果Cancer./桌面$gcc/I数码.码c:l:21：