19
A*搜寻算法的高效之处
如上，是不是对 A*、Dijkstra、双向 BFS 算法各自的性能有了个总体大概的印象列?由
上述演示，我们可以看出，在最短路径搜寻效率上，一般有 A*>Dijkstra、双向 BFS，其中
Dijkstra、双向 BFS 到底哪个算法更优，还得看具体情况。
由上，我们也可以看出，A*搜寻算法的确是一种比较高效的寻路算法。
A*算法最为核心的过程，就在每次选择下一个当前搜索点时，是从所有已探知的但未
搜索过点中(可能是不同层，亦可不在同一条支路上)，选取 f 值最小的结点进行展开。
而所有“已探知的但未搜索过点”可以通过一个按 f 值升序的队列(即优先队列)进行排
列。
这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队
首元素（f 值），对其可能子结点计算 g、h 和 f 值，直到优先队列为空(无解)或找到终止点
为止。
A*算法与广度、深度优先和 Dijkstra 算法的联系就在于：当 g(n)=0 时，该算法类似于
DFS，当 h(n)=0 时，该算法类似于 BFS。且同时，如果 h(n)为 0，只需求出 g(n)，即求出起
点到任意顶点 n 的最短路径，则转化为单源最短路径问题，即 Dijkstra 算法。这一点，可以
通过上面的 A*搜索树的具体过程中将 h(n)设为 0 或将 g(n)设为 0 而得到。
BFS、DFS 与 A*搜寻算法的比较
参考了算法驿站上的部分内容：
不管以下论述哪一种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一
个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜
索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。
我们用两张表来进行搜索，一个叫 OPEN 表，表示那些已经展开但还没有访问的结点
集，另一个叫 CLOSE 表，表示那些已经访问的结点集。
蛮力搜索（BFS，DFS）
BFS（Breadth-First-Search 宽度优先搜索）
首先将起始结点放入 OPEN 表，CLOSE 表置空，算法开始时：
1、如果 OPEN 表不为空，从表中开始取一个结点 S，如果为空算法失败
2、S 是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到 3
3、将 S 的所有后继结点展开，就是从 S 可以直接关联的结点（子结点），如果不在 CLOSE
表中，就将它们放入 OPEN 表末尾，而把 S 放入 CLOSE 表，重复算法到 1。
DFS（Depth-First-Search 深度优先搜索）
首先将起始结点放入 OPEN 表，CLOSE 表置空，算法开始时：
1、如果 OPEN 表不为空，从表中开始取一个结点 S，如果为空算法失败
2、S 是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到 3
3、将 S 的所有后继结点展开，就是从 S 可以直接关联的结点（子结点），如果不在 CLOSE
表中，就将它们放入 OPEN 表开始，而把 S 放入 CLOSE 表，重复算法到 1。
是否有看出：上述的 BFS 和 DFS 有什么不同？
仔细观察 OPEN 表中待访问的结点的组织形式，BFS 是从表头取结点，从表尾添加结
点，也就是说 OPEN 表是一个队列，是的，BFS 首先让你想到‘队列’；而 DFS，它是从
OPEN 表头取结点，也从表头添加结点，也就是说 OPEN 表是一个栈！
DFS 用到了栈，所以有一个很好的实现方法，那就是递归，系统栈是计算机程序中极
重要的部分之一。用递归也有个好处就是，在系统栈中只需要存结点最大深度那么大的空间，
我的内容管理
展开
