A*算法
A*算法解决加权图的最短路径问题。
原理
从图的特定起始节点开始，A*旨在找到从起始节点到目标节点见具有最小代价的路径（最少行驶距离、最短时间等）。A*算法维护源自起始节点的路径树，并且一次一个地延伸这些路径直到满足其终止标准。
在A*算法主循环的每次迭代中，需要确定对哪条路径进行扩展，A*算法根据路径的成本和评估点到目标点的的成本的估计来选择，具体来说，A*算法选择待评估集合中能使下式最小的点作为扩展路径的点：
其中是路径上的下一个点，是从起始点到节点的路径代价，是一个启发式函数，它是节点到目标点的估算代价。
A*的典型实现使用优先级队列来重复选择的最小成本（即f(n)）节点以进行扩展。此优先级队列称为open set或fringe。在算法的每个步骤中，从队列中移除具有最低f(n)值的节点，相应地更新其邻居的f和g值，并且将这些邻居添加到队列中。循环执行以上步骤，直到目标点被扩展，或者队列为空。目标点的f值是即为最短路径的成本，因为目标处的h值为零。
为了找到最短路径的节点序列，可以使路径上的每个节点指向其前趋。运行此算法后，结束节点将指向其前趋，依此类推，直到某个节点的前趋为起始节点。
关于h值
下面介绍在平面栅格地图中h值的三种计算方法：
曼哈顿距离当智能体只能在4个方向（无对角线）上移动时，可以使用曼哈顿距离作为h值。计算方法如下：
h = abs(current.x - goal.x) + abs(current.y-goal.y)
对角线距离当智能体能在8个方向上移动时，可以使用对角线距离作为h值。计算方法如下：
h = max{abs(current.x - goal.x), abs(current.y - goal.y) }
欧式距离 当智能体能在任意方向上移动时，可以使用欧式距离作为h值。计算方法如下：
h = sqrt( abs(current.x - goal.x)^2 + abs(current.y - goal.y)^2)
=========
h值大小的会影响A*算法的效果：
- h(n) := 0，则只有g(n)起作用，此时A*演变成Dijkstra算法，这保证能找到最短路径。
- 如果h(n)比从n移动到目标的实际代价小（或者相等），则A*确定能找到一条最短路径。但是h(n)越小，A*扩展的结点越多，运行就得越慢。
- 如果h(n)精确地等于从n移动到目标的代价，则A*将会仅仅寻找最佳路径上的节点而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，但仍可以在一些特殊情况下让它们精确地相等。只要提供完美的信息，A*算法会运行得很完美。
- 如果h(n)比从n移动到目标的实际代价高，则A*不能保证找到一条最短路径，但它运行得更快。
- 如果h(n)比g(n)大很多，则只有h(n)起作用，A*演变成BFS算法。
伪代码
functionreconstruct_path(cameFrom, current)
total_path := {current}
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path
functionA_Star(start, goal)
// 已经被评估的节点的集合
closedSet := {}
// 已经发现但未被评估的节点的集合
// 初始时，只有起始节点已被发现
openSet := {start}
// 每个节点的前趋
cameFrom := an empty map
// g值，初始时为无穷大，起始点的g值为0
gScore := map with default value ofInfinity
gScore[start] := 0
// f值，初始时为无穷大，起始点的f值与起始点的h值相等（起始点g值为0）
fScore := map with default value ofInfinity
fScore[start] :=heuristic_cost_estimate(start, goal)
while openSet is not empty
// 取出openSet中f值最小的节点current
current := the node in openSet havingthe lowest fScore[] value
// 若扩展点即为目标点，则算法结束，返回路径
if current == goal
return reconstruct_path(cameFrom,current)
// 将current从openSet移至closedSet
openSet.Remove(current)
closedSet.Add(current)
// 遍历邻居
for each neighbor of current
// 忽略已经被评估的点
if neighbor in closedSet
continue
// 从起始点到neighbor的距离
tentative_gScore := gScore[current]+ dist_between(current, neighbor)
if neighbor not in openSet // 发现新节点
openSet.Add(neighbor)
else if tentative_gScore >=gScore[neighbor]
continue
// 记录
cameFrom[neighbor] := current
gScore[neighbor] :=tentative_gScore
fScore[neighbor]:= gScore[neighbor] +heuristic_cost_estimate(neighbor, goal)