631306050112向雨佳+状态空间搜索+启发式搜索

《631306050112向雨佳+状态空间搜索+启发式搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重庆交通大学计算机与信息学院验证性实验报告班级：计软专业2013级1班学号：631306050112姓名：向雨佳实验项目名称：状态空间搜索8数码问题实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间：2016年6月2日评阅意见：实验成绩：签名：年月日一、实验目的理解和掌握状态空间搜索的策略。二、实验内容及要求在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上

2、、下、左、右）相邻的一个数字平移到空格中。用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件VC6.0四、设计方案㈠题目8数码问题㈡设计的主要思路1.基本数据结构分析和实现 ①结点状态  我采用了struct Node数据类型 typedef struct _Node{int digit[ROW][COL];int dist;  // distance between one state and the destination一个表和目的表的距离in

3、t dep;   // the depth of node深度// So the comment function = dist + dep.估价函数值  int index; // point to the location of parent父节点的位置 } Node;②发生器函数定义的发生器函数由以下的四种操作组成：  (1)将当前状态的空格上移Node node_up;Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE;   (2)将当前状态的空格下移  N

4、ode node_down;Assign(node_down, index);//向下扩展的节点  int dist_down = MAXDISTANCE;  (3)将当前状态的空格左移Node node_left;Assign(node_left, index);//向左扩展的节点  int dist_left = MAXDISTANCE;  (4)将当前状态的空格右移Node node_right;Assign(node_right, index);//向右扩展的节点  int dist_right = MAXDISTANCE

5、;通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。③.图的搜索策略经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。实验时,采用了广度(宽度)优先搜索来实现。宽度优先算法如下：   步1 把初始结点S0放入OPEN表中         步2 若OPEN表为空，则搜索失败，问题无解         

6、步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n         步4 若目标结点Sg=N，则搜索成功，问题有解步5 若N无子结点，则转步2         步6 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步2  ㈢主要功能五、主要代码#include  #include  #include  using namespace std;  const int ROW = 3;//行数 const int COL = 3;//列数

7、 const int MAXDISTANCE = 10000;//最多可以有的表的数目 const int MAXNUM = 10000;  typedef struct _Node{  int digit[ROW][COL];  int dist;  // distance between one state and the destination一个表和目的表的距离  int dep;   // the depth of node深度 // So the comment function = dist + dep.估价函数值 

8、 int index; // point to the location of parent父节点的位置 } Node;  Node src, dest;// 父节表 目的表  vector node_v;  // store the