一种构建最优二叉查找树的贪心算法

分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。     

改进的赫夫曼树（Huffman Tree）和赫夫曼编码（Huffman Code）构造算法

通过将待排序的数据应用快速排序算法进行排序处理,使得赫夫曼算法（Huffman Algorithm）65时间复杂度从O（n^2）降低为O（n＊log2n）。当用于构造赫夫曼树（Huffman Tree）的结点比较多时,可较大的提高程序的运行时间。     

旅行商问题中巡回路径的数据结构

旅行商问题中巡回路径的数据结构对局部启发式算法的效率起着非常关键的作用。巡回路径的数据结构必须能够查询一条回路中每个城市的相对顺序,并且能够将一条回路中的部分城市逆序。分析了数组表示法、伸展树表示法和两级树表示法表示巡回路径时各种基本操作的实现过程及时间复杂度。数组表示法能够在常数时间内确定一条回路中每个城市的相对顺序,但是最坏情况下完成逆序操作需要Ω（n）时间,不适用于大规模的旅行商问题。伸展树表示法执行查询和更新操作的平摊时间复杂度是O（logn）,适用于极大规模的旅行商问题。而两级树表示法在最坏情况下每一个更新操作的时间复杂度是O（n^0.5）,适用于大规模的旅行商问题。     

一种基于蜂群原理的划分聚类算法*

针对现有的大部分划分聚类算法受聚类簇的个数K的限制,提出一种基于蜂群原理的划分聚类算法。该方法通过引入蜂群采蜜机制,将聚类中心视为食物源,通过寻找食物源的自组织过程来实现数据对象的聚集。在聚类的过程中引入紧密度函数来评价聚类中心（局部）,引入分离度函数来确定最佳聚类簇的个数（全局）。与传统的划分聚类算法相比,本算法无须指定聚类个数即可实现聚类过程。通过仿真实验表明,本文提出的算法不但对最佳聚类数有良好的搜索能力,而且有较高的准确率：算法时间复杂度仅为O（n*k3）(k<相似文献   

基于动态规划的最优二叉搜索树算法的改进

基于动态规划的最优二叉搜索树构造算法,选择子问题的划分时,r值的循环范围过大,存在不足。本文对此改进,缩小了r值的范围,算法时间复杂度由O(n3)减小至O(n2),并对两个算法的优劣进行了比较。     

低代价最短路径树快速算法的时间复杂度研究

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!) e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n) e)更能体现FLSPT算法高效率.     

基于改进搜索策略的Live-Wire医学图像分割算法

Live-Wire 分割算法提供了一种精确的、可再现的交互式医学图像分割方法。Live-Wire算法中最优路径的搜索通常采用Dijkstra算法,其时间复杂度为O[n2]。提出从两个方面对Live-Wire医学图像分割算法的搜索策略进行改进以提高Live-Wire算法的实时性：（1）在最短路径的搜索过程中应用二叉堆排序,使算法的时间复杂度从原来的O[n2]降为O[n ln n];（2）在最短路径搜索中加入到达目标节点即停止的限制条件,可明显减少搜索节点数,使算法的时间复杂度远小于O[n ln n]。经算法分析及实验表明,搜索策略的改进可显著提高Live-Wire算法的运行效率。     

一种新的删除红黑树的结点的算法

提出一种新的删除红黑树的结点的算法，其主要思想是先自上而下处理某些子树再删除结点，不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。     

一种基于前缀编码的树生成算法

为了使树生成算法更为通用且效率更高,提出一种基于前缀编码的树生成算法.算法中的节点采用前缀编码的数据结构,便于用户对树中节点及其下层子节点上的关联数据进行快速查询和统计.由于在构造树之前已采用先根遍历的方式对节点进行了排序,同时建树过程中记录了最近各层节点的信息,因此无需搜索节点的上下层信息就可直接建立起树,大幅提高了建树效率,算法时间复杂度为O(n).该算法无需额外的数据预处理即可构造任意子树,且不会增加算法复杂度.     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

Fully dynamic maintenance of k-connectivity in parallel

