Forever Loop.

Trouble Busters

Thoughts on Pathfinding – 实现(下)

Thoughts on Pathfinding – 实现(上)的部分中,我们说到了一些不同数据结构对于整个算法复杂度的影响,今天我们将继续列举一些数据结构带来的影响,以及在实际情况中的应用。

哈希表

索引数组使用了大量的内存来保存那些不在 OPEN 集中的节点。一个改变的方法就是使用哈希表,使用哈希函数 h(n) 把图上的每一个节点 n 映射到一个哈希码。让哈希表的大小是 N 的两倍来让发生冲突的可能性降到最小。假设 h(n) 的复杂度是 O(1),因为我们需要搜索整个结构,那么关系检查操作复杂度为 O(1),插入操作复杂度是 O(1),移除操作复杂度是 O(numnodes)。提升优先级操作的复杂度是 O(1)。

伸展树

堆是一种基于树的结构,它的期望时间复杂度是 O(log F)。在 A* 中,当你移出一个节点时由于其他节点需要移动的特性,最佳复杂度以及最差复杂度的变化会比较大。如果我们能够设计一种数据结构使得复杂的的变化趋于可控,哪怕最佳情况下的花费可能会变高。

伸展树就是一种可以自我调整的树形结构。任何对节点的访问都尝试把该节点推到树的顶部。这就产生了一种类似“缓存”的效果:很少被使用的节点将在不影响速度的情况下被慢慢地被移动到树的底部。你的伸展树有多大并不重要,因为操作的所需要的时间与你的“缓存空间”有关。在 A* 中,低花费的节点会被经常使用,高花费的节点不会被长时间使用,所以那些高花费的节点可以移动到树的底部。

在使用了伸展树以后,集合关系检查,插入,移除最佳以及优先级操作的最佳复杂度都是 O(log F),最差复杂度是 O(F)。有代表性的是,伸展树带来的缓存效果能避免最坏情况的发生。迪杰斯特拉算法以及带有低估的启发式函数的 A* 算法却有一些特性让伸展树达不了最优。特别是对于某个节点 n 以及邻居节点 n’ ,理论上当 f(n’) >= f(n) 发生时,插入操作有可能只在树的一侧插入以至整个树失去平衡。尽管我没有可靠的用例。

HOT 队列

还有一种比堆好的数据结构。通常情况下,你可以限定优先级队列的范围。当你限定好一个范围,总会存在一个更符合你范围的算法。比如,对任意值的排序可以在 O(N log N)的范围内完成,但是当范围固定时,桶排序和基数排序可以在 O(N) 的时间内完成。

我们可以使用 HOT 队列(Heap On Top queues)来利用 f(n’) >= f(n),其中 n’ 是 n 的邻居节点。我们删除 f(n) 中值最小的节点 n,插入满足 f(n) <= f(n’) <= f(n) + delta 的节点 n’,其中 delta <= C。其中常数 C 是从一个节点到邻居节点花费改变量的最大值。因为 f(n) 是 OPEN 集中的最小值 f,并且正要被插入的所有节点都小于等于 f(n) + delta,我们知道 OPEN 集中所有的 f 值都在 0 至 delta 之间。所以在桶/基数排序中,我们可以用“桶”来对 OPEN 集中的节点进行排序。

通过 HOT 队列,顶端的桶使用二元堆而所有其他的桶都是未排序的数组。因为我们不知道节点会在哪个桶,所以集合关系检查的复杂度是 O(F)。插入以及移除最佳顶桶的复杂度是 O(log F/K)。插入其他桶的复杂度是 O(1),而移除最佳桶的情况不会发生!如果顶桶是空的,我们就必须把下一个桶即未排序的数组转换为二元堆。这个操作需要 O(F/K) 的时间。增加优先级的操作中,删除操作复杂度为 O(F/K),插入操作的复杂度为 O(log (F/K)) 或者 O(1)。

