试验四：A星算法求解迷宫问题试验知识讲解

1、实验四：A星算法求解迷宫问题实验精品文档实验四：A*算法求解迷宫问题实验一、 实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*算法求解迷宫问题，理解求解流程和搜索顺序。二、实验内容迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示 点不可以走，点用(x, y)表示，寻找从某一个给定的起始单元格 出发，经由行相邻或列相邻的单元格(可以通过的)，最终可以到达 目标单元格的、所走过的单元格序列。在任一个单元格中，都只能 看到与它邻近的4个单元格(如果位于底边，则只有3个；位于4个 角上，则只有2个是否能通过)。A*算法是人工智能中的一种搜索算法，是一种启发式搜索算 法，它不

2、需遍历所有节点，只是利用包含问题启发式信息的评价函 数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优 解的方向。它的独特之处是检查最短路径中每个可能的节点时引入 了全局信息，对当前节点距终点的距离做出估计，并作为评价节点 处于最短路线上的可能性的度量。A*算法中引入了评估函数，评估函数为：f (n) =g (n) +h(n)收集于网络，如有侵权请联系管理员删除精品文档其中：n是搜索中遇到的任意状态。g(n)是从起始状态到n的代 价。h(n)是对n到目标状态代价的启发式估计。即评估函数 f ( n)是 从初始节点到达节点n处已经付出的代价与节点n到达目标节点的 接近程度估价值的总和。这

3、里我们定义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).实验结果: C:U

4、SERSCHA 0D E SKTOPXSUAN FAkADe bug7*exeRI 口 旦精品文档I X:USERSChAODESKTOPSUANFAADebug7.exe. 3 = I 口 输入:迷宫左边长，上边宽？例如：的N0 9 8从下一行开始输入迷宫信息：061006100610001Q BO001101 *111010 0 0 0 1 0 0 S 0 11目 0 0 fr 0 1 0 1 01 J 0 f 1 1 1 0 0 0 1 fi 1 1100000输入起点坐标T且标点坐标响如91 3ft 20119 8调用眸算法打印结果如下工。,，），35/八,5,535,63.4S,7）

5、，6 ,7,京共走了.步Press An9 key to continue实验源码：#include #include #include using namespace std;int direc42=0,1,-1,0,0,-1,1,0;enum Flag收集于网络，如有侵权请联系管理员删除精品文档(SEAL,OPEN,UNVISITED)；typedef struct node(typedef struct node(int _x,_y;int _G;int _H;int _F;struct node *pre;Queue_Node;typedef struct(Flag flag;Queu

6、e_Node *point;Seal;节点坐标(x,y)实际已开销G探测将开销H优先级_F=_G+_H前驱顶点收集于网络，如有侵权请联系管理员删除精品文档class A_Star(public:构造函数A_Star()(input();)-A_Star()(for(int i=1;i=_len;+i)(for(int j=1;j=_wid;+j)(if(_sealij.point!=NULL)(delete _sealij.point;)收集于网络，如有侵权请联系管理员删除精品文档for(i=0;i=_len;+i)(delete _seali;delete _mazei;delete _se

7、al;delete _maze;void input()(cout”输入：迷宫左边长，上边宽！例如：30 20_len_wid;_seal=new Seal*_len+1;_maze=new unsigned char*_len+1;for(int i=0;i=_len;+i)(_seali=new Seal_wid+1;_mazei=new unsigned char_wid+1;cout从下一行开始输入迷宫信息：endl;for( i=1;i=_len;+i)收集于网络，如有侵权请联系管理员删除精品文档(for(int j=1；j_mazeij;_sealij.flag=UNVISITED

8、;_sealij.point=NULL;cout”输入起点坐标，目标点坐标，例如:1 1 30 20_sx_sy_ex_ey;if(_maze_sx_sy=1|_maze_ex_ey=1|bound(_sx,_sy)=f alse|bound(_ex,_ey)=false)(cout不可能存在这样的情况！endl;return;cout调用A*算法打印结果如下：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_n

9、ode);_seal_sx_sy.flag=OPEN;_seal_sx_sy.point=p_node;while(!_open.empty()(p_node=_open.top();_open.pop();int x=p_node-_x;int y=p_node-_y;_sealxy.flag=SEAL;for(int i=0;i4;+i)收集于网络，如有侵权请联系管理员删除精品文档(int tx=x+direci0;int ty=y+direci1;if(bound(tx,ty)=false|_mazetxty=1|_sealtxty.flag=SEAL)(continue;if(_sea

10、ltxty.flag=UNVISITED)(if(tx=_ex&ty=_ey)(print(p_node);cout(tx,ty)endl;cout总共走了 :_F步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);elseQueue_Node *temp=_sealtxty.point;if(p_node-_G+1_G)temp-_G=p_node-_G+1;temp-pre=p_node;temp-_F=temp

11、-_G+temp-_H;收集于网络，如有侵权请联系管理员删除精品文档cout没有从(_sx,_sy(_ex,_ey)的路径pre);cout(_x,_y),;)bool bound(int x,int y)(return (x=1)&(y=1);)int get_H(int x,int y)(return ab(x-_ex)+ab(y-_ey);收集于网络，如有侵权请联系管理员删除精品文档)int ab(int i)(return i_Fn2-_F;);priority_queueQueue_Node *,vector,cmp_open;僚小堆(开放列表)int _len,_wid;迷宫左边长，上边宽int _sx,_sy,_ex,_ey;Seal *_seal;动态开辟封闭列表unsign