A*算法简介
1.1 作用与特点
A* 算法是启发式搜索型的路径规划算法，是一种尽可能基于现有信息的搜索策略，也就是说搜索过程中尽量利用目前已知的诸如迭代步数，以及从初始状态和当前状态到目标状态估计所需的费用等信息。总体来说，A*算法是一种较迅速的路径规划算法，比遍历式的路径规划算法，如广度优先算法（BFS）等都更加迅速和节省空间。
1.2 A*算法的基本思想与数学函数模型：
1.2.1基本思想
引入当前节点j的估计函数f*,当前节点j的估计函数定义为：
f*(j)= g(j)+h*(j)
其中g(j)是从起点到当前节点j的实际费用的量度，h*(j)是从节点j到终点的最小费用的估计，可以依据实际情况，选择h*(j)的具体形式，h*(j)要满足一个要求：不能高于节点j到终点的实际最小费用。从起始节点点向目的节点搜索时，每次都搜索f*(j)最小的节点，直到发现目的节点。
1.2.2数学函数模型
A* 算法的核心是设计估价函数，设计估价函数h(j)有很多方法，
（1）估价函数1：欧几里德距离
可以证明，在和起点距离相等的中间节点集合里，与终点直线距离（欧几里德距离）越小的节点，方向夹角越小。假设在图2-3求S到G点的最短路径，与S最近的点是节点2，与G最近的是节点11，因此可以确定上路点是节点2，下路点是节点11，求S到G点的最短路径就是求节点2到节点11的路径。定义L(i,j)表示从节点i到节点j的有向线段，Angle[ L(I,j),L(a,b) ]表示有向线段ij和有向线段ab的夹角。由于Angle[ L(2,11),L(2,3) ]< Angle[L(2,11),L(2,1) ] ,因此选择节点3，而与节点3连接的节点有节点4和节点7，Angle[ L(3,11),L(3,7) ]< Angle[ L(3,11),L(3,4) ]，选择节点7，与节点7相连的节点有节点8，节点11，和节点6，由于Angle[L(7,11),L(7,11) ]< < Angle[ L(7,11),L(7,6) ]<Angle[ L(7,11),L(7,8) ],选择节点11，至此，已经找到从S到G点的一条路径。
假设起点S的坐标（Sx,Sy），终点G的坐标(Gx,Gy),中间点N的坐标(Nx,Ny), 估价函数取欧几里德距离，表示为：
这个估价函数的计算量很大，不利于海量数据的路径规划计算。
（2）估价函数2：曼哈顿距离
利用欧几里德距离计算估价函数的计算量很大，因此考虑将两点之间的曼哈顿距离作为估价函数。其中A点的经纬度为(Ax,Ay),B点的经纬度是(Bx,By),则A、B之间的Manhattan距离可以表示为:
其中：P=2πR/360
由于P是常数，可以简化为:
此估价函数计算量小，虽然不是严格的方向优先，但基本能保证最短路径的搜索方向向目标点的方向进行。
除了上面两种启发函数，还有octile启发函数与切比雪夫启发函数。一般曼哈顿启发函数即可较好满足要求。
1.2.3 A*算法的算法步骤
A* 算法程序中，包括两个列表（Open和Closed列表），一个记录下所有被考虑来寻找最短路径的方块（称为open 列表），一个记录下不会再考虑的方块（称为closed列表）。
（1）路径增量：
A*算法给每个方块一个G+H 和值：
G是从开始点A到当前方块的移动量（中间方块的数量）。所以从开始点A到相邻小方块的移动量为1，该值会随着离开始点越来越远而增大。
H是从当前方块到目标点的移动量估算值。这个常被称为探视，因为我们不确定移动量是多少 – 仅仅是一个估算值。
（1）算法步骤：
步1：生成空的Open表、Close表，将起点放入Open表
步2：如果Open表为空，则失败退出。
步3：从Open表中，找出头节点U,作为当前节点,将它从OPEN表中移除。
步4：判断U是否为终点，如果是，则通过节点U的父指针，一直遍历到起点，找到到最优路径，算法结束。否则，转步5.
步5：扩展当前节点U,找到其扩展的后继节点集合V,遍历集合V中的节点，如果节点即不在Open表也不在Close表，计算该节点的估计值，将节点加入到OPEN表，设置父节点为U.如果节点在Open表、Close表，比较当前节点的代价g(v)和Open表、Close表中代价，如果当前节点的代价g(v)小，更新表中的代价和父节点指针。
步6：按估价值递增的顺序，对Open表中所有节点进行排序。
步7：转步2.
下一篇文章来放matlab程序。学习时曾参考：
2. https://blog.csdn.net/autonavi2012/article/details/80923431（原理）
3. https://blog.csdn.net/m0_38054145/article/details/81808541（原理）
4. http://qiao.github.io/PathFinding.js/visual/（图解）