A*算法（三）：双向策略与类似算法

上一篇讲解了8方向A*算法的执行过程，本篇文章讲解双向A*算法。

目录

A算法（一）：4方向
A算法（二）：8方向
A算法（三）：双向策略与类似算法
A算法（四）：权值与混合型地图
A*算法（五）：在三维地图的可行性

思想与思路

“双向”策略其实在很多算法里都有使用过，主要是起到优化的作用。例如冒泡排序，单向冒泡排序每一趟都能确定一个元素的最终位置。如下图，冒泡排序会依次把8、7、6…放在最终位置。

使用双向策略，那么每一趟就能确定两个元素的最终位置。如下图，依次确定8和1、7和2、6和3…，当两个指针相遇时，排序就完成了。

类似地，A*算法也可以尝试双向策略。起点和终点同时探索，如下图，相遇时结束。

但是，所有A*算法的执行都有一个重要的条件，那就是必须事先知道终点的位置，如果不知道，那么A*算法就没有用武之地了。

类似算法

前面的文章讲过有一个和A*算法类似的算法——BFS，也就是广度优先遍历。在这里我们可以做一些比较。

1.两种算法都会一点一点向外扩张，BFS会以起点为圆心一层一层向外“盲目”扩张，而A*算法则以终点为导向进行“有目的”地扩张。

2.A*算法必须事先知道终点的位置，而BFS不需要，BFS一层一层向外扩张，发现了终点就停下来。

3.二者都可以使用双向策略，前提是事先知道终点的位置。

最后

本篇文章讲述了双向策略和类似的算法——BFS。下一篇文章我们来看看A*算法在混合型地图上该如何拓展。