人工智能导论：状态空间搜索实验-八数码问题求解解读

1、昆明理工大学信息工程与自动化学院学生实验报告20142015学年第一学期）年级、专业、班姓名成绩实验项目名称状态空间搜索实验一八数码问题求解指导教师胡蓉课程名称：人工智能导论开课实验室：该同学是否了解实验原理:A.了解口C.不了解口年月日教师评语该同学的实验能力：该同学的实验是否达到要求：实验报告是否规范：实验过程是否详细记录：A.强口A.达到口A.规范口A.详细口B.基本了解口B.中等口C.差口B.基本达到口B.基本规范口B.一般口C.未达到C.不规范C.没有口教师签名：年月一、实验内容和要求八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要

2、求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：图1八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或A*算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。实验报告内容格式要求：XXXXXXXXXXXX（中文：宋体，小四；英文：TimesNewRoman）。二、实验目的熟悉人工智能系统中的问题求解过程；熟悉状态空间的盲目搜索和启发式搜索算法的应用熟悉对八数码问题

3、的建模、求解及编程语言的应用。三、实验算法启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。2、数据结构与算法设计数码结构体typedefstructnodeintformNN;intevalue;intudirec;右/八数码结构体/数码组/评估值，差距/所屏蔽方向,防止往回推到上一状态,1上2下3左4structnode*parent;/父节点

4、Graph;Graph*QuMAX;队列Graph*StMAX;堆栈搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）a、把初始数码组压入队列;b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点:d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成,退出搜索；f、跳到步骤2；四、程序框图五、实验结果及分析采用深度优先搜索方式并简化搜索六、结论Open表close表01120234012456013目标完成七、

5、源程序及注释#include/设计了搜索深度范围，防止队列内存越界#include6、运行结果#include#defineN3/数码组大小#defineMax_Step50/最大搜索深度#defineMAX50typedefstructnode/八数码结构体intformNN;/数码组intevalue;/评估值intudirect;/所屏蔽方向，防止往回推到上已状态，1上2下3左4右structnode*parent;/父节点/打印数码组voidPrint(Graph*The_graph)inti,j;if(The_graph=NULL)prinTF(“图为空n);elseprintF(n

6、);for(i=0;iN;i+)printF(|t);for(j=0;jFormij);/遍历打印printF(t|n);printf=-vtvtvtBsMd/t-=Thegraphevalue)j、s知Iprint-h=n=)j一二一二一二看倉irrtEvaluate(G-5aph*Thelg-5aphJG-5aph宀IIirrtva1uteH、吊齊inrbijj-hor(iH0ji人Nji+)宀For(jHj人N-j+)宀i-h-Thelg-saphv-ho-smLij二HEndlg-saphv-ho-smLij)宀IIvalute+jThegraphvevalueuvalutejretu

7、rnvalute-二二二二一聲善庐Graph*Move(GraphDirectiirtc-seatNewIg-saph)宀IIGraph*舄产里3|3|1-、inrhHasGetBlankH0j、nMm朋姦artIrrtAb1eMoveH1j、淞审列炒inrbijjjtijtjjxjyj-hor(iH0ji人Nji+)、m朋姦妝圖Tj宀For(jHj人N-j+)宀i-h(Thegraph-hormi二jTH0)宀IHasGetBlankuljbreak-if(HasGetBlank=1)break;/printf(空格位置：d,%dn,i,j);t_i=i;t_j=j;/移动空格switch(

8、Direct)case1：/上t_i-;if(t_i=N)AbleMove=0;break;case3：/左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;yformxy=The_graph-formxy;/复制数码组elseNew_graph=The_graph;/移动后New_graph-formij=New_graph-fo

9、rmt_it_j;New_graph-formt_it_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+;/入队Qurear=Begin;while(rear!=front)/队列不空front+;/出队g1=Qufront;/printf(开始第d个图：n,fr

10、ont);/Print(g1);for(i=1;iudirect)/跳过屏蔽方向continue;g2=Move(g1,Direct,1);/移动数码组if(g2!=g1)/数码组是否可以移动/可以移动Evaluate(g2,End);/评价新的节点/printf(开始产生的第d个图：n,i);/Print(g2);if(g2-evalueevalue+1)/是优越节点g2-parent=g1;/移动空格switch(Direct)/设置屏蔽方向，防止往回推case1：/上g2-udirect=2;break;case2：/下g2-udirect=1;break;case3：/左g2-udir

11、ect=4;break;case4：/右g2-udirect=3;break;rear+;Qurear=g2;/存储节点到待处理队列if(g2-evalue=0)/为0则搜索完成g=g2;/i=5;break;elsefree(g2);/抛弃劣质节点g2=NULL;if(g!=NULL)/为0则搜索完成if(g-evalue=0)break;Step+;/统计深度if(StepMax_Step)break;returng;/初始化一个八数码结构体Graph*CR_BeginGraph(Graph*The_graph)srand(unsigned)time(0);intM=10;/随机移动步数i

12、ntDirect;inti,x,y;Graph*New_graph;New_graph=(Graph*)malloc(sizeof(Graph);for(x=0;xN;x+)for(y=0;yformxy=The_graph-formxy;for(i=0;ievalue=0;New_graph-udirect=0;New_graph-parent=NULL;returnNew_graph;intmain(intargc,constchar*argv)/insertcodehere./*GraphBegin_graph=2,8,3,1,6,4,0,7,5,0,0,NULL;GraphBegin_

13、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;/初始数码组Graph*Begin_graph;Begin_graph=CR_BeginGraph(&End_graph);/随机产生初始数码组Evaluate(Begin_graph,&End_graph);/对初始的数码组评价printf(”初始数码组：n”)；Print(Begin_graph);printf(目标数码组：n);Print(

14、&End_graph);Graph*G,*P;inttop=-1;/图搜索G=Search(Begin_graph,&End_graph);/打印if(G)/把路径倒序P=G;/压栈while(P!=NULL)top+;Sttop=P;P=P-parent;printf(n);/弹栈打印while(top-1)P=Sttop;top-;Print(P);printf(n);elseprintf(”搜索不到结果，深度为dn,Max_Step);/设计搜索深度范围主要是防止队列内存越界return0;读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟。3、读书破万卷，下笔如有神。20、读书给人以快乐、给人以光彩、给人以才干。培根达尔文4、我所学到的任何有价值的知识都是由自学中得来的。5、少壮不努力，老大徒悲伤。6、黑发不知勤学早，白首方悔读书迟。颜真卿7、宝剑锋从磨砺岀，梅花香自苦寒来。8、读书要三到：心到、眼到、口到9