频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
关于A*寻路算法的认识
2015-04-21 08:54:09      个评论      
收藏   我要投稿
那么关于这两者之间的关系是怎么样呢?

 

个人理解的是A*算法其实是一种带有路径信息的有策略的广度优先搜索,我们平常用的广度优先搜索,没有带有路径信息,搜索起来是一种盲目的搜索。

 

例如,当寻路到A节点时,下一步是以A为中心,分别测试A周围的8个点,并且又以它们为中心,继续向外扩散,以期找到待寻找的点。

 

这样的搜索带有盲目性,测试了大量的无效的点。

 

 

 

A*算法在每个节点中加入了路径的信息:

 

F:当前点的路径信息,包含了到当前点到起点与到终点的信息。(F=G+H)

 

G:当前点到唯一的起点的路径信息。

 

H:当前点到指定终点的距离信息。

 

 

 

那么我们怎么样通过这些指定的路径信息来避免广度优先搜索的盲目选取下一个路径点而得到一条最小路径呢? 

 

其实我们可以把这看成是一个最小路径的“感染”问题。

 

F B C D

 

E A G H

 

I  N K L

 

如上图:

 

首先参照上文博客,水平方向移动一格路径代价是10,斜方向移动一格路径代价是14。

 

起点A的G值初始化0,这个当然,自己到自己的距离是0;其它点中的G初始化为INT_MAX;通过对A的广度搜索,来设置各个节点的G值与父节点。

 

例:A的八个方向,FBCEGINK,选取出F最小的点,假设为G。

 

     对G的八个方向,BCDAHNKL,我们同样需要设定这8个方向的G值与父节点。这8个方向中与A重叠的有BCNK。

 

     重叠意味着有两条路径,对于K来说,可以是A->K,也可以是A->G->K。

 

那么怎么样选择呢?

 

这时我们要判断G的值,哪条路径使得G的值最小,我们就选择它。

 

G的值是起点A到本节点的路径长度,这是一个累积的值,是前面各个G一路累积(感染)下来的,代表的是当前的路径,我们选择的肯定是使得K的G最小,这样对整个最小路径都是有利的,因为可以一直感染下去。

 

那么H的作用在哪里呢?

 

H仅仅是对路径方向的一个大致的判断,上图中,若指定终点在A的右边,那么EFI肯定不会被选中,这样就不用盲目的8个方向都去判断。

 

 

 

终上所述:

 

G和H的作用共同体现于F中,每次我们都是在广度搜索中去寻找F最小的点,然后根据G的值,设置下一个广度搜索中的节点的父节点,父节点永远是使得子节点中的G值最小。(到起点A的路径最短)。

 

 

 

自己写的A*的核心函数代码,测试curr节点的周围8个节点,并且设置路径及父节点信息,其余的部分则是广度优先搜索的框架,这里不再写出来。

 

 

 1 void getSurrroundPoints(point& curr, list<point>& result)
 2 {
 3     int x = curr.m_x;                              //curr坐标信息
 4     int y = curr.m_y;
 5     
 6     for (int i = x-1;i <= x+1; i++)
 7     {
 8         for (int j = y - 1; j <= y + 1; j++)       //8个方向
 9         {
10             if (i == x && j == y)                  //循环到自己,跳过此次循环
11                 continue;
12 
13             if ( find_if(closeList.begin(), closeList.end(), pointEqualLocation(i, j)) == closeList.end()  //当前节点还没有被检查过
14                 &&canReach(i, j))                                                                          //当前节点不是障碍物
15             {            
16                 if (x == i || y == j)      //上下左右四个方向 g=10
17                 {
18                     if ((curr.m_g + 10) >= point_ptr[i][j].m_g)
19                     {
20                                           //start到(i,j)的 不必经过curr 
21                                           //什么也不做,保留原来的路径信息与父节点
22                     }
23                     else
24                     {                    //start到(i,j)的 经过curr路径会更小 
25                                          //更新路径信息 更改父节点
26                         point_ptr[i][j].m_g = curr.m_g + 10;      //更新节点中的G值
27                         point_ptr[i][j].m_fx = curr.m_x;          //设置父节点
28                         point_ptr[i][j].m_fy = curr.m_y;
29 
30                     }
31                 }
32                 else                     //斜方向 g=14;
33                 {
34                     if ((curr.m_g + 14) >= point_ptr[i][j].m_g)
35                     {
36                                         //start到(i,j)的 不必经过curr 
37                                         //什么也不做,保留原来的路径信息与父节点
38                     }
39                     else
40                     {                    //start到(i,j)的 经过curr路径会更小 
41                                           //更新路径信息 更改父节点
42                         point_ptr[i][j].m_g = curr.m_g + 14;    //更新节点中的G值
43                         point_ptr[i][j].m_fx = curr.m_x;        //设置父节点
44                         point_ptr[i][j].m_fy = curr.m_y;
45 
46                     }
47                 }
48                 point_ptr[i][j].m_h = abs(endPoint_x - i) + abs(endPoint_y - j);  //计算到终点的距离
49                 point_ptr[i][j].m_f = point_ptr[i][j].m_g + point_ptr[i][j].m_h;  //F=G+H
50 
51                 result.push_back(point_ptr[i][j]);                  //放到链表中 等待下次的检查
52             }
53         }
54     }
55 }

 


点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:单链表的算法
下一篇:模式串匹配--KMP算法
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站