带有度约束的最小耗费生成树的分支限界算法

最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。     

最小生成树的算法

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

最小生成树的算法——减枝算法

最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树.Kruskal算法和Prim算法是求最小生成树的常用算法.本文讨论了一种新的算法.     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法——最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。     

矩阵形网络图最小生成树算法的优化

最小连接问题在网络优化中有广泛的应用,找到快速有效的算法来构造最小生成树是解决问题的关键。该文提出了一种构造算法,在存储结构和排序方法两方面进行了改进。从理论上分析了算法的计算复杂度,并实际测试了算法运行时间。结果表明该算法较现有算法有了很大提高。     

最小比率生成树的竞争决策算法

最小比率生成树是找出目标函数形式为两个线性函数比值最小的生成树,例如总代价与总收益比值最小的生成树。当不限制分母的符号时,这是一个NP-hard问题。在分析最小比率生成树数学性质的基础上,提出了最小比率生成树的竞争决策算法。为了防止算法陷入局部最优,采用edge_exchange操作来增加算法的搜索范围。为了验证算法的有效性,采用无关和相关两种策略产生测试数据,并使用Delphi 7.0实现了算法的具体步骤。     

最小生成树问题的数学模型及其证明

对图论中赋权无向图中最小生成树问题的数学模型,分析了建立的过程,并证明了各边不构成圈的一个等价条件,最后推广到有向图中,为用数学软件求解图论问题打下基础。     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

基于Prim算法和Kruskal算法的最小生成树优化研究

文章从目前最常见的两种在图最小生成树算法,即Prim和Kruskal算法,展开了阐述和分析,运用了大量的数据和实例对这两种计算方法进行了分析和研究。通过试验并对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图。     

A faster distributed protocol for constructing a minimum spanning tree

This paper studies the problem of constructing a minimum-weight spanning tree (MST) in a distributed network. This is one of the most important problems in the area of distributed computing. There is a long line of gradually improving protocols for this problem, and the state of the art today is a protocol with running time due to Kutten and Peleg [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27], where Λ(G) denotes the diameter of the graph G. Peleg and Rubinovich [D. Peleg, V. Rubinovich, A near-tight lower bound on the time complexity of distributed MST construction, in: Proc. 40th IEEE Symp. on Foundations of Computer Science, 1999, pp. 253-261] have shown that time is required for constructing MST even on graphs of small diameter, and claimed that their result “establishes the asymptotic near-optimality” of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].In this paper we refine this claim, and devise a protocol that constructs the MST in rounds, where μ(G,ω) is the MST-radius of the graph. The ratio between the diameter and the MST-radius may be as large as Θ(n), and, consequently, on some inputs our protocol is faster than the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27] by a factor of . Also, on every input, the running time of our protocol is never greater than twice the running time of the protocol of [S. Kutten, D. Peleg, Fast distributed construction of k-dominating sets and applications, J. Algorithms 28 (1998) 40-66; preliminary version appeared in: Proc. of 14th ACM Symp. on Principles of Distributed Computing, Ottawa, Canada, August 1995, pp. 20-27].As part of our protocol for constructing an MST, we develop a protocol for constructing neighborhood covers with a drastically improved running time. The latter result may be of independent interest.     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

A simpler minimum spanning tree verification algorithm

The problem considered here is that of determining whether a given spanning tree is a minimal spanning tree. In 1984 Komlós presented an algorithm which required only a linear number of comparisons, but nonlinear overhead to determine which comparisons to make. We simplify his algorithm and give a linear-time procedure for its implementation in the unit cost RAM model. The procedure uses table lookup of a few simple functions, which we precompute in time linear in the size of the tree.     

A filter-and-fan algorithm for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.     

Degree-constrained minimum spanning tree problem with uncertain edge weights

Uncertainty theory has shown great advantages in solving many nondeterministic problems, one of which is the degree-constrained minimum spanning tree (DCMST) problem in uncertain networks. Based on different criteria for ranking uncertain variables, three types of DCMST models are proposed here: uncertain expected value DCMST model, uncertain α-DCMST model and uncertain most chance DCMST model. In this paper, we give their uncertainty distributions and fully characterize uncertain expected value DCMST and uncertain α-DCMST in uncertain networks. We also discover an equivalence relation between the uncertain α-DCMST of an uncertain network and the DCMST of the corresponding deterministic network. Finally, a related genetic algorithm is proposed here to solve the three models, and some numerical examples are provided to illustrate its effectiveness.     

基于GPU的并行最小生成树算法的设计与实现*

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的minreduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。     

改进的最小生成树自适应分层聚类算法

针对传统最小生成树聚类算法需要事先知道聚类数目和使用静态全局分类依据,导致聚类密度相差较大时,算法有效性下降,计算复杂度大等问题,提出一种改进的最小生成树自适应分层聚类算法,根据最近邻关系,自动为每个聚类簇设定独立的阈值,使之适应分布密度相差较大的情况,并能自动确定聚类数目。实验表明,算法具有较好的性能,尤其对数据密度分布不均匀的情况也能得到较好的聚类结果。