赞
踩
上一篇文章讲解了A*算法的最简版本,不了解的朋友可以先看看4方向的A*算法的全过程,再来看本篇文章。
A算法(一):4方向
A算法(二):8方向
A算法(三):双向策略与类似算法
A算法(四):权值与混合型地图
A*算法(五):在三维地图的可行性
在讲解8方向A*算法前,我们需要想想这个“最小代价”是指什么。
第一种情况,如下图,如果离开A到周围的8个方格的代价均是1,那么从起点到终点的“最小代价”就是指最少需要走几步。
第二种情况,如下图,如果斜着走的代价是√2,那么从起点到终点的“最小代价”就是指最小距离长度。
和上一篇一样,我们给每个方格定义变量A、B、C
A指初始位置到当前方格的最小代价
B指当前方格到终点的估计代价
C指A + B的值
但和4方向A*算法不同的是,8方向允许斜着计算B,例如下图。
(0,4)的B = 3, (1,2)的B = 3
了解这一点不同后,我们来看看它的全过程。先计算起点周围方格的A、B、C,如下图。
此时访问C值最小且没访问过的方格,也就是(2,1)和(1,2),并计算它们的相邻点的A,B,C值。如下图。
重复上一步的操作,访问C值最小且没访问过的方格,也就是(0,2)、(1,3),并计算它们的相邻点的A,B,C值。如下图。
重复上一步的操作,访问C值最小且没访问过的方格,也就是(0,1)、(1,0)、(0,3)、(3,2),并计算它们的相邻点的A,B,C值。如下图。
重复上一步的操作,访问C值最小且没访问过的方格,也就是(3,3)、(4,3),并计算它们的相邻点的A,B,C值。如下图。
重复上一步的操作,访问C值最小且没访问过的方格,也就是(4,4),并计算它的相邻点的A,B,C值。如下图。
此时,终点的A = 5、B = 0、C = A + B = 5,也就是说起点到终点的最小步数为5。接着再从终点的位置往起点搜索,沿途访问C值最小的相邻方格便能引出最短路径。可以看到最短路径不止一条,如下图。
A还是指初始位置到当前方格的最小代价
B还是指当前方格到终点的估计代价
C还是指A + B的值
只不过现在斜着走算√2,例如下图。
(1,1)的B = 2√2 + 2,(0,1)的B = 3√2 + 1。
但为了计算方便,这里把√2 近似等于 1.4。于是(1,1)的B = 2.8 + 2 = 4.8,(0,1)的B = 4.2 + 1 = 5.2。
了解这一点不同后,我们来看看它的全过程。先计算起点周围方格的A、B、C,如下图。
终于找到终点了。同样地,从终点向起点回溯。于是最短距离长度为6.2。
本篇文章分别从基于步数和基于距离长度讲述了8方向A*算法的执行过程。下一篇讲述双向策略以及类似的算法。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。