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

(更多…)