《Unity3D高级编程之进阶主程》第一章,C#要点技术(六) 搜索算法

搜索算法

广度优先搜索和深度优先搜索是最直接的搜索方式,但也效率最差,直接使用广度和深度算法,而不加以优化和改进,会浪费太多CPU,以至于整体效率差劲。

好的搜索算法,大部分需要有数据结构的支撑,在数据结构里记录了信息的特征,搜索的记录,和当前搜索内容的环境,以达到裁剪优化的目的。

搜索的目的一般有,一个数组中找出某元素,一个数组中找出某个范围的所有元素,一个2D或3D空间中找出某元素,2D或3D空间中找出某一个范围的所有元素,以及一堆相互连接的结构中找出两点的最短路径等等等。

===

二分查找算法

二分查找算法是搜索中用的最多,也是最简单易用的,效率也比较好。不过它有个先决条件,条件是查找的数组必须是有序的数组。

也就是说,在使用二分算法查找前,必须对数组进行排序。而且在每次更改,插入,删除后都要进行排序以保证数组的有序状态。

二分查找算法的步骤是:

1,将数组分为三块,依次是前半部分,中间位,后半部分。

2,将要查找的值和数组的中间位进行比较,若小于中间位则在前半部分查找,若大于中间位则在后半部分查找,等于中值时直接返回。

3,下一个查找范围,跳入1步骤,依次进行递归过程,将当前的范围继续拆分成前半部分,后半部分,和中间位三部分,直到范围缩小到最小,如果还是没有找到,那说明元素并不在数组里面。

二分查找的平均时间复杂度为O(logN),算是一个比较好的时间复杂度了。不过前提是数组或序列是有序的,这个门槛比较高。

二叉树、二叉查找树、平衡二叉树、红黑树、B树

二叉树及其衍生的所有算法都是以节点有且只有至多两个节点为规则的,这种结构在一维数组上比较有效且容易理解。

二叉查找树,在二叉树之上建立的查找树,主要目标是快速查找,它在构造时的特点是,左边的子节点一定比父节点小,右边的子节点一定比父节点大。算法的方式与二分查找算法有点类似,不一样在于,构建出来的树形结构,由于数据的排序不同有可能是深度很大的二叉树犹如直线连接的节点,因此它是个不稳定的查找方式,搜索的速度由构造元素的顺序决定,顺序不好,速度就不佳,不稳定。

平衡二叉树,就是用来解决查找二叉树的问题的,它的规则是,父节点的左右两棵树的深度差的绝对值不能超过1,并且左右两棵子树叶同样遵循这个规则。二叉树的深度问题解决了,在查找时就不会出现不稳定的状况了。

红黑树,就是实现平衡二叉树的算法,红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

红黑树虽然高效稳定,但实际项目中运用的还是少,首先算法复杂度高,普通的程序员还是要费点心思去研究的,时间成本、人力成本增加。另一方面,因为完全可以用“快速排序”+“二分查找”代替,效率一样而且更加稳定、简单、易用,如果使用优化后的快速排序效率时常会高于红黑树。至少在游戏项目中,是很难看到其应用场景的,但并不代表它没用,树形结构的好处就是有自带有更多的信息,节点中不止存放的是‘值’信息,还有很多与值相关与逻辑相关的数据可提供更好的服务。

B树,是建立在平衡二叉查找树之上的,多叉树。它的节点上有多个值的,且多叉的,且平衡的,查找树。犹如在红黑树之上,建立了多叉的方式,并且比较方式由单一值比较,改为了多值比较。一个节点里的信息是个数组,且它们是有序的,可用二分查找比较和查找,找到中间节点继续往下搜索。

B树会更快吗,从查找上来看与红黑树效率一样,从构建上来看,增加,删除会更复杂,算法上都是使用二分思想所以相差不多。其实B树在游戏里也很少能用到,因为能代替它的算法很多。不过它在文件存储结构上能发挥巨大作用,这也是它被发明的原因,包括B+和B*树都是从B树衍生而来。

