文档介绍：A*算法实验报告实验目的1熟悉和掌握启发式搜索的定义、估价函数和算法过程学会利用A*算法求解N数码难题理解求解流程和搜索顺序实验原理A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的代价以及从节点n到达目标节点的代价。实验条件WindowNT/xp/7及以上的操作系统内存在512M以上CPU在奔腾II以上实验内容分别以8数码和15数码为例实际求解A*算法画出A*算法求解框图分析估价函数对搜索算法的影响分析A**算法基本步骤1) 生成一个只包含开始节点n。的搜索图G,把n°放在一个叫OPEI的列表上。2) 生成一个列表CLOSE,它的初始值为空。3) 如果OPE表为空,则失败退出。4) 选择OPE上的第一个节点,把它从OPE中移入CLPSEP称该节点为n。5) 如果n是目标节点,顺着G中,从n到no的指针找到一条路径,获得解决方案,成功退出(该指针定义了一个搜索树,在第7步建立)。6) 扩展节点n,生成其后继结点集M在G中,n的祖先不能在M中。在G中安置M勺成员,使他们成为n的后继。7) 从M勺每一个不在G中的成员建立一个指向n的指针(例如,既不在OPE中,也不在CLOSED)。把M的这些成员加到OPE中。对M勺每一个已在OPE中或CLOSE中的成员m如果到目前为止找到的到达m勺最好路径通过n,就把它的指针指向n。对已在CLOSE中的M勺每一个成员,重定向它在G中的每一个后继,以使它们顺着到目前为止发现的最好路径指向它们的祖先。8) 按递增f*值,重排OPEN相同最小f*值可根据搜索树中的最深节点来解决)。9) 返回第3步。在第7步中,如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低,就要重定向指向该节点的指针。已经在CLOSE中的节点子孙的重定向保存了后面的搜索结果,但是可能需要指数级的计算代价。实验步骤算法流程图程序代码#inelude<iostream>#include<ctime>#inelude<vector>usingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTANCE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;// 一个表和目的表的距离intdep;//t深度intindex;// 节点的位置}Node;Nodesrc,dest;//父节表目的表vector<Node>node_v;// 存储节点boolisEmptyOfOPEN()//open 表是否为空{for(inti=0;i<();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}判断这个最优的节boolisEqual(intindex,intdigit[][COL])//点是否和目的节点一样{for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++){if(node_v[index].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator«(ostream&os,Node&node){for(inti=0;i<ROW;i++){for(intj=0;j<COL;j++)os<<[i][j]<<'';os<<endl;}returnos;}输出每一输出每一步的voidPrintSteps(intindex,vector<Node>&rstep_v)〃个遍历的节点深度遍历{(node_v[index]);index=node_v[index].index;while(index!=0){(node_v[index]);index=node_v[index].index;}_for(inti=()-1;i>=0;i--)〃探索过程一cout<<"Step"<<()-i<<endl<<rstep_v[i]<<endl;}voidSwap(int&a,int&b){intt;t=a;a=b;b=t;voidAssign(Node&node,intindex){for(inti=0;i<ROW;i++)for(intj