人工智能-八数码实验报告

昆明理工大学信息工程与自动化学院学生实验报告（2014——2015学年第一学期）课程名称：人工智能导论开课实验室：信自楼234室2014年9月30日年级、专业、班学号姓名成绩实验项目名称状态空间搜索实验—八数码问题求解指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a)初始状态(b)目标状态图1八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或A*算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。二、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法A*算法是一种常用的启发式搜索算法。在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为：f'(n)=g'(n)+h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n)=g(n)+h(n)其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。3.A*算法的步骤A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。A*算法的步骤如下：1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。四、程序框图五、实验结果及分析输入初始状态：283目标状态：123164804705765运行结果屏幕打印OPEN表与CLOSE表：OPENCLOSE1234023456012346701523468901572348910015762348111213015769234812131415015769113481213141516170157691124812131415161718190157691123481213141516171920015769112318812131415161719212201576911231841213141516171921222301576911231848121314151617192122242501576911231848231213141516171921222426015769112318482324发现26为目标节点搜索树：六、结论对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列。如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。因此，18.100832147651…72031847652..112831647053..112830147654..112831407655…80231847656…923018476510.1428316470511.142831647500…728310476519.1228371406521.1228314376522.1428314576020.118032147657…912308476510.1123418076513.1312384076511..910382476512.131238647058..121237840659..1012380476523..912378460524..812370468525.1212378465015.1431082476514.12013824765目标节点注释：每个方格中最上面两个数字分别为编号与启发值，下面九个数字为八数码。较粗的箭头为解路径可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否相同，相同则问题可解，应当能搜索到路径。否则无解。七、源程序及注释#includeiostream#includectime#includevectorusingnamespacestd;constintROW=3;constintCOL=3;constintMAXDISTANCE=10000;constintMAXNUM=10000;intabs(inta){if(a0)returna;elsereturn-a;}typedefstruct_Node{intdigit[ROW][COL];intdist;//距离intdep;//深度intindex;//索引值}Node;Nodesrc,dest;vectorNodenode_v;//储存节点boolisEmptyOfOPEN(){//判断Open表是否空for(inti=0;inode_v.size();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}boolisEqual(intindex,intdigit[][COL]){//判断节点是否与索引值指向的节点相同for(inti=0;iROW;i++)for(intj=0;jCOL;j++){if(node_v[index].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator(ostream&os,Node&node){for(inti=0;iROW;i++){for(intj=0;jCOL;j++)osnode.digit[i][j]'';osendl;}returnos;}voidPrintSteps(intindex,vectorNode&rstep_v){//输出步骤rstep_v.push_back(node_v[index]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;}for(inti=rstep_v.size()-1;i=0;i--)coutSteprstep_v.size()-iendlrstep_v[i]endl;}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.digit[i][j]=node_v[index].digit[i][j];}intGetMinNode(){//获取启发值最小的节点intdist=MAXNUM;intloc;//thelocationofminimizenodefor(inti=0;inode_v.size();i++){if(node_v[i].dist==MAXNUM)continue;elseif((node_v[i].dist+node_v[i].dep)dist){loc=i;dist=node_v[i].dist+node_v[i].dep;}}returnloc;}boolisExpandable(Node&node){//判断是否可扩展for(inti=0;inode_v.size();i++){if(isEqual(i,node.digit))returnfalse;}returntrue;}intDistance(Node&node,intdigit[][COL]){//计算距离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.digit[i][j]==digit[k][l]){distance+=abs(i-k)+abs(j-l);flag=true;break;}elseflag=false;}if(flag)break;}returndistance;}intMinDistance(inta,intb){//二者取小return(ab?a:b);}voidProcessNode(intindex){//展开节点intx,y;boolflag;for(inti=0;iROW;i++){for(intj=0;jCOL;j++){if(node_v[index].digit[i][j]==0){x=i;y=j;flag=true;break;}elseflag=false;}if(flag)break;}Nodenode_up;//上移操作Assign(node_up,index);intdist_up=MAXDISTANCE;if(x0){Swap(node_up.digit[x][y],node_up.digit[x-1][y]);if(isExpandable(node_up)){dist_up=Distance(node_up,dest.digit);node_up.index=index;node_up.dist=dist_up;node_up.dep=node_v[index].dep+1;node_v.push_back(node_up);}}Nodenode_down;//下移操作Assign(node_down,index);intdist_down=MAXDISTANCE;if(x2){Swap(node_down.di