关于寻路算法的一些思考(4):A* 算法的变体
2015-04-09来源:易贤网

定向搜索

在A*算法的循环中,OPEN集合用来保存所有用于寻找路径的被搜索节点。定向搜索是在A*算法基础上,通过对OPEN集合大小设置约束条件而得到的变体算法。当集合太大的时候,最不可能出现在最优路径上的节点将会被剔除。这样做会带来一个缺点:由于必须得保持这样的筛选,所以可选择的数据结构类型会受到限制。

迭代深化(Iterative deepening)

迭代深化是一种很多AI算法采用的方法,开始的时候给一个估计值,然后通过迭代使它越来越精确。这个名字来源于游戏树搜索中对接下来几次操作的提前预判(例如,在象棋游戏中)。你可以通过向前预判更多的操作来深化游戏树。一旦当你的结果不发生变化或提高很多,就可以认为你已经得到了一个非常好的结果,即使让它更精确,结果也不会再改善。在迭代深化A*(IDA*)算法中,“深度”是 f 值当前的一个截断值。当 f 值太大的时候,节点不会被考虑(也就是说,不会被加入到OPEN集中)。第一次循环时,只需要处理非常少的节点。随后的每次循环,都会增加访问的节点数。如果发现路径得到优化,就继续增加当前的截断值,否则结束。更多细节,参见链接。

我个人并不看好IDA*算法在游戏地图寻路中的应用。迭代深化的算法往往增加了计算时间,同时降低了内存需求。然而,在地图寻路的场景中,节点仅仅包含坐标信息,所需要的内存非常小。所以减少这部分内存开销并不会带来什么优势。

动态加权

在动态加权算法中,你假定在搜索开始时快速达到(任意)一个位置更为重要,在搜索结束时到达目标位置更为重要。

f(p) = g(p) + w(p) * h(p)

有一个权值(w >=  1 )和该启发式关联。当不断接近目标位置的时候,权重值也不断降低。这样降低了启发式函数的重要性,并增加了路径实际代价的相对重要性。

带宽搜索

带宽搜索有两个被认为非常有用的特性。这个算法变体假设 h 是一个估计过高的值,但它的估计误差不会超过 e。那么在这样的条件下,搜索到的路径代价与最优路径代价的误差不会超过 e。这里需要再一次强调,启发值设置得越好,那么得到的结果也将越好。

另外一个特性是用来判断你是否可以删掉OPEN集合中的某些节点。只要 h+d 大于路径真实代价(对于一些 d),那么你可以丢掉任意满足其 f 值比OPEN集合中最优节点 f 值至少大 e+d 的节点。这是一个很奇异的特性。你相当于得到了一个 f 值的带宽;所有在这个带宽意外的节点都可以被丢弃掉,因为他们被保证一定不会出现在最优路径中。

有意思地是,对于这两种特性分别使用不同的启发值,仍然可以计算得到结果。你可以使用一个启发值来保证路径代价不会太大,另外一个启发值来决定丢弃掉OPEN集中的哪些节点。

双向搜索

与从头到尾的搜索不同,你也可以并行地同时进行两个搜索,一个从开始到结束,一个从结束到开始。当它们相遇的时候,你就会得到一个最优路径。

这个想法在一些情况下非常有用。双向搜索的主要思想是:搜索结果会形成一个在地图上呈扇形展开的树。而一个大的树远不如两个小的树,所以使用两个小的搜索树更好。

面对面的变体将两个搜索结果链接到一起。该算法选择满足最佳 g(start,x) + h(x,y) + g(y,goal) 的一对节点,而不是选择最佳前向搜索节点 g(start,x) + h(x,goal) 或者最佳后向搜索节点 g(y,goal) + h(start,y)。

重定向算法放弃同时前向和后向的搜索方法。该算法首先进行一个短暂的前向搜索,并选出一个最佳的前向候选节点。接着进行后向搜索。此时,后向搜索不是朝向开始节点,而是朝向刚刚得到的前向候选节点。后向搜索也会选出一个最佳后向搜索节点。然后下一步,再运行前向搜索,从当前的前向候选节点到后向候选节点。这个过程将会不断重复,直到两个后选节点重合。

动态A*与终身规划A*

有一些A*的变体算法允许初始路径计算之后地图发生改变。动态A*可以用于在不知道全部地图信息的情况进行寻路。如果没有全部信息,那么A*算法的计算可能会出现错误,动态A*的优势在于可以快速改正那些错误而不会花费很多时间。终身规划A*算法可以用于代价发生改变的情况。当地图发生改变的时候,A*计算得到路径可能会失效;终身规划A*可以重复利用以前的A*计算来产生新的路径。

然而,动态A*与终身规划A*都要求大量的空间——运行A*算法时需要保持它的内部信息(OPEN/CLOSED集合,路径树,g值)。当路径发生改变的时候,动态A*或终身规划A*算法会告诉你是否需要根据地图的变化调整你的路径。

对于一个有大量运动单元的游戏,通常不会想要保存所有的信息,所以动态D*和终身规划A*可能不适用。这两种算法主要为机器人而设计。当只有一个机器人的时候,你不需要为了其他机器人的路径来重复使用内存。如果你的游戏只有一个或比较少的单元,你能会想要研究一下动态A*或者终身规划A*算法。

D*算法概述

D*文章1

D*文章2

终身规划算法概述

终身规划算法论文(PDF)

终身规划 A*算法 applet

跳跃点搜索

提高A*算法计算速度的大多数技术都是采取减少节点数量的策略。在统一代价的方格网络中,每次单独搜索一个独立格空间是非常浪费的。一个解决办法是对其中关键节点(例如拐角)建立一个用来进行寻路的图。但是,没有人愿意预先计算出一个路标图,那就来看看可以在网格图上向前跳跃的A*变体算法,跳跃点搜索。 考虑到当前节点的孩子节点有可能会出现在OPEN集合中,跳跃点搜索直接跳跃到从当前点可看到的遥远的节点。随着OPEN集合中节点的不断减少,每一步的代价都会越来越高虽然都很高,但是步数也会越来越少。相关细节,可以参考链接;这篇博客中有很好的可视化解释;还有,reddit上对优缺点的讨论可点击这个链接。

此外,在矩形对称消减中,有对地图进行分析和图中嵌入跳跃。这两种技术都是应用于方格网络图中的。

Theta*

有时网格会用来寻路是因为地图是用网格来生成,而不是因为真的要在网格上移动。如果给定一个关键点的图(例如拐角)而不是网格的话,A*算法可以运行得更快并得到更优的路径。但是,如果你不想预先计算那些图的拐角,你可以通过A*算法的变体Theta*在方格网络上进行寻路而不必严格遵循那些方格。当构建父亲指针的时候,如果有一个祖先与该节点间存在边,那么Theta*算法会直接将该指针指向该祖先而忽略所有的中间节点。不像路径光滑那样将A*找到的路径变为直线,Theta*可以把那些路径的分析作为A*算法过程的一部分。这样的做法可以比后处理方格路径使之成为任意倾角的路径的方式,可以得到更短的路径。这篇文章的是对算法的一个比较合理的介绍,另外可参考懒惰Theta*。

Theta*的思路也可能被应用于导航网格。

更多信息请查看IT技术专栏

推荐信息