关于寻路算法的一些思考（4）：A* 算法的变体

210 阅读 0 评论 139 点赞

我是靠谱客的博主单身老鼠，最近开发中收集的这篇文章主要介绍关于寻路算法的一些思考（4）：A* 算法的变体，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

定向搜索

在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*的思路也可能被应用于导航网格。