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

重庆交通大学计算机与信息学院
验证性实验报告
班级: 计软专业 2013级1班
学号: 631306050112
姓名: 向雨佳
实验项目名称: 状态空间搜索 8数码问题
实验项目性质: 验证性实验
实验所属课程: 人工智能
实验室(中心):软件中心实验室(语音楼8楼)
指导教师: 朱振国
实验完成时间: 2016 年 6 月 2 日
评阅意见:
实验成绩: 签名: 年月日
一、实验目的
理解和掌握状态空间搜索的策略。
二、实验内容及要求
在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里,现在要求实验这个问题:将该九宫格调整为某种有序的形式。调整的规则是,每次只能将与空格(上、下、左、右)相邻的一个数字平移到空格中。
用选定的编程语言编写程序,利用不同的搜索策略进行状态空间搜索(如宽度优先搜索、深度优先搜索、有界深度优先搜索等)。
三、实验设备及软件

四、设计方案
㈠题目
8数码问题
㈡设计的主要思路
 
①结点状态  
我采用了struct Node数据类型
 typedef struct _Node{
int digit[ROW][COL];
int dist;  // distance between one state and the destination一个表和目的表的距离
int dep;   // the depth of node深度
// So ment function = dist +  
 int index; // point to the location of parent父节点的位置 } 
Node;
②发生器函数
定义的发生器函数由以下的四种操作组成: 
 (1)将当前状态的空格上移
Node node_up;
Assign(node_up, index);//向上扩展的节点 
int dist_up = MAXDISTANCE;  
 (2)将当前状态的空格下移  Node 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;
通过定义结点状态和发生器函数,就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。
③.图的搜索策略
经过分析,8数码问题中可采用的搜速策略共有:、、、、,一共五种。其中,广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。
实验时,采用了广度(宽度)优先搜索来实现。
宽度优先算法如下:  
  步1 把初始结点S0放入OPEN表中  
       步2 若OPEN表为空,则搜索失败,问题无解  
       步3 取OPEN表中最前面的结点N放在CLOSE表中,并冠以顺序编
号n  
       步4 若目标结点Sg=N,则搜索成功,问题有解
步5 若N无子结点,则转步2  
       步6 扩展结点N,将其所有子结点配上指向N的放回指针,依次放入OPEN表的尾部,转步2  
㈢主要功能
五、主要代码
#include <iostream>
 #include <ctime> 
#include <vector> using namespace std;  
const int ROW = 3;//行数 
const int COL = 3;//列数 
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