Given a graph G=(V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of G in the parallel setting for k=2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: (1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n^3/4) processors per update and query. (2) It is shown that the biconnectivity problem can be solved in O(log^{2 n} ) time using O(nα(2n, n)/logn) processors per update and O(1) time with a single processor per query or in O(log n log_n/^m) time using O(nα(2n, n)/log n) processors per update and O(logn) time using O(nα(2n, n)/logn) processors per query, where α(.,.) is the inverse of Ackermann's function. (3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log_n/^m+logn log log n/α(3n, n)) time using O(nα(3n, n)/log n) processors per update and O(1) time with a single processor per query. (4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to Ω(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n^3/4) processors. All the proposed algorithms run on a CRCW PRAM     

一种有效的最小生成树并行算法

本文基于三维网孔处理机阵列，运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法。     

一种新的删除HB(k)树的结点的算法

Foster的删除HB(k)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退。提出一种新的删除HB(k)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。举例说明新算法的执行过程。证明新算法是正确的。与Foster的删除HB(k)树的结点的算法相比,新算法不涉及辅助栈的使用。设n是HB(k)树的结点的个数。新算法的时间复杂性是O(log2n),与Foster的删除HB(k)树的结点的算法的相同。实验结果表明新算法的平均执行时间比Foster的删除HB(k)树的结点的算法短。新算法的空间复杂性是O(1),比Foster的删除HB(k)树的结点的算法低。     

基于凸剖分的多边形窗口线裁剪算法

以不增加新点的方式将多边形剖分为一些凸多边形,并基于这些多边形的边建立二叉树进行管理.裁剪计算时,根据二叉树快速地找到与被裁剪线有相交的凸多边形,然后运用高效的凸多边形裁剪算法进行线裁剪.该方法能自适应地降低裁剪计算的复杂度,使其在O(logn)和O(n)之间变化,并在大多数情况下小于O(n),其中n是多边形边数.虽然该方法需要进行预处理,但在许多应用(如多边形窗口对多边形的裁剪)中,其总执行时间(包括预处理时间和裁剪时间)比已有的不需要预处理的裁剪算法少很多.     

存在完整性约束时最小化树模式查询的算法

树模式是查询树型结构数据如XML和LDAP的天然模型。在一个给定的数据库上进行查询，查询的效率很大程度上依赖于查询的大小。因此，在查询前删除查询中的冗余分支，使查询最小化是非常重要的。在树型结构数据库中，存在孩子必需、后代必需和子类3种完整性约束是十分普遍的。针对存在这3种完整性约束的情况，基于扩展的模拟概念提出了一种复杂度为O（n^2）的最小化树模式查询算法（n为树模式查询的节点数）。分析结果表明这个算法的效率要远高于同类算法。     

一个求图的连通分支的并行算法

已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log²n)时间、O(n²/logn)处理器;而在SIMD—CRCW共享存贮模型上需O(logn)时间、O(n²)处理器,建议的算法同著名的Hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂     

一类扩展的Steiner树优化问题及其应用

本文提出了一个计算机网络通信和分布式系统中的一类扩展的Ｓｔｅｉｎｅｒ树问题．对此问题设计了两个求其最优解的算法．这两个算法的时间复杂性分别是Ｏ（３（ｋ－１）·ｎ＋２（ｋ－１）·ｎ２）和Ｏ（２（ｎ－ｋ）·ｎ２）．其中，ｋ是一棵Ｓｔｅｉｎｅｒ树需支撑的给定顶点的个数．     

Fast dynamic intersection searching in a set of isothetic line segments

We reconsider the (isothetic) line segment intersection searching problem: Given a set S of n horizontal and vertical line segments and a query segment q, find all t segments in S intersecting q. We describe the first dynamic solution for this problem which achieves O(log n + t) query time. This, however, has to be paid by O(n log² n) space requirements and O(log³ n) update time. If segments are defined over a grid of size N × N (the semidynamic case), then the problem can be solved in O(logN + t) query time, O(n log² N) space and O(log² N) update time. The solution is based on the use of segment tree and range tree and the halfobject technique.     

基于特征路径的XML文档变化检测算法

由于在线信息变化频繁,XML文档变化快速检测成为Internet查询系统、搜索引擎以及连续查询系统的关键技术。目前国际上的研究主要集中于有序模式的XML文档比较,针对有序模式最好的算法复杂度为O(nkgn),其中n为文档的长度,而针对无序模式为多项式时间复杂度,为提高处理效率,提出一种基于特征路径的变化检测算法,将传统标号树匹配问题转换为基于特征路径的无重复路径标号树的匹配问题,同时适于有序和无序两种模式,复杂度为O(n),其中n为文档结点的个数．实验证明KF-Diff 能够非常高效地比较XML文档。     

基于数据网格的书法字k近邻查询

提出一种在数据网格环境下的书法字k近邻查询方法.当用户在查询结点提交一个查询书法字和k时,首先以一个较小的查询半径,在数据结点进行基于混合距离尺度的书法字过滤,然后将过滤后的候选书法字以“打包”传输的方式发送到执行结点,在执行结点并行地对这些候选书法字进行距离(求精)运算,最终将结果书法字返回到查询结点.当返回的书法字个数小于k时,扩大半径值,继续循环,直到得到k个最近邻书法字为止.理论分析和实验表明,该方法在减少网络通信开销、增加I/O和CPU并行、降低响应时间方面具有较好的性能.