人工智能(A星算法)

.1/11A*算法实验报告实验目的1．熟悉和掌握启发式搜索的定义、估价函数和算法过程2.学会利用A*算法求解N数码难题3.理解求解流程和搜索顺序实验原理A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。实验条件1.WindowNT/xp/7及以上的操作系统2.内存在512M以上3.CPU在奔腾II以上实验内容1.分别以8数码和15数码为例实际求解A*算法2.画出A*算法求解框图3.分析估价函数对搜索算法的影响4.分析A*算法的特点实验分析1.A*算法基本步骤1）生成一个只包含开始节点n0的搜索图G，把n0放在一个叫OPEN的列表上。2）生成一个列表CLOSED，它的初始值为空。3）如果OPEN表为空，则失败退出。4）选择OPEN上的第一个节点，把它从OPEN中移入CLPSED，称该节点为n。5）如果n是目标节点，顺着G中，从n到n0的指针找到一条路径，获得解决方案，成功退出（该指针定义了一个搜索树，在第7步建立）。.2/116）扩展节点n，生成其后继结点集M，在G中，n的祖先不能在M中。在G中安置M的成员，使他们成为n的后继。7）从M的每一个不在G中的成员建立一个指向n的指针（例如，既不在OPEN中，也不在CLOSED中）。把M1的这些成员加到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止找到的到达m的最好路径通过n，就把它的指针指向n。对已在CLOSED中的M的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的最好路径指向它们的祖先。8）按递增f*值，重排OPEN（相同最小f*值可根据搜索树中的最深节点来解决）。9）返回第3步。在第7步中，如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低，就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果，但是可能需要指数级的计算代价。实验步骤算法流程图是目标节点是o开始读入棋局初始状态是否可解在open表中找到评价值最小的节点，作为当前结点初始状态加入open表扩展新状态，把不重复的新状态加入open表中当前结点从open表移除输出结果结束否o否o是o.3/11程序代码#includeiostream#includectime#includevectorusingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTANCE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//一个表和目的表的距离intdep;//t深度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;}.4/11returntrue;}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++).5/11for(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);.6/11flag=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){.7/11Swap(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);.8/11}}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;coutInputsource:endl;for(inti=0;iROW;i++)//输入初始的表for(intj=0;jCOL;j++){cinnumber;src.digit[i][j]=number;}src.index=0;src.dep=1;coutInputdestination:endl;//输入目的表for(intm=0;mROW;m++)for(intn=0;nCOL;n++){cinnumber;dest.digit[m][n]=number;}node_v.push_back(src);//在容器的尾部加一个数据.9/11coutSearch...endl;clock_tstart=clock();while(1){if(isEmptyOfOPEN()){coutCann'tsolvethisstatement!endl;return-1;}else{intloc;//thelocationoftheminimizenode最优节点的位置loc=GetMinNode();if(isEqual(loc,dest.digit)){vectorNoderstep_v;coutSource:endl;coutsrcendl;PrintSteps(loc,rstep_v);coutSuccessful!endl;coutUsing(clock()-start)/C