A*是一种路径搜索算法，比如为游戏中的角色规划行动路径。
1. 输入
A* 算法的输入是，起点（初始状态）和终点（目标状态），以及两点间所有可能的路径，以及涉及到的中间节点（中间状态），每两个节点间的路径的代价。
一般还需要某种启发函数，即从任意节点到终点的近似代价，启发函数能够非常快速的估算出该代价值。
2. 输出
输出是从起点到终点的最优路径，即代价最小。同时，好的启发函数将使得这一搜索运算尽可能高效，即搜索尽量少的节点/可能的路径。
3. 公式
f(n)=g(n)+h(n)
f(n) 是从初始状态经由状态n到目标状态的代价估计
g(n) 是在状态空间中从初始状态到状态n的实际代价
h(n) 是从状态n到目标状态的最佳路径的估计代价
4. 搜索算法
A*算法是从起点开始，检查所有可能的扩展点（它的相邻点），对每个点计算g+h得到f，在所有可能的扩展点中，选择f最小的那个点进行扩展，即计算该点的所有可能扩展点的f值，并将这些新的扩展点添加到扩展点列表（open list）。当然，忽略已经在列表中的点、已经考察过的点。
不断从open list中选择f值最小的点进行扩展，直到到达目标点（成功找到最优路径），或者节点用完，路径搜索失败。
算法步骤：
1） 把起点加入 open list 。
2） 重复如下过程：
a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
b. 把这个节点移到 close list（已经考察过的节点列表） 。
c. 对当前节点的所有邻近节点
◆ 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
◆ 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，
记录该方格的 F ， G 和 H 值。
◆ 如果它已经在 open list 中，检查这条路径 ( 即经由当前节点到达它那里 ) 是否更好，
用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为
当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，
改变后你可能需要重新排序。
d. 停止，当你
◆ 把终点加入到了 open list 中，此时路径已经找到了，或者
◆ 查找终点失败，并且 open list 是空的，此时没有路径。
3） 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。
参考
A* 算法步骤的详细说明请参考 A*寻路算法，它包含图文案例清楚的解释了A*算法计算步骤的一些细节，本文不再详细展开。
5. 为什么A能够快速找到最优路径*
看一下上面参考文档中的案例图，最终搜索完成时，蓝色边框是close list中的节点，绿色边框是open list中的节点，每个方格中三个数字，左上是f（=g+h），左下是g（已经过路径的代价），右下是h（估计未经过路径的代价）。蓝色方格始终沿着f值最小的方向搜索前进，避免了对一些不好的路径（f值较大）的搜索。（图片来自A*寻路算法）
6. 启发式函数
现在我们可以理解，A*算法中启发函数是最重要的，它有几种情况：
1) h(n) = 0
一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。但效率不高，因为得不到启发。
2) h(n) < 真实代价
如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A*保证能找到一条最短路径。h(n)越小，A*扩展的结点越多，运行就得越慢。越接近Dijkstra算法。
3) h(n) = 真实代价
如果h(n)精确地等于从n移动到目标的代价，则A*将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A*会运行得很完美，认识这一点很好。
4) h(n) > 真实代价
如果h(n)有时比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。
5) h(n) >> 真实代价
另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。
7. 更多讨论
关于启发函数h、Dijkstra算法、BFS（最佳优先搜索）算法、路径规划情况下启发函数的选择、算法实现时List的数据结构、算法变种等等更多问题，请参考：A*算法
