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) 发生时,插入操作有可能只在树的一侧插入以至整个树失去平衡。尽管我没有可靠的用例。

(更多…)

Thoughts on Pathfinding – 实现(上)

如果不考虑具体的实现代码,A* 算法其实是相当简单的。想象它有一个 OPEN 集和一个 CLOSED 集。其中 OPEN 集保存着等待那些筛选的节点。在最初,OPEN 集只包含一个元素,那就是最开始的起始节点。CLOSED 集包含那些已经被访问过的节点。在最初,CLOSED 集是没有任何内容的。如果用图的方式来理解,那么 OPEN 集就是边境而 CLOSED 集就是那些可访问区域的内部。由于每一个节点同时保存着指向其父节点的指针,所以我们可以知道它是如何被访问到的。

在实际流程中,有一个主要的循环不停地从 OPEN 集中取出最佳的节点 n(拥有最小 f 值的节点)并检查这个节点。如果 n 是最终的目标节点,那么我们的任务就完成了。否则,节点 n 将从 OPEN 集中移除并加入 CLOSED 集。接着检查节点 n 的邻居,节点 n’。如果 n’ 也被访问过,那么我们就不再考虑这个节点(注)。如果 n’ 在 OPEN 集中,那么它以后肯定是会被检查到的,所以我们现在也不需要考虑这个节点(注)。否则,我们把 n’ 加入 OPEN 集中,并把它的父节点设置成 n。通往节点 n’ 的花费 g(n’) 将被设置成 g(n) + movementcost(n, n’)。

你可以在这里查看一些交互式图例的演示。

注:我在这里忽视了一个小小的细节。操作时你其实需要检查节点的 g 值是否变小了,如果变小了,你应该重新 OPEN 它。

注:如果你使用的是始终最小的启发式,这种情况不会发生。在实际设计中,通常使用的是不最小的启发式

你可以在这里看到 Python 的 C++ 的实现方法。

(更多…)