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)

原文发布于微信公众号 - mwangblog(mwangblog)

原文发表时间:2019-05-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券