WEB开发网
开发学院软件开发VC 在A*寻路中使用二叉堆 阅读

在A*寻路中使用二叉堆

 2006-07-23 11:33:11 来源:WEB开发网   
核心提示:A*算法中最缓慢的部分就是在开启列表中寻找F值最低的节点或者方格,取决于地图的大小,在A*寻路中使用二叉堆,你可能有十几,成百甚至上千的节点需要在某个时候使用A*搜索,这个描述很简单,你可能会想到网上寻找快速排序的更多资料,无需多讲,反复搜索这么大的列表会严重拖慢整个过程

A*算法中最缓慢的部分就是在开启列表中寻找F值最低的节点或者方格。取决于地图的大小,你可能有十几,成百甚至上千的节点需要在某个时候使用A*搜索。无需多讲,反复搜索这么大的列表会严重拖慢整个过程。然而,这些时间在极大程度上受你存储列表的方式影响。

有序和无序的开启列表:简单的方法

最简单的方法就是顺序存储每个节点,然后每次需要提取最低耗费元素的时候都遍历整个列表。这提供可快速的插入速度,但是移除速度可能是最慢的,因为你需要检查每个元素才能够确定哪个才是F值最低的。

通常你可以保持你列表处于有序状态来提升效率。这花费了稍微多一点的预处理时间,因为你每次插入新元素都必须把他们放在恰当的位置。不过移除元素倒是很快。你只要移除第一个元素就可以了,它一定是F值最低的。

有很多方法可以保持你的数据有序(选择排序,冒泡排序,快速排序,等等)并且你可以用你最熟悉的搜索引擎找到这方面的文章。不过我们至少可以先提几种想法。最简单的方法可能是,当你需要添加新元素的时候,从列表开始的地方,依次比较每个元素的F值和要插入的F值的大小。一旦找到一个相等或者更高的F值,你就可以把新元素插入到列表中那个元素的前面。取决于你使用的计算机于亚,使用class或者struct实现的链表可能是不错的方法。

这种方法可以通过保持列表中所有元素的平均值来得到改进,使用这个平均值来决定是从头(如上所说)还是从尾开始处理。总的说来,比平均F值低的新元素将被从头开始处理,而比平均F值高的则从末尾开始。这种方法可以节省一半的时间。

复杂一些,但是更快的方法是把这一想法提高到新的层次使用快速排序,它基本上是从比较新元素和列表中间元素的F值开始。如果新元素的F值低,你接着把它和1/4处元素进行比较,如果还是更低你就比较它和1/8处的元素,如此这般,不断的折半你的列表并且比较,直到找到合适的位置。这个描述很简单,你可能会想到网上寻找快速排序的更多资料。这比至此描述的任何方法都快。

1 2 3 4 5 6  下一页

Tags:路中 使用

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接