前段时间接触到 A* 算法，才知道除了Dijkstra和Floyd算法之外，还有一个称之为 A-star的启发式搜索算法也是用于求解最短路径的。以前没有接触过这类启发式搜索算法，所以在此，对A-star算法做一个总结。输出过程如下：
以下所有假设描述都是在N*N的矩阵中，从源节点到目的节点的问题背景。
- 广度优先搜索就是从源节点开始，第一步走到所有可能的节点，然后再这些节点的基础上继续递归，形式有点类似于地震波一样。一层一层的搜索过去，直到找到目的节点为止。当然，其劣势就在于会做很多无用功，算法复杂度太大。
- 广度优先搜索是一层一层的盲目去找，只关注到了出发点到当前扩展点的关系，并没有关注当前点和目的点之间的关系。比如，目的点在最右边，而当前点还在往左边走，这不就是无用功么。A*算法就是解决了这个问题，同时考虑出发点和当前点，以及当前点和目的点之间的关系，然后进行启发式搜索。
- 维护两个表，一个是open表，另一个是closed表，前者是保存所有考虑用来寻找最短路径的节点，后者保存所有已经遍历过的节点，最开始把起点加入open表中，然后取出来，找到从起点可以直接到的所有点，都保存到open中，然后起点加入到closed。然后open表中的所有点根据 F = G + H的值，选出最小的，继续算法过程。G是从出发点到当前点的移动距离，H是当前点到目的点的估算距离(欧式距离或者其他什么距离)。
- 算法思路就是上面这个，理解之后还是很简单的。本来还想自己总结的，发现网上比我写得好的太多了。就不写了吧。
- 参考：A星寻路算法介绍和A*，那个传说中的算法
- 自己实现了一个A-star算法，同时里面实现了一下优先队列：源码见