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

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

逼近最优的更新最小生成树的并行算法

给定连通无向赋值图G=(V,E),|V|=n,|E|=m,当G的某边的赋值改变时,必引起其最小生成树的改变。本文给出了一个快速有效地求新的最小生成树的并行算法,时间为O(log m),处理器个数为O(m~(1/2)),计算模型为EREW-PRAM。预处理也仅需O(log~2m)时间O(m)个处理器,与求初始最小生成树的耗费一样。我们的算法的并行时间与处理四个数的乘积为O(m~(1/2) log m)(此问题已知最快的串行算法时间为O(m~(1/2)))。     

最小生成树的算法

本文提出了一个利用集合运算生成最小生成树的算法。研究了实现集合运算的数据结构及施加在这个结构上的算法。该算法利用公式分组排序。利用路径压缩的方法进行查找，并运算。该算法将有Ｎ个顶点Ｅ条边的无向连通网络生成最小生成树的期望时间是Ｏ。     

网孔处理机阵列上最小生成树算法

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n~2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n~2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子.     

基于Sollin算法的最小生成树求解

Prim算法、Kruskal算法和Sollin算法是最小生成树的典型构造算法。这三个算法均基于贪婪策略。Prim和Kruskal算法在本专科数据结构课程中有详细的介绍,而Sollin算法涉及较少。本文基于边集数组这一存储结构,详细说明了Sollin算法的步骤与实现。     

基于数据结构的最小生成树算法

数据结构是计算机科学的算法理论基础和软件设计的技术基础,在计算机领域中有着举足轻重的作用。本文以邻接矩阵作为图的存储结构,指出如何在计算机上实现克鲁斯卡尔算法,并分析所设计算法的时间复杂度。     

最小生成树问题

本文给出了最小生成树的计算方法,并用此算法解决了一实例。     

树的后根遍历的一种并行算法

本文运用并行计算的PRAM模型研究树的遍历问题，提出了树的后根遍历的一种并行算法，并给出了一个实例。     

最小生成树是否唯一

最小生成树是图论的经典问题,求最小生成树以及求最小生成树的权值和得到了足够关注,而很少人去研究最小生成树是否唯一.对于给定的图而言,因为最小生成树的权值和是确定的,所以最小生成树不唯一当且仅当最小生成树的形状不唯一.本文提出判断最小生成树是否唯一的三种方法并且对它们给予分析和评价.     

大图数据上顶点驱动的并行最小生成树算法

最小生成树(minimum spanning tree, MST)是图论中最为经典算法之一.基于MST结构的聚类、分类和最短路径查询等复杂图算法,在效率和结果质量方面均有显著提高.然而,随着互联网的迅猛发展,图数据规模也变得越来越大,包含千万甚至上亿个顶点的大图数据越发常见.因此,如何在大图数据上实现查询处理和数据挖掘算法已成为亟待解决的问题之一.除此之外,由于大图数据的动态性特征,如何动态地维护算法结果也势必成为最受关注的问题之一.针对目前集中式的最小生成树算法无法解决海量和动态图数据的问题,首先提出了分区Prim(partition Prim, PP)算法,基于此提出了顶点驱动的并行MST算法——PB(PP Boruvka)算法,并论证了PB算法的正确性.另外,基于MapReduce和BSP框架实现了PB算法.针对只删除动态图特征,提出了MST维护算法,以实现高效的增量计算.对提出的计算和维护算法进行了代价分析和比较.最后,使用真实和模拟数据集,验证了PB算法和维护算法的有效性、高效性和可扩展性.     

基于自然邻居和最小生成树的原型选择算法

K最近邻居是最流行的有监督分类算法之一。然而,传统的K最近邻居有两个主要的问题:参数K的选择以及在大规模数据集下过高的时间和空间复杂度需求。为了解决这些问题,提出了一种新的原型选择算法,它保留了一些对分类贡献很大的关键原型点,同时移除噪声点和大多数对分类贡献较小的点。不同于其他原型选择算法,该算法使用了自然邻居这个新的邻居概念来做数据预处理,然后基于设定的终止条件构建若干个最小生成树。基于最小生成树,保留边界原型,同时生成一些具有代表性的内部原型。基于UCI基准数据集进行实验,结果表明提出的算法有效地约简了原型的数量,同时保持了与传统KNN相同水平的分类准确率;而且,该算法在分类准确率和原型保留率上优于其他原型选择算法。     