在 A* 中,我们加入 OPEN 集中的许多节点实际上是根本不被需要的。在这方面 HOT 队列会有很大的优势,因为不需要的元素的插入操作只花费 O(1) 的时间。只有需要的元素被转换(那些代价较低的节点)。唯一一个时间超过 O(1) 的操作就是从堆中删除节点,话费 O(log (F/K)).

另外,如果 C 比较小,我们可以让 K=C,则对于最小的桶,我们甚至不需要一个堆,因为在一个桶中的所有节点都具有相同的 f 值。所以插入和移除最佳的花费都是 O(1)。有人研究过,HOT 队列在至多有 800 个节点的 OPEN 集中和堆一样快,当 OPEN 集中有至多 1500 个结点时,则比堆快 20%。我认为当节点越多,HOT 队列也会越快。

HOT 队列的一个简单变化就是二层队列:把好的节点放进一个数据结构(堆或者数组),而把不够好的节点放入另一个数据结构(数组或链表)。因为大多数进入 OPEN 集中的节点都不足够好,所以它们从不被检查,因而把它们放进一个大数组中是没有坏处的。

配对堆

对于 A*,在理论上斐波那契堆是一个不错的优先级队列。但实际上却从未被使用,一个配对堆可以理解成一个简单的斐波那契堆。有人说它们工作的不错;尽管我从未使用过。

数据结构比较

有一点值得我们注意的是,我们并不仅仅需要关心复杂度的问题。我们也要关心算法中常数的行为。为了了解原因,假设我们有两个算法,一个复杂度为 O(log F),而另一个复杂度是 O(F),其中 F 是堆中元素的个数。再假设第一个算法在你的机器上运行需要花费 10,000 * log(F) 秒,而另一个算法的花费时间为 2*F 秒。当 F=256 时,第一个算法需要 80,000 秒,而第二个算法只需要 512 秒。看上去更“快”的算法却花费了更多的时间,而且,只有当 F > 200,000 时,第一个算法才开始变快。

你不能仅仅比较两个算法。你也应该比较算法的实现方法。同时你还要知道你的样本的大概规模。在上面这个例子中,当 F > 200,000 时,第一个算法才会比较快速,但是,如果你的实际样本规模,打个比方,只有 30,000 的话,那么第二个算法才是你的最佳选择。

没有一种基本的数据结构是完全适用于所有情况的。无序数组和链表在插入操作的花费很低(速度快),但是关系检查和移除的操作却花费巨大(速度慢)。有序数组和链表在关系检查以及移除操作时速度较快,但是插入操作的花费却很慢。二元堆的插入和移除操作的速度较快,但是关系检查就很慢。伸展树能让所有操作都快一些。HOT 队列让插入操作和移除操作都快了一些,同时也让关系检查操作也加速了一些。索引数组的关系检查和插入操作的速度很快,但是移除操作却不可思议的慢,同时还要消耗相当的内存空间。哈希表类似于索引数组,但是消耗的内存空间要少得多,而且移除操作比起后者要稍微快速一些。

有关高级优先队列的资料和相关实现,请查看 Lee Killough 的优先级队列页面

混合实现

为了达到最佳的性能,你也许需要混合实现一些数据结构。比如对 O(1) 的成员关系检测使用 O(1) 复杂度的索引数组,对 O(log F) 的插入操作以及 O(log F) 的移除最佳操作使用二元堆。对于优先级的提升,使用索引数组进行测试以确定是否真的要进行调整(通过排序索引数组中的 g 值),然后对于那些极少需要调整的情况,使用二元堆进行操作。你也可以使用索引数组保存堆中每个节点的位置;这可以是你的优先级提升操作的复杂度变为 O(log F)。

与程序循环的交互

交互式的(尤其是实时的)程序对最佳路径的计算要求很高。能够得到任何的解决方案有时候比得到一个最佳方案可能更重要。尽管如此,在所有其他因素都相同的情况下来说,短路径要比长路径好的多。

