八数码问题求解--实验报告

实验报告一、实验问题八数码问题求解二、实验软件VC6.0编程语言或其它编程语言三、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索和启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。四、实验数据及步骤（一、）实验内容八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。2831231484765765(a)初始状态(b)目标状态图1八数码问题示意图（二、）基本数据结构分析和实现1.结点状态我采用了structNode数据类型typedefstruct_Node{intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sothecommentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;2.发生器函数定义的发生器函数由以下的四种操作组成：(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数码问题的隐式图的生成问题。接下来就是搜索了。3.图的搜索策略经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。实验时,采用了广度(宽度)优先搜索来实现。（三、）广度(宽度)优先搜索原理1.状态空间盲目搜索——宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。图2、宽度优先搜索示意图2.宽度优先算法如下：步1把初始结点S0放入OPEN表中步2若OPEN表为空，则搜索失败，问题无解步3取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n步4若目标结点Sg=N，则搜索成功，问题有解步5若N无子结点，则转步2步6扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步23.宽度优先算法流程图CSBEDAIFHGJ把S放入OPEN表FangruOPEN是否为空表?失败起始是否图3、宽度优先算法流程图4．8数码难题用宽度优先搜索所生成的搜索树如图4。搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格）。图中有26个节点，也就是源程序运行结果。1So23456789101112131415161718192021把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针成功是否有任何后继节点为目标节点?否是2831047652032147652831640652831647502831647050832147652031847652830147652341807652831407652837146052301847652831457601230847650231847652837140652801437652081437562830641752831457062831607542223242526图4.八数码题宽度优先搜索树五、实验结果及分析上机试验时,，经多次程序调试，最后得一下结果。此结果所得节点（状态图）很多，可知宽度优先搜索的盲目性很大，当目标节点距离初始节点较远时，就会产生大量的无用节点，搜索效率低。但是，只要问题有解，用宽度优先搜索总可以找到它的解。830214765883204765123804765283714650283704615图5.程序运行结果六、结论人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算法。本实验采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性，这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。所以图4宽度优先搜索树及程序运行结果图5得到的节点（状态图）很多,而解路径为1-3-8-16-26，其它节点是没有用的节点，搜索效率很低。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。学到了不少知识。七、源程序及注释#includeiostream#includectime#includevectorusingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTANCE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sothecommentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;Nodesrc,dest;//父节表目的表vectorNodenode_v;//storethenodes存储节点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.digit[x][y],node_down.digit[x+1][y]);if(isExp