无论用得到用不到,思考方式和思考角度是关键,知道了有这些多种角度的思考方式,在平时的算法编写时就有了更多的思路和想法,因为指不定什么时候就从这种思想角度里得出了你要的算法,毕竟需求和环境是多变的,我们需要找到适合的优秀的算法。
四叉树搜索算法

四叉树搜索算法,有点像二叉树的多维度版本,有点类似一维数组上数组分成4块进行查找,但也仅限于此。

四叉树的最重要的理念是空间划分,把一个二维空间划分成多个块来存放,它由树形结构支撑,每个点有四个子节点,这四个子节点代表父节点的四个象限区块,四个子节点加起来代表整个完整的父节点,以此类推下去,每个节点可以有子节点,一旦有就得四个一起有。

在实际运用中,四叉树也是在2D平面空间上的搜索用的比较多,虽然其他领域也有用到,但在2D平面空间划分上更适合。我们可以把一个2D矩形平面想象成,一个分成相等四个大小的矩形,总共四块矩形方块,每块中又再次分成相等大小的四块,直到分到定义的最小块为止,每一块都有自己的父节点和子节点(除了最底部的节点)。

当元素加入这个平面时,也就是加入到了这个四叉树的数据结构中去,从最大的四块开始依次往下推,一直到推到没有子区块的节点上,每个区块都有元素容量。当元素达到最大容量时,节点分裂。把需要搜索和查找的每个元素按这个步骤推入四个子节点。

形成四叉树数据结构后,就可以根据这个数据结构进行查找元素了。比如,在某个位置上查找在相同块内的所有元素。给出坐标后,就能根据四叉树依次推下去最终找到没有子节点的那个节点,获取块上的所有信息。

由于每次元素加入到四叉树时,在每个父节点都会留下相关的信息,所以在父节点上也能得到相关的信息列表。比如把地图分成3级,每一级四块矩形图上都存有相关元素的信息,可以快速得到1,2,3级地图上某块内的所有元素的信息。

四叉树在游戏项目中的运用有,二维平面上的有效碰撞检测搜索范围,地形的有效展示范围,在地图上找人或事务或地点,在地图上找某范围的人或事务或地点,二维平面的寻路网格构建等。

由于四叉树的搜索是建立在元素不移动的状态下进行的,一旦移动就得进行先删除后再加入的操作,如果移动的操作比较频繁,效率将急剧下降。所以四叉树构建的搜索算法,不适合大量元素移动频繁的系统上。而对于那些固定或者说太变动的,如,地形,地块,网格,地点,物体,以及不动的人是比较有效的。
八叉树搜索算法

八叉树与四叉树类似,但在理念上更关注三维空间上的划分。八叉树把一个立方体,纵向和横向各切一刀,分裂成八个相同大小的立方体,每个小立方体也就是子节点,也可以在适当的时候分裂成八个相同大小的小立方体,用树形结构表示每个大大小小的立方体形成了八叉树。

经过树形结构构造,八叉树就很容易用在3D空间中的场景管理,可以很快地知道物体在3D场景中的位置,或测试与其它物体是否有碰撞以及是否在可视范围内。因此八叉树在实际游戏中用到的,有渲染中的渲染裁切,和物理引擎中的碰撞检测。

优秀的算法都是能找到事物特征并且利用好事物特征的算法,不同种类的算法有其自身的理念,混用或合用几个算法也是常有的事,理解和知晓是第一步,灵活运用真的不是一朝一夕的事,若非项目需要所驱动的算法研究通常也只是纸上谈兵,真搬上项目真刀实枪的干时,很多时候都是和底下读几篇文章、敲几个算法是完全两样的,所以我才常听到‘老兵们’常说的一句,适合的才是最好的,和交朋友、谈恋爱是一个道路。

感谢您的耐心阅读

Thanks for your reading

  • 版权申明

    本文为博主原创文章,未经允许不得转载:

    《Unity3D高级编程之进阶主程》第一章,C#要点技术(六) 搜索算法

    Copyright attention

    Please don't reprint without authorize.

  • 微信公众号