实验'A*算法求解迷宫问题实验时间：2021.03.09创作：欧阳法二、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解迷宫问题，理解求解
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
和搜索顺序。三、实验内容迷宫问题可以
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
述为：一个二维的网格，（）表示点可走，1表示点不可以走，点用（x,y）表示，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格（可以通过的），最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的4个单元格（如果位于底边，则只有3个；位于4个角上，则只有2个是否能通过）。A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需適历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。A*算法中引入了评估函数，评估函数为：f(a)=g(n)+h(n)其中：n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f(n)是从初始节点到达节点n处已经付出的代价与节点、n到达目标节点、的接近程度估价值的总和。这里我们定义n点到目标点的最小实际距离为h(n)*,A*算法要满足的条件为：h(n)v=h(n)*迷宫走的时候只能往上下左右走，每走一步，代价为1,这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：h(n)=|cnd.x-n.x|+|cnd.y-n.y|这里end表示迷宫的目标点，n表示当前点，很明显这里h(n)V二h(n)*。g(n)容易表示，即每走一步的代价是1,所以利用f(n)二g(n)+h(n)这种策略，我们可以不断地逼近目标点，从而找到问题的解。时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为实验结果：实验源码：#include
#include#includcusingnamespacestd;intdirec[4][2]={{0,l},{-1,0},{0,-1},{1,0}};enumFlag{SEAL,OPEN,UNVISITED}；t\-pcdefstructnode{int_x_y;int_G;Gint_H;Hint_F;_F二_G+_Hstructnode*prc;}Queuc_Node;typcdefstruct{Flagflag;Qucuc_Node*point;}Scal;classA_Star{publie://构造函数〃节点坐标(x,y)//实际已开销〃探测将开销//优先级//前驱顶点A_StarQinputO；}~A_StarO{for(inti=l;i<=_lcn;+4-i){for(intj=l;j<=_wid;+-+-j){if(_seal[i][j].point!=NULL){delete_seal[i][j].point;for(i=0;i<=」cri;++i){delete[|_seal[i];deleteQ_mazc[i];}delete[]_scal;delete[]_mazc;}voidinput。{cout«"输入：迷宫左边长，上边宽！例如:302()"«cndl;cin>>_lcn>>_wid;_scal=ncwSeal*[_len+1];_mazc=ncwunsignedchar*[_lcn+l];for(inti=();i<=_lcn;++i){_seal[i]=newScal[_wid+1];_mazc[i]=ncwunsignedchar[_wid+l];}cout«"从下一行开始输入迷宫信息:"«cndl;for(i=l;i<=_lcn;++i){for(intj=l;j<=_wid;++j)cin>>_mazc[i][j];_seal[i][j].flag=UN\nSITED;_scal[i][j].point=NULL;}}cout<<"输入起点坐标,目标点坐标，例如：113()20n«cndl;cin>>_sx>>_sy>>_ex>>_ey;if(_mazc[_sx][_sy]=='r||_ma2e[_ex][_ey]==,r||bound(_sx,_sy)==false||bound(_ex,_ey)==false){cout«"不可能存在这样的情况！"«cndl;return;}cout«"调用A*算法打印结果如下："«cndl;AQ；//A*核心算法voidA0{//源点放入开放列表Qucuc_Nodc*p_node=ncwQueue_Nodc;p_node->prc=NULL;p_node->_H=get_H(_sx,_sy);p_node->_G=0;p_node->_x=_sx;p_node->_y=_sv；p_node->_F=p_node->_H+p_node->_G;_opcn.push(p_nodc);_seal[_sx][_sy].flag=OPEN;_scal[_sx][_sy].point=p_node;whilc(!_opcn.empty-0){p_node=_opcn.top0;_opcn.pop();intx=p_node->_x;inty=p_nodc->_y;2021.03.09_scal[x]^].flag=SEAL;for(inti二();i<4;++i){inttx=x+direc[i][0];intty=y+direc[i][l];if(bound(tx,ty)==falsc||_mazc[tx][ty]==,r||_scal[tx][ty].flag==SEAL){continue;if(_seal[tx][ty].flag==UNVISITED){if(tx==_ex&&ty==_ey){print(p_nodc);cout«"(,,«tx«V«ty«，，)M«endl;cout<<''总共走了:H«p_node->_Fprc=p_node;tcmp->_G=p_node->_G+1;tcmp->_x=tx;tcmp->_y=ty;tcmp->_H=get_H(tx,ty);tcmp->_F=tcmp・>_G+temp->_H;_opcn.push(tcmp);}else{Qucuc_Nodc*temp=_seal[tx][ty|.point;if(p_node->_G+l_G){tcmp->_G=p_nodc->_G+1;tcmp->prc=p_node;tcmp->_F=tcmp->_G+tcmp->_H;}}}}cout«"没有Ak(n<<_sx«n,"<<_sy<"«7"«_cx«n,n«_ey«n)6勺路径”VV«idl;}//打印路径voidprint(Qucuc_Nodc*p){if(p二二NULL){return;}print(p->prc);cout«',(n«p->_x«,,,',«p->_y«n),n;}boolbound(intx,inty){return(xv=」n)&&(x>=1)&&(yv=_wid)&&(y>=1);}intgct_H(intx.inty){returnab(x-_ex)+ab(jr-_cy);}intab(inti){returni<0?-i:i;}private:structcmp{booloperatorO(Qucue_Nodc*nl,Queue_Node*n2){returnnl->_F>n2->_F;}}；priorit}T_queuc,cmp>_opcn;//最小堆(开放列表)int」cn,_wid;//迷宫左边长,上边宽int_sx,_sy^ex,_cy;Seal**_seal;//动态开辟封闭列表unsignedchar**_mazc;//迷宫地图}；intmain(){A_Startest;return0;四、实验目的通过这次实验，使我对启发式搜索算法有了更进一步的理解，特别是估计函数h(n)所起到的巨大重用。一个好的估计函数对于启发式搜索算法来说是十分关键的。时间：2021.03.09创作：欧阳法
浙公网安备 33021202002483