631306050102周桐 状态空间搜索 启发式搜索.doc

重庆交通大学计算机与信息学院验 证性实验报告班级: 软件开发专业 13级1班学号: 631306050102 姓名: 周桐实验项目名称: 状态空间搜索 8 数码问题实验项目性质: 验证性实验实验所属课程: 人工智能实验室( 中心): 软件中心实验室(语音楼 8 楼) 指导教师: 朱振国实验完成时间: 2016 年6月6日一、实验目的理解和掌握状态空间搜索的策略。二、实验内容及要求(一) 实验内容在一个 3*3 的九宫中有 1-8 个数码及一个空格随即的摆放在其中的格子里,现在要求实验这个问题:将该九宫格调整为某种有序的形式。调整的规则是,每次只能将与空格(上、下、左、右)相邻的一个数字平移到空格中。(二) 实验要求用选定的编程语言编写程序,利用不同的搜索策略进行状态空间搜索(如宽度优先搜索、深度优先搜索、有界深度优先搜索等)。三、实验设备及软件计算机一台、 Microsoft Visual 2015 C++ 四、设计方案(一)题目状态空间搜索 8数码问题(二)设计的主要思路输入要排序的 1~8 数码序列建立一个队列,将初始结点入队,并设置队列头和尾指取出队列头(头指针所指)的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列判断扩展出的新结点与队列中的结点是否重复。否的话,记录其父结点,并将它加入队列,更新队列尾指针,队列头的结点可以扩展,直接返回第二步。评阅意见: 实验成绩:签名:年月日否则将队列头指针指向下一结点,再返回第二步。是的话,队列头的结点可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。判断扩展出的结点是否是目标结点, 是的话,就显示路径;否的话,就转到上一步。最后程序结束。(三)主要功能交换空格( 0)位置,直至到达目标位置为止。五、主要代码#include <> #include <> #include <> #include <queue> #include <stack> using namespace std; #define HashTableSize 362881 #define NOT ! #define UP0 #define DOWN 1#define LEFT 2#define RIGHT 3#define Bit char typedef struct maps { Bit detail[9]; int myindex;// 记录自己节点在 hash 表中的位置 Bit position;// 记录空格( 0)在序列中的位置}Map,*PMap; ; //初始状态 int EndIndex; //上移,下移,左移,右移 int const derection[4] ={-3,3,-1,1 } //可移动的四个方向 int const Factorial[9] ={40320,5040,720,120,24,6,2,1,1}; int HashTable[HashTableSize]={0}; //hash 表,其中记录的是上一个父节点对应的位置/**** 八数码的输入(在这里不做任何输入检查,均认为输入数据是正确的) ***/ void input() {int i,j; int sum ,count ,index for(i =0;i<9;i++) {scanf("%1d", &[ i]); [ i]||( =i) }for(i =0;i<9;i++)// 计算逆序{if( 0==[ i]) continue; for(j =0;j<i;j++) sum +=(0!=[j]&&[j]<[i]); } for( i=0;index =0i<9;i++) //计算初始状态的 hash 值{ for(j =0,count =0;j<i;j++) count +=[ j]>[ i]index +=Facto rial[ [ i]]*count; } =index +1 EndIndex =sum%2 ?161328:322561; //目标状态的 hash 值 return; }/***hash 值的计算*Parent: 父状态的 hash 值*direct: 移动的方向**/ inline int HashValue(Map& Parent ,int& direct ){ int i= int newindex = Bit *p=P