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)

留下评论

电子邮件地址不会被公开。 必填项已用*标注