搜索
实验四：A*算法求解迷宫问题实验1、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解迷宫问题，理解求解流程和搜索顺序。2、实验内容迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示点不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格(可以通过的)，最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的4个单元格(如果位于底边，则只有3个；位于4个角上，则只有2个是否能通过)。A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n）其中：n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f(n)是从初始节点到达节点n处已经付出的代价与节点n到达目标节点的接近程度估价值的总和。这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为：h（n）=h（n）*迷宫走的时候只能往上下左右走，每走一步，代价为1，这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：h（n）=|end.x–n.x|+|end.y–n.y|这里end表示迷宫的目标点，n表示当前点，很明显这里h（n）=h（n）*。g（n）容易表示，即每走一步的代价是1，所以利用f（n）=g（n）+h（n）这种策略，我们可以不断地逼近目标点，从而找到问题的解。时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n).实验结果：实验源码：#includequeue#includevector#includeiostreamusingnamespacestd;intdirec[4][2]={{0,1},{-1,0},{0,-1},{1,0}};enumFlag{SEAL,OPEN,UNVISITED};typedefstructnode{int_x,_y;//节点坐标(x,y)int_G;//实际已开销Gint_H;//探测将开销Hint_F;//优先级_F=_G+_Hstructnode*pre;//前驱顶点}Queue_Node;typedefstruct{Flagflag;Queue_Node*point;}Seal;classA_Star{public://构造函数A_Star(){input();}~A_Star(){for(inti=1;i=_len;++i){for(intj=1;j=_wid;++j){if(_seal[i][j].point!=NULL){delete_seal[i][j].point;}}}for(i=0;i=_len;++i){delete[]_seal[i];delete[]_maze[i];}delete[]_seal;delete[]_maze;}voidinput(){cout输入:迷宫左边长,上边宽!例如：3020endl;cin_len_wid;_seal=newSeal*[_len+1];_maze=newunsignedchar*[_len+1];for(inti=0;i=_len;++i){_seal[i]=newSeal[_wid+1];_maze[i]=newunsignedchar[_wid+1];}cout从下一行开始输入迷宫信息：endl;for(i=1;i=_len;++i){for(intj=1;j=_wid;++j){cin_maze[i][j];_seal[i][j].flag=UNVISITED;_seal[i][j].point=NULL;}}cout输入起点坐标,目标点坐标,例如:113020endl;cin_sx_sy_ex_ey;if(_maze[_sx][_sy]=='1'||_maze[_ex][_ey]=='1'||bound(_sx,_sy)==false||bound(_ex,_ey)==false){cout不可能存在这样的情况！endl;return;}cout调用A*算法打印结果如下：endl;A();}//A*核心算法voidA(){//源点放入开放列表Queue_Node*p_node=newQueue_Node;p_node-pre=NULL;p_node-_H=get_H(_sx,_sy);p_node-_G=0;p_node-_x=_sx;p_node-_y=_sy;p_node-_F=p_node-_H+p_node-_G;_open.push(p_node);_seal[_sx][_sy].flag=OPEN;_seal[_sx][_sy].point=p_node;while(!_open.empty()){p_node=_open.top();_open.pop();intx=p_node-_x;inty=p_node-_y;_seal[x][y].flag=SEAL;for(inti=0;i4;++i){inttx=x+direc[i][0];intty=y+direc[i][1];if(bound(tx,ty)==false||_maze[tx][ty]=='1'||_seal[tx][ty].flag==SEAL){continue;}if(_seal[tx][ty].flag==UNVISITED){if(tx==_ex&&ty==_ey){print(p_node);cout(tx,ty)endl;cout总共走了:p_node-_F步endl;return;}Queue_Node*temp=newQueue_Node;_seal[tx][ty].flag=OPEN;_seal[tx][ty].point=temp;temp-pre=p_node;temp-_G=p_node-_G+1;temp-_x=tx;temp-_y=ty;temp-_H=get_H(tx,ty);temp-_F=temp-_G+temp-_H;_open.push(temp);}else{Queue_Node*temp=_seal[tx][ty].point;if(p_node-_G+1temp-_G){temp-_G=p_node-_G+1;temp-pre=p_node;temp-_F=temp-_G+temp-_H;}}}}cout没有从(_sx,_sy)---(_ex,_ey)的路径endl;}//打印路径voidprint(Queue_Node*p){if(p==NULL){return;}print(p-pre);cout(p-_x,p-_y),;}boolbound(intx,inty){return(x=_len)&&(x=1)&&(y=_wid)&&(y=1);}intget_H(intx,inty){returnab(x-_ex)+ab(y-_ey);}intab(inti){returni0?-i:i;}private:structcmp{booloperator()(Queue_Node*n1,Queue_Node*n2){returnn1-_Fn2-_F;}};priority_queueQueue_Node*,vectorQueue_Node*,cmp_open;//最小堆(开放列表)int_len,_wid;//迷宫左边长,上边宽int_sx,_sy,_ex,_ey;Seal**_seal;//动态开辟封闭列表unsignedchar**_maze;//迷宫地图};intmain(){A_Startest;return0;}3、实验目的通过这次实验，使我对启发式搜索算法有了更进一步的理解，特别是估计函数h(n)所起到的巨大重用。一个好的估计函数对于启发式搜索算法来说是十分关键的。