前面提到过迪杰斯特拉算法，它的原理简述如下：
1.将所有的点放在B集合。(起点距离为0，其他点为无穷大)
2.从B集合找出距离最小的点，取走并放在A集合。
3.根据A集合的新加入的点，对B集合中的邻点进行距离更新。然后转到2。
4.直至终点加入到A集合表示找到，或B集合无最小值全部为无穷大，表示无法找到。
(B集合可以理解为所有待确认的点，其中有的已赋值，有的未赋值，也可以理解为已赋值的为集合B，未赋值的不属于任何集合。建议前者，这样不需要加入队列这一步骤，只对邻点赋值即可)
可知Dijkstra算法总是先找到实际距离最小的点，即使它离终点很远或根本不连通，直至终点从B集合中优先弹出。
而A*算法是一种启发式算法，算法依赖启发函数h(n)，原理与Dijkstra算法步骤类似，区别是
1.引入了f(n)=g(n)+h(n)的概念，从B集合中找出的不是实际距离最小，而是估算距离最小的点。
2.终点的实际距离被赋值即表示找到，并不需要终点被优先队列弹出。
g(n)是起点到当前点的实际距离，h(n)是当前点到终点的估计距离。f(n)为两者的和。这相当于在Dijkstra的寻路算法中加入了导航功能。
这使得A*算法会更高效，导向性更强。而h(n)决定了算法的导向性高低。
h(n)启发函数常用的有：1.曼哈顿距离(适用四方向移动)；2.对角线距离(八方向移动)；3.欧几里得距离(任意方向移动)；
并不是所有的寻路都适用A*算法，更多在启发函数容易建立时考虑使用(避障类)，对于有向图不好建立启发函数则不适用A*。
THE END