一般来说,计算靠近起始节点的路径比计算靠近目标节点的路径要更重要一些。根据立即开始原理:让目标尽快的开始运动,哪怕并不是最理想的路径。随后再计算一个最佳的路径。在实时程序中,A* 的延迟比准确更重要。

我们可以对物体进行编程让它们能够根据自己的本能(简单行为)或者智力(一条预先计算好的路径)来心动。除非有其他因素控制,否则它们就按照已有的本能进行移动(通常都是这样使用,Rodeny Brook 的机器人体系结构中也如此使用),与立即进行计算所有路径有所不同,让目标在每一个、两个、或者更多的循环中搜索路径。先让目标先按照本能进行行动(比如简单地朝终点直线前进),然后才为它们寻找路径。这种方法让路径搜索的花费趋于平缓,因为计算操作不会集中发生走同一个时刻。

提前退出

我们可以在 A* 进行主循环的时候从中提前退出来得到一条局部的路径。通常来说,当算法找到目标节点的时候,整个主循环也随之退出了。然而,在此之前的任意节点,可以得到一条到达 OPEN 集中当前最佳节点的路径。这个节点就是到达目标节点最佳路径中的一个理想的中间节点。

可以提前退出的情况包括已经检查了一定数量的节点,A* 已经运行了一些时间,或者已经扫描了一些距离初始节点有一些距离的节点。当拼接路径的时候,应当注意限制这些路径的最大值,而且一定比完整路径要小。

中断算法

如果需要进行路径搜索的目标比较少,或者用于保存 OPEN 和 CLOSED 集的数据结构规模也比较小,那么可以设计一个中断流程保存算法状态,然后退出搜索循环。

组运动

路径的请求并不是均匀分布的。在即时模式中有一个常见的情况就是用户有可能会同时选择多个物体并命令它们朝着目标进行移动。这种操作会给整个系统带来沉重的负担。

在这种情况下,为某个物体寻找的最优路径对其他物体也是同样有效的。其中一种方法就是寻找一条从物体的中心到目标的中心路径 P。然后对所有物体都使用这条路径的绝大部分,而后再对每一个物体,比如前十步,或者后十步分别寻找自己的最优路径。这样物体 i 得到的一条从自身开始到 P[10]  的路径,紧接着就是共享的路径 P[10…len(p) – 10],最后则是从 P[len(P) – 10] 到目的地的路径。

为每个物体分别寻找路径是比较快速的(平均长度为 10),而较长的路径被共享。大多数路径只要寻找一次就能被所有组内的其他物体共享。然而,当用户们看到所有的物体都沿着相同的路径移动时,可能会对系统失去兴趣。为了对之做一些改进,可以让物体稍微沿着不同的路径进行运动。其中一种方法就是选择邻近节点以改变路径。

还有一种方法就是让每个物体都意识到其他物体的存在(或许是通过随机选择 一个“领导”物体,或者是通过选择一个能够最好地意识当前情况的物体),同时仅仅为领导寻找路径,然后用 flocking 算法让它们以组的形式进行运动。

然而还有一种方法就是使用 A* 算法的中间状态。这个状态可以被朝着目标移动的多个物体共享,只要物体共享相同的启发式函数和花费函数。那么当主循环退出的时候,只要不消除 OPEN 和 CLOSED 集;使用 A* 上一次的 OPEN 和 CLOSED 集开始下一次的循环(这可以被看成是中断算法和提前退出部分的一般化)。

细化

如果图中没有障碍物,取而代之的是不同花费的地形,那么可以通过低估地形的花费来计算一条初始路径。比如,如果草地的花费是 1,山地的花费是 2,山脉的花费是 3,那么 A* 会考虑通过 3 个草地以避免 1 个山脉。通过把草地看成 1,山地看成 1.1,而山脉看成 1.2 来计算出事路径,A* 将会用更少的时间去设法避免山脉,而且可以更快地找到一条路径(类似于精确启发式的效果)。一旦找到一条路径,物体就可以开始移动,循环就可以持续下去。当有富裕的计算资源时,可以用真是的移动花费去计算更好的路径。

 

评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.