A*寻路算法

引入

假设你身处一座迷宫，要从起点穿过障碍到达终点，像上图一样，想要快速找到一条最短路径该如何做呢？
DFS？显然太耗时间。BFS？有太多点不必遍历。
所以，我们可以引入A*算法来解决这一问题。

概述

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。 ----摘自 百度百科

如下图1，若要搜索s到t的最短路径（只能上下左右走），用BFS的话，如图2，会搜索大量的没用格子（如红框框起来的），原因是什么呢？我们发现，是因为BFS会以自身为中心，无条件向四周蔓延。所以，我们想，能否加上若干条件，让BFS总向终点的方向搜呢？

在A* 算法中，f数组维护了“从初始状态经由状态n到目标状态的最小代价估计”，即上述的“条件”，计算方法为：\(f_{i,j}=g_{i,j}+h_{i,j}\)。其中，g数组存的是“在状态空间中从初始状态到状态n的最小代价”，h数组存了“从状态n到目标状态的路径的最小估计代价”。说人话，g存的是从起点到该点的代价，h存的是该点到终点的预计代价，f就是g+h，即综合代价。显然f越小，它在最短路径上的可能性越大，我们就要选择它继续遍历。
于是，我们得到了A* 算法的大致框架