一种带控制节点的最小生成树聚类方法

综合考虑对象间相对距离和高等级对象对低等级对象的集聚效应这两种聚类影响因素，提出了一种带控制节点的最小生成树聚类方法。该方法用聚类对象间距离为权构建一棵最小生成树，将树中高等级节点作为分割最小树时选取被打断边的控制因素，使本次分割而成的两子树都包含控制节点，且被打断的边是在此条件下的最长边，最终使每棵子树包含且仅包含一个控制节点。检验自构建数据和地震数据的聚类结果证明，该方法在某些情况下能够较好地揭示数据分布的真实规律。     

Efficient determination of the k most vital edges for the minimum spanning tree problem

We study in this paper the problem of finding in a graph a subset of k edges whose deletion causes the largest increase in the weight of a minimum spanning tree. We propose for this problem an explicit enumeration algorithm whose complexity, when compared to the current best algorithm, is better for general k but very slightly worse for fixed k. More interestingly, unlike in the previous algorithms, we can easily adapt our algorithm so as to transform it into an implicit enumeration algorithm based on a branch and bound scheme. We also propose a mixed integer programming formulation for this problem. Computational results show a clear superiority of the implicit enumeration algorithm both over the explicit enumeration algorithm and the mixed integer program.     

最大生成树算法和决策式算法相结合的中文依存关系解析

基于最大生成树解析算法和决策式解析算法的互补关系,提出了最大生成树解析算法和决策式解析算法相结合的中文依存关系解析方法。结合方法利用Nivre模型的依存关系解析结果和依存度修正最大生成树模型有向边的权重,再搜索最大生成树作为依存树。使用宾州中文树库中的4 500句语料作十折交叉测试,结合模型的依存关系正确率达到了86.49%。结果表明该文提出的结合方法有效地提高了的中文依存关系解析性能。     

一种新的求解度约束最小生成树的遗传算法

染色体编码是遗传算法的关键内容,编码的优劣并直接影响算法的性能.提出了基于过程控制的生成树编码方法--PC编码.PC码为定长的整数向量,使用PC编码求解特定生成树问题时,首先选定的一个有效算法,并将修改为可控算法,然后用编码向量控制算法的运行过程,从面得到唯一生成树.为了求解度约束最小生成树(DCMST)问题,在D-Prim算法的基础上,设计r过程可控的度约束生成树构造PC-Prim算法.给出了以PC-Prim算法作为译码器的求解DC-MST问题的遗传算法.仿真结果表明遗传算法求解精度和运行时间均优于参与其他算法.     

基于密度的最小生成树聚类算法研究

基于密度的方法是一种相当有效的聚类方法,能够发现任意形状的聚类,对噪声数据不敏感,但是聚类结果严重依赖于用户参数的合理选择。针对其存在的问题,将最小生成树理论与基于密度的方法相结合,提出了一种基于密度的最小生成树聚类算法。通过构造、分割最小生成树得到确定样本空间划分的最小生成子树;根据子树特性,产生局部密度参数;并对生成子树进行局部密度聚类。理论分析和应用结果表明。该算法不仅体现了基于密度聚类方法的优点,聚类结果不依赖于用户参数的选择,使数据聚类更合理,特别是对大型数据库非常有效;也体现了数据分区的思想,使其可以并行执行,进一步提高了信息处理的时空效率和性能。     

求解多目标最小生成树问题的改进算法

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.     

一种基于网格和最小生成树的数据流聚类算法

针对CluStream算法对非球状簇聚类的不足,同时基于均匀网格划分的聚类算法多数是以降低聚类精度为代价来提高聚类效率,给出了一种新的数据流聚类算法一GTSClu算法,该算法是基于网格的最小生成树(MST)数据流聚类算法.算法分为在线处理与离线聚类两部分,并运用了网格拆分与最小生成树技术,可以有效排除噪声数据,发现任意...     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.