模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

双向选择排序算法

为丰富O(n²)阶排序算法的种类,以更好地服务于教学科研和日常应用,提出了一种新的排序算法-双向选择排序算法.通过数学方法分析得知:该算法的时间复杂度为O(n²),空间复杂度为O(1).通过实验对比得知:在相同条件下,该算法的运行时间平均为冒泡排序的27%、简单选择排序的62%、直接插入排序的88%.     

Improved `Order-N' Performance Algorithm for the Simulation of Constrained Multi-Rigid-Body Dynamic Systems

This paper presents an algorithm for the efficient numerical analysisand simulation of modest to heavily constrained multi-rigid-body dynamicsystems. The algorithm can accommodate the spatial motion of generalmulti-rigid-body systems containing arbitrarily many closed loops inO(n + m)operations overall for systems containing n generalizedcoordinates, and m independent algebraic constraints. The presentedapproach does not suffer from the performance (speed) penaltyencountered by most other of the so-called `O(n)' state-spaceformulations, when dealing with constraints which tend to actually showO(n + m + nm + nm ²+ m ³) performance. Additionally, these latterformulations may require additional constraint violation stabilizationprocedures (e.g. Baumgarte's method, coordinate partitioning, etc.)which can contribute significant additional computation. The presentedmethod suffers less from this difficulty because the loop closureconstraints at both the velocity and acceleration level are directlyembedded within the formulation. Due to these characteristics, thepresented algorithm offers superior computing performance relative toother methods in situations involving both large n and m.     

Clamshell Casting

A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed by a rotation once the liquid has hardened. We consider the case where the object to be manufactured is modeled by a polyhedron with combinatorial complexity n of arbitrary genus. The cast consists of exactly two parts and is removed by a rotation around a line in space. The following two problems are addressed: (1) Given a line of rotation l in space, we determine in O(nlog n) time whether there exists a partitioning of the cast into exactly two parts, such that one part can be rotated clockwise around l and the other part can be rotated counterclockwise around l without colliding with the interior of P or the cast. If the problem is restricted further, such a partitioning is only valid when no reflex edge or face of P is perpendicular to l, the algorithm runs in O(n) time. (2) An algorithm running in O(n ⁴log n) time is presented to find all the lines in space that allow a cast partitioning as described above. If we restrict the problem further and find all the lines in space that allow a cast partitioning as described above, such that no reflex edge or face of P is perpendicular to l, the algorithm’s running time becomes O(n ⁴ α(n)). All of the running times are shown to be almost optimal.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

Fast heuristic algorithms for rectilinear steiner trees

A fundamental problem in circuit design is how to connectn points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP-complete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have anO(n logn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching inO(n ²) total time. However, it is shown that the latter approach runs inO(n ^3/2) expected time, forn points selected from anm×m grid. Empirical results are presented for problems up to 10,000 points.     

An Almost Quadratic Time Algorithm for Sparse Spliced Alignment

The sparse spliced alignment problem consists of finding a chain of zero or more exons from O(n) prescribed candidate exons of a DNA sequence of length O(n) that is most similar to a known related gene sequence of length n. This study improves the running time of the fastest known algorithm for this problem to date, which executes in O(n ^2.25) time, or very recently, in O(n ²log ² n) time, by proposing an O(n ²log n)-time algorithm.     

Efficient Graph-Theoretic Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System

We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n ²) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n ³/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n ²) processors. No previous algorithm was known for these latter problems on the LARPBS.     

Efficient parallel algorithms for breadth first spanning forests of general graphs

Ghosh and Bhattacharjee propose [2] (Intern. J. Computer Math., 1984, Vol. 15, pp. 255-268) an algorithm of determining breadth first spanning trees for graphs, which requires that the input graphs contain some vertices, from which every other vertex in the input graph can be reached. These vertices are called starting vertices. The complexity of the GB algorithm is O(log² n) using O{n ³) processors. In this paper an algorithm, named BREADTH, also computing breadth first spanning trees, is proposed. The complexity is O(log² n) using O{n ³/logn) processors. Then an efficient parallel algorithm, named- BREADTHFOREST, is proposed, which generalizes algorithm BREADTH. The output of applying BREADTHFOREST to a general graph, which may not contain any starting vertices, is a breadth first spanning forest of the input graph. The complexity of BREADTHFOREST is the same as BREADTH.