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

西安郵電大学人工智能实验报告书（三）学院：自动化学院专业：智能科学与技术班级：智能1403姓名：刘忠强时间：2016-3-29一、实验目的1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的盲目搜索策略；3.掌握盲目收索算法，重点是宽度优先收索和深度优先收索。二、实验算法广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点开始逐层向下扩展，再第n层节点还没有完全搜索之前，不进如第n+1层节点。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排在后面。三、程序框图四、实验结果及分析初始状态：目标状态：283216164408705753五、源程序及注释#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.digit[x][y],node_down.digit[x+1][y]);if(isExpandable(node_down)){dist_down=Distance(node_down,dest.digit);node_down.index=index;node_down.dist=dist_down;node_down.dep=node_v[index].dep+1;node_v.push_back(node_down);}}Nodenode_left;//左移操作Assign(node_left,index);intdist_left=MAXDISTANCE;if(y0){Swap(node_left.digit[x][y],node_left.digit[x][y-1]);if(isExpandable(node_left)){dist_left=Distance(node_left,dest.digit);node_left.index=index;node_left.dist=dist_left;node_left.dep=node_v[index].dep+1;node_v.push_back(node_left);}}Nodenode_right;//右移操作Assign(node_right,index);intdist_right=MAXDISTANCE;if(y2){Swap(node_right.digit[x][y],node_right.digit[x][y+1]);if(isExpandable(node_right)){dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.dist=dist_right;node_right.dep=node_v[index].dep+1;node_v.push_back(node_right);}}node_v[index].dist=MAXNUM;}intmain(){intnumber;cout输入初始状态:endl;for(inti=0;iROW;i++)for(intj=0;jCOL;j++){cinnumber;src.digit[i][j]=number;}src.index=0;src.dep=1;cout输入目标状态endl;for(intm=0;mROW;m++)for(intn=0;nCOL;n++){cinnumber;dest.digit[m][n]=number;}node_v.push_back(src);while(1){if(isEmptyOfOPEN()){cout找不到解!endl;return-1;}else{intloc;//thelocationoftheminimizenodeloc=GetMinNode();if(isEqual(loc,dest.digit)){vectorNoderstep_v;cout初始状态：endl;coutsrcendl;PrintSteps(loc,rstep_v);cout成功!endl;break;}elseProcessNode(loc);}}return0;}六、实验心得：不得不说这次的实验内容真的好难，涉及到的算法很复杂也很抽象，但是这次实验确实让我的编程能力有了很大的提高，让我对人工智能技术有了更深一步的认识，在解决问题和算法设计方面也有了很大的提高。这次实验我花了好几天的时间去查找资料，阅读并消化，最后采用了深度优先算法解决了八数码难题。这次实验让我明白了一个问题一开始无论看起来有多么困难，只要你能花时间去研究就一定能找出解决问题的方法。