首页 > 代码库 > A*算法研究

A*算法研究

许多工业与科学计算问题都可以转化为在图中寻路问题。启发式的寻路方法将问题表示为一个图,然后利用问题本身的信息,来加速解的搜索过程。一个典型的例子是有一些通路连接若干城市,找出从指定起点城市到指定终点城市的路径。但是有些问题不存在如此明显的事先定义好的图,它们的图是隐式图,也就是说,问题给定了搜索起点与一系列操作,对起点进行这些操作得到了它的后继结点,以及该操作的代价,对这些后继结点不断地重复操作,就得到了一个带权的有向图,隐式图就定义好了。

对于解决最小路径问题,A*算法性能卓越。首先,对于任何有解路径,A*总能找到一条最佳路径,也就是说A*算法是可采纳的。其次,在保证能找到最佳路径的前提下,A*算法扩展了最少个数的结点,也就是说A*算法是最优的。

使用启发信息的一种重要方法就是估价函数。A*使用技术分享来表示结点技术分享的估价函数,它表示从起点到目标,经由结点技术分享最小费用路径上的费用。它由技术分享技术分享两部分组成,即技术分享。其中技术分享表示从初始结点到技术分享的最佳解路径的费用,技术分享表示从技术分享到目标结点的最佳解路径的费用。但想要知道它们的精确值很难,我们可以使用技术分享来估计技术分享,使用技术分享来估计技术分享技术分享来估计技术分享技术分享表示目前为止,从起始点到技术分享的最小费用,因为日后可能找到更小的费用,所以有技术分享。而在A*算法中,对技术分享的估计通常是乐观的,比实际所需的费用要小,即有技术分享。它们之间的关系可以用下图形象地表示:

技术分享

注:黄色是估计值,黑色是最佳解路径费用

A*算法维护两个集合:OPEN 集和 CLOSED 集。OPEN 集包含待检测节点。初始状态的OPEN集仅包含一个元素:开始位置。CLOSED集包含已检测节点。初始状态的CLOSED集为空。从图形上来看,OPEN集是已访问区域的边界,CLOSED集是已访问区域的内部。每个节点还包含一个指向父节点的指针,以确定追踪关系。

算法有一个主循环,重复地从OPEN集中取最优节点n(即f值最小的节点)来检测。如果n是目标节点,那么算法结束;否则,将节点n从OPEN集删除,并添加到CLOSED集中,然后查看n的所有邻节点n‘。cost= g(n) + movementcost(n, n‘)。n‘有如下三种情况:

  1. 邻结点在CLOSED集中,说明它已被检测过,如果cost<g(n‘),那么说明找到了一条通过n到达n‘更近的路径,更新g(n‘)为cost, n‘的父结点为n,把邻结点从CLOSED集中删去,并把它重新放入OPEN集中(因为同样都是到达n‘,h(n‘)是一样的,g(n‘)小必然能带来更小的f(n‘)),如果cost>=g(n‘),则跳过该邻结点。
  2. 邻结点在OPEN集中,说明它之前被拓展过,如果cost<g(n‘),那么说明找到了一条通过n到达n‘更近的路径,更新g(n‘)为cost, n‘的父结点为n,邻结点仍留在OPEN集中。如果cost>=g(n‘),则跳过该邻结点。
  3. 邻结点不在CLOSED集或者OPEN集中,则加入OPEN集中。

算法用伪代码表示如下:

OPEN = priority queue containing START

 

CLOSED = empty set

 

while lowest rank in OPEN is not the GOAL:

 

current = remove lowest rank item from OPEN

 

add current to CLOSED

 

for neighbors of current:

 

cost = g(current) + movementcost(current, neighbor)

 

if neighbor in OPEN and cost less than g(neighbor):

 

remove neighbor from OPEN, because new path is better

 

if neighbor in CLOSED and cost less than g(neighbor): **

 

remove neighbor from CLOSED

 

if neighbor not in OPEN and neighbor not in CLOSED:

 

set g(neighbor) to cost

 

add neighbor to OPEN

 

set priority queue rank to g(neighbor) + h(neighbor)

 

set neighbor‘s parent to current

 

reconstruct reverse path from goal to start

 

by following parent pointers

在A*算法中,h(n)越大启发信息越多,但是有时计算启发信息本身的代价很高,例如计算技术分享的开销较大,可以使用技术分享来代替,(技术分享总是成立)虽然会扩展多一些的结点,但是依旧是高效的。h(n)=0时,A*退化成了DIjkstra算法。

技术分享时,算法不再可采纳,不一定能找到最优解,但是能以较快的速度找到满意解,这在大多数时候是高效的。例如使用技术分享来代替技术分享。当h(n)很大时,A*变成了贪心算法。

所以要仔细选择h(n),在算法是否可采纳、搜索效率、计算开销之间权衡。

A*算法研究