快速动态优先搜索树的实现及其应用

对形如([x1:x2],[-∞:y])的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O(n),插入、删除操作的时间复杂度为O(logn),搜索复杂度为O(logn+k)。

无向图的无序深度优先生成树判定算法探究

深度优先搜索树的判定是图论中的一个重要算法，它的算法的优化将给一些其它的图论算法带来高效解决的契机。本文就深度优先搜索树的判定算法从判定条件的给出及其串行算法的设计，到对该算法利用欧拉遍历方法并行优化，得到更好的成本更优的并行算法。

卫星网络基于广度优先树的报文扩散算法

卫星网络ISL子网的拓扑结构具有动态性、周期性和可预知性,时间离散化类的路 由算法是卫星网络的主流路由算法之一。由于ISL子网是网格状、存在物理环路的网络,运行 过程中有大量的信令报文需要从某一颗卫星扩散到整个ISL子网,为避免环路路径和重复报 文问题,提出基于广度优先搜索生成树的报文扩散算法。仿真结果证明算法正确有效。

代数码书分级分段优化搜索方法研究

代数码书作为一种流行的固定码书结构,其搜索方法直接影响解码语音质量及计算复杂度。本文提出了一种代数码书分级分段优化搜索GSOS(Graded and Subsection Optimization Search)方法。GSOS方法融合了脉冲替代法、分段搜索及分级优化方法的优点,通过创建优质的初始码书,达到提高初始码书质量的目的,并将码书矢量的乘法运算用分段子码书的加法运算替代,同时将脉冲按贡献不同进行分级,由此提高脉冲替代优化的搜索效率;将该方法用于自适应多速率宽带语音编码器AMR-WB固定码书搜索阶段,实验结果表明,所提出的搜索方法可使固定码书搜索计算量降为深度优先树搜索方法的13.75%,但解码语音质量只降低了4.01%,主观听觉感受基本感觉不出差异。

单向链路无线传感器网络的强连通多跳控制集

强连通控制集常被用来代表具有不同传输范围的无线传感器网络的虚拟骨干,较小的虚拟骨干更能高效地进行数据收集和节约无线网络的能量。为了计算强连通控制集,提出了一种新的多跳宽度优先搜索树强连通控制集算法(d-hop BFS_SCDS)。该算法首先使用贪婪策略找到一个多跳控制集(d-DS),然后利用宽度优先搜索树连接d-DS中的节点形成一个强连通多跳控制集。该算法的近似比为(2.4d 2+3.6d+1.2)(dk+1/2)2,其中k是网络的传输范围比。仿真实验表明该算法是有效的,符合预期的结果。

基于NAND Flash存储器的磨损均衡DP算法优化

双池DP(Dual Pool)算法对于NANDFlash的磨损均衡控制水平较高,但是磨损均衡过程较长,磨损均衡分布不均,第一个磨穿块容易较早出现。为了解决这些不足之处,在吸收双池算法磨损控制思想的基础上,提出一种基于优先搜索树(PST)的磨损均衡思想,在块搜索策略和垃圾回收策略等方面进行优化。实验结果表明,算法继承了磨损均衡控制水平较高的优点,磨损均衡过程相比双池算法降低70%,系统资源利用率降低40%,NAND Flash使用寿命提高了30%。

染色数为5和6的图中的圈长

Moore和West提出问题:每一个(k+1)-临界的非完全图中是否存在一个模k的意义下长度为2的圈.这里证明了更强的结论:对于k=4,5,每一个(k+1)-临界的非完全图中一定存在模k的意义下所有长度的圈.