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

《人工智能导论状态空间搜索实验—八数码问题求解.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a)初始状态(b)目标状态图1八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或A*算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结

3、果进行分析总结，得出结论。实验报告内容格式要求：XXXXXXXXXXXX（中文：宋体，小四；英文：TimesNewRoman）。二、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法启发函数设定由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零，因此可以把数码不同的位置个数作为标志一个节点到目标节点距离远近的一个启

4、发性信息，利用这个信息来扩展节点的选择，减少搜索范围，提高搜索速度。2、数据结构与算法设计数码结构体typedefstructnode//八数码结构体{intform[N][N];//数码组intevalue;//评估值，差距intudirec;//所屏蔽方向,防止往回推到上一状态,1上2下3左4右structnode*parent;//父节点}Graph;Graph*Qu[MAX];//队列Graph*St[MAX];//堆栈搜索过程：（搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点））a、把初始

5、数码组压入队列；b、从队列中取出一个数码组节点；c、扩展子节点，即从上下左右四个方向移动空格，生成相应子节点：d、对子节点数码组作评估，是否为优越节点，即其评估值是否小于等于其父节点加一，是则将其压入队，否则抛弃。e、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；f、跳到步骤2；四、程序框图起始把s放入open表失败成功是否open表为空表？是把open表中的第一个节点n移入close表否扩展节点n，把其后裔放入open表的前头是否有后继节点为目标节点？否是五、实验结果及分析采用深度优先搜

6、索方式并简化搜索六、结论813204765(2)103824765(3)813024（0）765813024765(4)123804765(5)013824765(1)Open表close表0120234012456013目标完成七、源程序及注释#include   }//设计了搜索深度范围，防止队列内存越界#include   6、运行结果#include     #define N 3 //数码组大小  #define Max_Step 50 //最大搜索深度

7、  #define MAX 50    typedef struct node//八数码结构体  {      int form[N][N];//数码组      int evalue;//评估值      int udirect;//所屏蔽方向，防止往回推到上已状态，1上2下3左4右      struct node *parent;//父节点  /////////打印数码组  void Print(Graph *The_graph)  {      int i,j;      if(The_graph==NULL

8、)          printf("图为空");      else      {          printf("---------------------");          for(i=0;i

9、t");              for(j=