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

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

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

3、w Roman）。二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法启发函数设定 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。2、数据结构与算法设计数码结构体typedef struct node /八数码结构体int formNN; /

4、数码组int evalue; /评估值，差距int udirec; /所屏蔽方向,防止往回推到上一状态,1上2下3左4右struct node *parent; /父节点Graph;Graph *QuMAX;/队列Graph *StMAX;/堆栈搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）a、把初始数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。 e、判断压入队的子节点数码组（优越点）的评估值，为

5、零则表示搜索完成，退出搜索； f、跳到步骤2；四、程序框图起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是 五、实验结果及分析采用深度优先搜索方式 并简化搜索六、结论813204765 (2)103824765 (3)813024 （0）765813024765 (4)123804765 (5)013824765 (1)Open表 close表01 2 02 3 4 0 12 4 5 6 0 1 3 目标完成七、源程序及注释#include /设计了搜索深度范围，防止队列内

6、存越界#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);for(i=0;iN;i+)printf(|t);for

7、(j=0;jformij);/遍历打印printf(t|n);printf(|ttt差距:%dt|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;jformij!=End_graph-formij)valute+;The_graph-evalue=valute;returnvalute;/移动数码组Graph*Move(Graph*The_graph,intDirect,intCrea

8、tNew_graph)Graph*New_graph;/intHasGetBlank=0;/是否获取空格位置intAbleMove=1;/是否可移动inti,j,t_i,t_j,x,y;for(i=0;iN;i+)/获取空格坐标i,jfor(j=0;jformij=0)HasGetBlank=1;break;if(HasGetBlank=1)break;/printf(空格位置:%d,%dn,i,j);t_i=i;t_j=j;/移动空格switch(Direct)case1:/上t_i-;if(t_i=N)AbleMove=0;break;case3:/左t_j-;if(t_j=N)AbleM

9、ove=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-formt_it_j;New_graph-formt_it_j=0;/printf(移动产生的新图:n);/Print(New_graph);retu

10、rnNew_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,front);/Print(g1);for(i=1;iudirect)/跳过屏蔽方向continue;g2=Move(g1,Direct,1);/移

11、动数码组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-udirect=4;break;case4:/右g2-udirect=3;break;rear+;Qurear=g2;/存储节点到待处理队列if(g2

12、-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;/随机移动步数intDirect;inti,x,y;Graph*New_graph;New_graph=(Graph*)malloc(sizeof(Graph

13、);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_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(&End_graph);Graph*G,*P;inttop=-1;