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

重庆交通大学计算机与信息学院验证性实验报告班 级： 计软专业 2013级1班 学 号： 631306050112 姓 名： 向雨佳 实验项目名称： 状态空间搜索 8数码问题 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 2 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的理解和掌握状态空间搜索的策略。二、实验内容及要求在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件VC6.0四、设计方案 题目 8数码问题 设计的主要思路1.基本数据结构分析和实现结点状态我采用了structNode数据类型typedefstruct_Node intdigitROWCOL;intdist;/distancebetweenonestateandthedestination一个表和目的表的距离intdep;/thedepthofnode深度/Sothecommentfunction=dist+dep.估价函数值intindex;/pointtothelocationofparent父节点的位置Node;发生器函数定义的发生器函数由以下的四种操作组成：(1)将当前状态的空格上移Nodenode_up;Assign(node_up,index);/向上扩展的节点intdist_up=MAXDISTANCE;(2)将当前状态的空格下移Nodenode_down;Assign(node_down,index);/向下扩展的节点intdist_down=MAXDISTANCE;(3)将当前状态的空格左移Nodenode_left;Assign(node_left,index);/向左扩展的节点intdist_left=MAXDISTANCE;(4)将当前状态的空格右移Nodenode_right;Assign(node_right,index);/向右扩展的节点intdist_right=MAXDISTANCE;通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。.图的搜索策略经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。实验时,采用了广度(宽度)优先搜索来实现。宽度优先算法如下： 步1把初始结点S0放入OPEN表中步2若OPEN表为空，则搜索失败，问题无解步3取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n步4若目标结点Sg=N，则搜索成功，问题有解步5若N无子结点，则转步2步6扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步2 主要功能五、主要代码 #include#include#includeusingnamespacestd;constintROW=3;/行数constintCOL=3;/列数constintMAXDISTANCE=10000;/最多可以有的表的数目constintMAXNUM=10000;typedefstruct_NodeintdigitROWCOL;intdist;/distancebetweenonestateandthedestination一个表和目的表的距离intdep;/thedepthofnode深度/Sothecommentfunction=dist+dep.估价函数值intindex;/pointtothelocationofparent父节点的位置Node;Nodesrc,dest;/父节表目的表vectornode_v;/storethenodes存储节点boolisEmptyOfOPEN()/open表是否为空for(inti=0;inode_v.size();i+)if(node_vi.dist!=MAXNUM)returnfalse;returntrue;boolisEqual(intindex,intdigitCOL)/判断这个最优的节点是否和目的节点一样for(inti=0;iROW;i+)for(intj=0;jCOL;j+)if(node_vindex.digitij!=digitij)returnfalse;returntrue;ostream&operator(ostream&os,Node&node)for(inti=0;iROW;i+)for(intj=0;jCOL;j+)osnode.digitij;osendl;returnos;voidPrintSteps(intindex,vector&rstep_v)/输出每一个遍历的节点深度遍历rstep_v.push_back(node_vindex);index=node_vindex.index;while(index!=0)rstep_v.push_back(node_vindex);index=node_vindex.index;for(inti=rstep_v.size()-1;i=0;i-)/输出每一步的探索过程coutSteprstep_v.size()-iendlrstep_viendl;voidSwap(int&a,int&b)intt;t=a;a=b;b=t;voidAssign(Node&node,intindex)for(inti=0;iROW;i+)for(intj=0;jCOL;j+)node.digitij=node_vindex.digitij;intGetMinNode()/找到最小的节点的位置即最优节点intdist=MAXNUM;intloc;/thelocationofminimizenodefor(inti=0;inode_v.size();i+)if(node_vi.dist=MAXNUM)continue;elseif(node_vi.dist+node_vi.dep)dist)loc=i;dist=node_vi.dist+node_vi.dep;returnloc;boolisExpandable(Node&node)for(inti=0;inode_v.size();i+)if(isEqual(i,node.digit)returnfalse;returntrue;intDistance(Node&node,intdigitCOL)intdistance=0;boolflag=false;for(inti=0;iROW;i+)for(intj=0;jCOL;j+)for(intk=0;kROW;k+)for(intl=0;lCOL;l+)if(node.digitij=digitkl)distance+=abs(i-k)+abs(j-l);flag=true;if(isExpandable(node_right)dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.dist=dist_right;node_right.dep=node_vindex.dep+1;node_v.push_back(node_right);node_vindex.dist=MAXNUM;六、测试结果及说明上机试验时,，经多次程序调试，最后得一下结果。此结果所得节点（状态图）很多，可知宽度优先搜索的盲目性很大，当目标节点距离初始节点较远时，就会产生大量的无用节点，搜索效率低。但是，只要问题有解，用宽度优先搜索总可以找到它的解。七、实验体会人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算法。本实验采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性，这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。所以图4宽度优先搜索树及程序运行结果图5得到的节点（状态图）很多,而解路径为1-3-8-16-26，其它节点是没有用的节点，搜索效率很低。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。学到了不少知识。重庆交通大学计算机与信息学院验证性实验报告班 级： 计软专业 2013级1班 学 号： 631306050112 姓 名： 向雨佳 实验项目名称： 启发式搜索 A*算法 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 12 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的理解和掌握A*算法。二、实验内容及要求在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）三、实验设备及软件VC6.0四、设计方案 题目 A*算法 设计的主要思路（1）编制程序实现求解八数码问题A*算法，采用估价函数其中：d(n)是搜索树中节点n的深度；w(n)为节点n的数据库中错放的棋子个数；p(n)为节点n的数据库中的每个棋子与其目标位置之间的距离的总和。（2）分析上述（1）中的两种估价函数求解八数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。 主要功能八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。五、主要代码#includestdio.h#definenum3voidshow(intbeginnumnum)for(inti=0;inum;i+)for(intj=0;jnum;j+) printf(%d,beginij);printf(n);printf(n);voidexchange(intbeginnumnum,introw_one,intcolumn_one,introw_two,intcolumn_two)inttemp;temp=beginrow_twocolumn_twobeginrow_twocolumn_two=beginrow_onecolumn_one;beginrow_onecolumn_one=temp;intjudge(intbeginnumnum,intendnumnum)intcount=0; for(inti=0;inum;i+)for(intj=0;j=20)return0;ntnode; inttemp;for(intq=0;qjishu;q+) node=1; for(intw=0;wnum&node;w+) for(intr=0;rnum&node;r+)if(ji_shuqwr!=beginwr) node=0;if(node=1)return0;for(inti=0;inum;i+) for(intj=0;j0&biaoji!=0)exchange(begin,row-1,column,row,column);temp=judge(begin,end);if(temp=right)temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,2,row-1,column);if(temp_zhi=1)return1;exchange(begin,row-1,column,row,column);if(column0&biaoji!=1)exchange(begin,row,column-1,row,column);temp=judge(begin,end);if(temp=right)temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,3,row,column-if(temp_zhi=1)return1;exchange(begin,row,column-1,row,column); if(rownum-1&biaoji!=2)exchange(begin,row+1,column,row,column); temp=judge(begin,end); if(temp=right)temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,0,row+1,column);if(temp_zhi=1)return1;exchange(begin,row+1,column,row,column); if(columnnum-1&biaoji!=3)exchange(begin,row,column+1,row,column);temp=judge(begin,end); if(temp=right)temp_zhi=yidong(begin,end,temp,jishu+1,ji_shu,1,row,column+1);if(temp_zhi=1)return1;exchange(begin,ro