631306050107侯甚男+启发式搜索+状态空间搜索.doc

重庆交通大学计算机与信息学院验证性实验报告班 级： 计软 专业 13 级 1 班 学 号： 631306050107 姓 名： 侯甚男 实验项目名称： 启发式搜索 A*算法 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 9 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的1、 理解和掌握A*算法2、 掌握人工智能系统中问题的求解过程二、实验内容及要求1、实验内容：在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。2、实验要求：用选定的编程语言编写程序，利用策略函数判断搜索和A*算法实现状态空间搜索策略。三、实验设备及软件笔记本，Microsoft Visual Studio 2010四、设计方案（一）题目在33方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。解八数码的问题如果按正常的思维，采用盲目搜索的话，如上面实验的宽度优先搜索和深度优先搜索，不仅搜索的次数多，而且往往容易陷入死循环中，所以面对此问题需要一种策略启发式搜索。（二）启发式搜索策略1、A*算法A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为： f(x)=d(x)+w(x), 其中f(x) 是节点x从初始点到目标点的估价函数，d(x) 是在状态空间中从初始节点到n节点的实际代价，w(x是从x到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值w(x)实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。其中是当前被考察和扩展的结点在搜索图中的节点深度，是节点与目标状态结点相比较，错位的数字个数。一般来说，某结点的越大，说明它离目标节点越远。2、主要代码的设计定义goal数组为目标状态1,2,3,8,0,4,7,6,5。结构体Chessboard记录棋盘信息，其中变量pos数组坐标记录每个数码a的位置，其值为数码a。d表示该棋盘的深度，f为启发函数值，move为父节点移动到该节点的方式，以便在输出时告诉用户该如何移动棋子知道目标状态。2）struct LNode：定义节点LNode结构体，存放该节点状态时的棋盘信息board，和指向父节点、下一节点的指针(*parent,*next)，以及标记量flag值为true时表示该节点是最佳路径上的节点。3）int* Findzero(LNode* &Node)：为方便找到空格，我设计了找到该函数Findzero(*&Node)，以便找到当前节点空格所在位置以利于接下来的程序执行。返回值为空格所在的行和列。4）int Wrong(LNode *Node)和int pick(LNode *Node)：分别为函数和。5）LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数还是。6）void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)分别为表OPEN、CLOSE的创建和表的插入操作。7）LNode* Getminf(List &L)主要是实现从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点。5、 主要代码#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/记录0的位置，zero0:r行；zero1:c列 typedef int Piece;struct Chessboard/棋盘信息 Piece posNN;/记录每个数码a的位置r行c列int d,f,move;/d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;break;return z;int Wrong(LNode *Node)int w=0,i,j;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)w+;return w;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);break; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1:/向左移，不能出界：zero1=2New-Node-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2New-Node-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=NewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+Wrong(NewNode);break; case 2:NewNode-board.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;void InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(List &L)List p=L,q=L-next,r=L,min;min=q;/p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 数 码 问 题 求 解n); printf(n请输入初始状态：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盘状态：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close); printf(请选择(1:A算法;2:A*算法):); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+Wrong(Start);break; case 2:Start-board.f=Start-board.d+pick(Start);break; /Start-board.f=0+Wrong(Start);Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/将S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best);if(!(Best-board.f-Best-board.d)printf($*有解！*$n); break;z=Findzero(Best);zero0=*(z+0);zero1=*(z+1);if(zero1=N-1&Best-board.move!=2)ListInsert(Open,extend(Best,Best-board.d,zero,1,choose);if(zero1board.move!=1)ListInsert(Open,extend(Best,Best-board.d,zero,2,choose);if(zero0=N-1&Best-board.move!=4)ListInsert(Open,extend(Best,Best-board.d,zero,3,choose);if(zero0board.move!=3)ListInsert(Open,extend(Best,Best-board.d,zero,4,choose);printf(本算法搜索图中总共扩展的节点数为：%dn,NodeQTY); printf(t最佳路径如下所示：n); if(Open-next)while(Best-parent)Best-flag=1;Best=Best-parent;List p=Close-next,q=Close-next;if(p=Start) q=p-next;else exit(1);int Step=0; while(p&q)/在Close表中依标记找到路径 if(q-flag=1&q-parent=p)printf(Step %d:0 move as the %d-flag of movement.n,+Step,q-board.move);for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);p=q;/记住父节点 q=q-next;printf(到达目标状态！n); elseprintf(该问题无法求解！n);六、实验体会通过本次验证性实验，了解学习了A*算法，获益匪浅。重庆交通大学计算机与信息学院验证性实验报告班 级： 计软 专业 13 级 1 班 学 号： 631306050107 姓 名： 侯甚男 实验项目名称： 状态空间搜索（8数码问题） 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 8 日评阅意见：实验成绩： 签名： 年 月 日一、 实验目的1、 理解和掌握状态空间搜索的策略二、 实验内容及要求1、实验内容：在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。2、实验要求：用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、 实验设备及软件电脑，Eclipse四、设计方案1、宽度优先算法 1、把根节点放到队列的末尾。 2、每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。 3、找到所要找的元素时结束程序。 4、如果遍历整个树还没有找到，结束程序。2、深度优先算法1、把根节点压入栈中。2、每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。3、找到所要找的元素时结束程序。4、如果遍历整个树还没有找到，结束程序。五、主要代码#include stdafx.h#include iostream#include #include #include #include static int target9 = 1, 2, 3, 8, 0, 4, 7, 6, 5 ;/class definitionclass eight_numprivate:int num9;int not_in_position_num;int deapth;int eva_function;public:eight_num* parent;eight_num* leaf_next;eight_num* leaf_pre;eight_num(int init_num9);eight_num(int num1, int num2, int num3, int num4, int num5, int num6, int num7, int num8, int num9)num0 = num1;num1 = num2;num2 = num3;num3 = num4;num4 = num5;num5 = num6;num6 = num7;num7 = num8;num8 = num9;eight_num(void)for (int i = 0; i9; i+)numi = i;void cul_para(void);void get_numbers_to(int other_num9);int get_nipn(void)return not_in_position_num;int get_deapth(void)return deapth;int get_evafun(void)return eva_function;void set_num(int other_num9);void show(void);eight_num& operator=(eight_num&);eight_num& operator=(int other_num9);int operator=(eight_num&);int operator=(int other_num9);/计算启发函数g(n)的值void eight_num:cul_para(void)int i;int temp_nipn = 0;for (i = 0; iparent = NULL)deapth = 0;elsedeapth = this-parent-deapth + 1;eva_function = not_in_position_num + deapth;/构造函数1eight_num:eight_num(int init_num9)for (int i = 0; i9; i+)numi = init_numi;/显示当前节点的状态void eight_num:show()using std:cout;cout num0;cout ;cout num1;cout ;cout num2;cout n;cout num3;cout ;cout num4;cout ;cout num5;cout n;cout num6;cout ;cout num7;cout ;cout num8;cout n;/复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)for (int i = 0; i9; i+)other_numi = numi;/设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)for (int i = 0; i9; i+)numi = other_numi;eight_num& eight_num:operator=(eight_num& another_8num)for (int i = 0; i9; i+)numi = another_8num.numi;not_in_position_num = another_8num.not_in_position_num;deapth = another_8num.deapth + 1;eva_function = not_in_position_num + deapth;return *this;eight_num& eight_num:operator=(int other_num9)for (int i = 0; i9; i+)numi = other_numi;return *this;int eight_num:operator=(eight_num& another_8num)int match = 1;for (int i = 0; i9; i+)if (numi != another_8num.numi)match = 0;break;if (match = 0)return 0;elsereturn 1;int eight_num:operator=(int other_num9)int match = 1;for (int i = 0; i9; i+)if (numi != other_numi)match = 0;break;if (match = 0)return 0;elsereturn 1;/空格向上移int move_up(int num9)int i;for (i = 0; i 9; i+)if (numi = 0)break;if (i3)return 0;elsenumi = numi - 3;numi - 3 = 0;return 1;/空格向下移int move_down(int num9)int i;for (i = 0; i5)return 0;elsenumi = numi + 3;numi + 3 = 0;return 1;/空格向左移int move_left(int num9)int i;for (i = 0; i 9; i+)if (numi = 0)break;if (i = 0 | i = 3 | i = 6)return 0;elsenumi = numi - 1;numi - 1 = 0;return 1;/空格向右移int move_right(int num9)int i;for (i = 0; i 9; i+)if (numi = 0)break;if (i = 2 | i = 5 | i = 8)return 0;elsenumi = numi + 1;numi + 1 = 0;return 1;/判断可否解出int icansolve(int num9, int target9)int i, j;int count_num = 0, count_target = 0;for (i = 0; i9; i+)for (j = 0; ji; j+)if (numjnumi & numj != 0)count_num+;if (targetjparent)if (*p = num)return 1;return 0;/寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start)eight_num *p, *OK;p = OK = start;int min = start-get_evafun();for (p = start; p != NULL; p = p-leaf_next)if (minp-get_evafun()OK = p;min = p-get_evafun();return OK;int main(void)using std:cout;using std:cin;double time;clock_t Start, Finish;int memery_used = 0, step = 0;int num9;int flag = 0;/是否输入错误标志，1表示输入错误int bingo = 0;/是否查找成功标志，1表示成功int i, j;cout 请输入数据（0代表空位）：n;for (i = 0; i numi;for (j = 0; ji; j+)if (numi = numj)flag = 1;if (numi8 | flag = 1)i-;cout 存在非法数据，请重新输入：n;eight_num S(num), Target(target);S.parent = S.leaf_next = S.leaf_pre = NULL;S.cul_para();memery_used+;cout 初始数据为：n;S.show();cout 目标结果为：n;Target.show();if (!icansolve(num, target)cout leaf_pre;OK_leaf-get_numbers_to(num);if (move_up(num) & !existed(num, OK_leaf)new_8num = new eight_num;new_8num-set_num(num);new_8num-parent = OK_leaf;new_8num-cul_para();new_8num-leaf_pre = p;if (p = NULL)leaf_start = new_8num;elsep-leaf_next = new_8num;p = new_8num;memery_used+;OK_leaf-get_numbers_to(num);if (move_down(num) & !existed(num, OK_leaf)new_8num = new eight_num;new_8num-s