A*算法是在Dijstra算法上进行改进，知道起点和终点位置Dijstra算法是四面八方全部寻找，而A*算法则可以往一个最优方向寻找，即启发式的搜索，在提高算法效率的同时，保证找到一条最优路径。

一、原理：

A*算法的核心在于估价函数的设计上，如下式：

 其中：称为耗散函数，为起始节点到节点n的实际代价（距离）；称为启发函数，表示节点n到目标节点的估计代价；表示从起始节点经由节点n到目标节点的估计代价。

 同Dijstra算法类似，A*算法也维持一个Open表。Open表中节点的优先级是依据的大小排列的，值越小，被搜索到的优先级越高。为保证能搜索到最优解启发函数不能太大，不能大于节点n到目标节点的实际代价。如果等于0则A*算法退化为Dijstra算法，虽然能保证得到最优路径，但算法效率低。如果恰好等于节点n到目标节点的实际代价，则A*算法探索的节点恰好就是最优路径上的节点。所以的取值直接影响算法的速度和精度。常见的取值有两点之间的欧几里得距离（Euclidean Distance）和曼哈顿距离（Manhattan）等。

 如上图每个方格左上角是，左下角是，右下角是。

 如果不高于实际到目标顶点的距离，则一定可以求出最优解，而且越小，需要计算的节点越多，算法效率越低，常见的评估函数有欧几里得距离、曼哈顿距离、切比雪夫距离，评估函数就是告诉算法往哪个方向进行搜索。

①、曼哈顿距离：

正方向网格的标准试探法是曼哈顿距离，如网格大小为D则：

 这里没有区别考虑对角线移动，或者认为没有对角线移动；

②、切比雪夫距离：

如果地图允许对角线移动，则需要一个不同的启发函数。这里增加一个D2为对角线移动的成本；

 当D=1，且D2=1，这称为切比雪夫距离。当D=1，且D2=sqrt(2)这称为八分位数距离；

③、欧几里得距离：

如果地图可以在任何角度移动，则应该使用直线距离：

二、相关概念和搜索流程：

1、A*算法中涉及到的相关概念：

1）开放表（openlist）：

openlist中存放待搜索的节点，初始只有起点A，然后将A放入closelist，将A的相邻节点放入openlist中；

2）封闭表（closelist）：

closelist中存放的是已经搜索过的节点；

3）父节点：

当前节点的上一个节点；

2、A*算法的流程步骤：

1）把起点加入openlist表中；

2）重复下面的过程：

a、遍历openlist，查找F值最小的节点，把它当作当前要处理的节点；

b、把这个节点移入closelist；

c、对当前方格的8个相邻方格（二维环境是8个方格，三维环境是26个方格）的每一个方格处理如下：

1. 如果它是障碍点或不可达点（边界点）或在closelist中则忽略它；
2. 如果它不在openlist中，把它加入openlist中，并且把当前方格设置为它的父节点，记录该方格的F、G、H值；
3. 如果它已经在openlist中，检测当前的这条路径是否更好（如果节点已经在方格中则说明已经有一个父节点到达了这个方格，那么现在要看当前节点到这个方格是不是路径更优），这里比较G值，更小的G值表示路径更好。如果更好，则将它的父节点改为当前节点，并重新计算它的G和F值。如果openlist中是按F值排序的话，则此时需要重新排序；
4. 停止：如果终点加入了openlist中；或者查找失败；或者openlist表为空，此时没有了路径；
5. 保存路径，从终点开始，每个方格沿着父节点移动到起点，如果得到的便是路径。

三、一个二维例程：

参照网上资料验证了一下二维的：就不贴代码了

上图，起点在绿色方格，黑色方格是障碍点，蓝色的方格表示已经搜索过了；黄色方格表示得到的最优路径。