A*算法

A*算法解决加权图的最短路径问题。

原理

从图的特定起始节点开始，A*旨在找到从起始节点到目标节点见具有最小代价的路径（最少行驶距离、最短时间等）。A*算法维护源自起始节点的路径树，并且一次一个地延伸这些路径直到满足其终止标准。

在A*算法主循环的每次迭代中，需要确定对哪条路径进行扩展，A*算法根据路径的成本和评估点到目标点的的成本的估计来选择，具体来说，A*算法选择待评估集合中能使下式最小的点作为扩展路径的点：

f(n)=g(n)+h(n)

其中n是路径上的下一个点，g(n)是从起始点到节点n的路径代价，h(n)是一个启发式函数，它是节点n到目标点的估算代价。

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算法。

伪代码

function reconstruct_path(cameFrom, current)
    total_path := {current}
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path

function A_Star(start, goal)
    // 已经被评估的节点的集合
    closedSet := {}

    // 已经发现但未被评估的节点的集合
    // 初始时，只有起始节点已被发现
    openSet := {start}

    // 每个节点的前趋
    cameFrom := an empty map

    // g值，初始时为无穷大，起始点的g值为0
    gScore := map with default value of Infinity
    gScore[start] := 0

    // f值，初始时为无穷大，起始点的f值与起始点的h值相等（起始点g值为0）
    fScore := map with default value of Infinity
    fScore[start] := heuristic_cost_estimate(start, goal)

    while openSet is not empty
        // 取出openSet中f值最小的节点current
        current := the node in openSet having the 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)