STP协议与生成树设计优化

生成树协议是交换或桥接网络中管理冗余链路和负载均衡的一个关键协议，对交换网络的性能有重大影响。本文详细分析了生成树协议的工作原理，并阐述了生成树设计与优化的方法。     

一种协商式生成树协议

在交换式以太网中,怎样维护无环路的拓扑结构,如何最大限度地缩小网络的转发延迟,是本文的研究重点.笔者提出一种为每个虚拟局域网建造一个树结构的协商式生成树协议.在BPDU中加入标示性能的标志,交换机根据这个标志为每个VLAN生成、维护一个稳定的树结构,使交换机端口由阻止状态到转发状态的延迟明显缩短,提高了网络的实时特性.最后运用多层交换完成虚拟局域网之间的通信.这个算法能够快速收敛,缩小交换机端口的转发延迟,提高网络的实时特性.     

基于最小生成树的动态多播路由算法

提出了基于最小生成树的动态多播路由算法，称之为DPG（dynamic prim-based greedy multicast algorithm)算法，该算法属于不重组的动态多播路由算法。由于在所有节点都是多播节点时，最小生成树是最佳的，因此期望通过该算法产生的多播树的性能在合理的范围之内。结果表明DPG算法是一种平均无效率和最大无效度都在可接受的范围内的一种动态路由算法，尤其在多播节点密度较高时，它的平均无效率和最大无效度都较低。同时DPG算法的平均无效度对网络大小和网络平均节点度数不敏感，DPG算法的另一优点是时间复杂度低，它比贪婪算法和加权贪婪算法都快速。     

最小费用流的生成树算法

本文先用生成树算法,迅速找到一个网络最小费用流的可行初始解,然后再用网络的单纯形解法,得出最小费用流的最优解.由于初始可行解具有优化的成分,又接近最优解,所以对提高运算效率很有益处.     

基于最小度约束下的最小生成树算法

针对网络设计和组合优化中的度约束最小生成树问题,通过引入分裂图以及分裂数的概念,给出了网络G关于v0的最小度支撑树的最小度等于分裂数的结论.并在此基础上提出了一种关于v0的最小度约束条件下的最小生成树算法,最后对算法的正确性给出了证明.算例表明了算法的有效性.     

基于遗传算法的最小生成树算法

以图论和遗传算法为基础 ,提出了一种求最小生成树的改进遗传算法 .该算法采用二进制编码表示最小树问题 ,用深度优先搜索算法进行图的连通性判断 ,并设计出相应的适应度函数、单亲换位算子和单亲逆转算子以及四种控制性进化策略 ,以提高算法执行速度和进化效率 .与Kruskal算法相比 ,该算法能在一次遗传进化过程中获得一批最小生成树 ,适合于解决不同类型的最小树问题     

最小生成树算法的快速实现

给出一种基于向量合并的最小生成树算法 ,它的时间复杂度和空间复杂度分别为O(E)和O(max(E ,V) ) ,算法简洁、快速     

基于蚁群系统的双目标最小生成树算法

带有多个目标的最小生成树问题在实际生活中有着广泛的应用,但用传统方法很难有效地解决,本文提出一种基于多目标决策的蚁群系统求解双目标最小生成树算法,利用两个启发信息来构造新的状态转移规则,并改进了信息素更新规则,指导蚂蚁找到Pareto最优解。试验结果表明,该算法能有效解决双目标生成树问题,与Pareto最优枚举法比较,求解时间减少了。     

基于VB的最小生成树KRUSKAL算法的实现

对求解加权连通无向图最小生成树的KRUSKAL算法进行了探讨,并用VB实现,同时以读取文件的方法输入图,弥补了利用面向过程的程序设计语言在求解最小生成树时输入数据的复杂性。通过可视化的形式显示无向图和最小生成树,使结果直观且容易理解。     

近似最小树的哈希Dijkstra算法

为了解决Dijkstra(DK)算法对大规模数据构造最小树时效率不高的问题,结合局部敏感哈希映射(LSH),针对欧氏空间中的样本,提出了一种近似最小树的快速生成算法,即LSHDK算法.该算法通过减少查找近邻点的计算量提高运行速度.计算实验结果表明,当数据规模大于50 000个点时,LSHDK算法比DK算法速度更快且所计算的近似最小树在维数较低时误差非常小(0.00~0.05%),在维数较高时误差通常为0.1%~3.0%.     

求最小生成树的邻接矩阵法

求图的最小生成树,目前已有多种算法.今介绍一种新的算法——邻接矩阵法,叙述该算法的步骤,进行理论证明,并给出一个说明本算法的实例所述算法形象直观、容易理解、求解过程简便、易于在计算机上实现.特别是它为求解工程上经常遇到的某种“受限最小生成树”提供了新的途径.比如,当PLAN型计算机网络的拓扑结构和其限制条件较为复杂时,使用邻接矩阵法编制其求解的计算机程序结构清晰,调试容易.     

基于最小生成树的切片数据点排序算法

提出一种基于最小生成树的切片数据点排序算法,该算法建立散乱点云空间索引结构,基于该结构快速获取切片邻域数据,依据邻域数据与切片的位置关系将其划分为正负2个区域,通过正负邻域配对点连线与切片求交获取切片数据点,构造切片数据点的无向完全连通图,求解该图最小生成树,并将最小生成树的各分枝首尾相连,实现切片数据点的排序,实例证明该算法可对逆向工程中各种复杂型面切片数据点排序,排序结果准确,算法运行效率高。     

用"破圈法"求全部最小生成树的算法

求连通图的最小生成树是数据结构中讨论的一个重要问题．但在现实生活中，经常遇到如何得到连通图的所有最小生成树．针对此问题，运用“破圈法”思想，对所给的图进行约化，在约化图的基础上，提出了求全部最小生成树的算法，给出了应用例子．     

流体管网中模糊最小树的算法与分析

目的将模糊集应用到管网分析中,研究流体管网中模糊最小树的算法.方法利用全水平截集排序指标(OERI)法对模糊管网中的分支进行排序,在保持网络结构不变的情况下,将网络图论的常规算法适当调整,求得管网的模糊最小树.结果结合算例,既算出了树的模糊阻抗值,又针对无差异、乐观与悲观3种权重情况获得了树的OERI值,实现了模糊最小树算法.结论在保持网络结构不变的情况下,将网络图论的常规算法适当调整,既可求得管网的模糊最小树,又获得了对应不同主观权重函数时树的OERI值.     

基于最小生成树的动态通道布线算法

针对电子设计自动化中低的通道布线布通率,对影响布通率的因素进行了研究,分析了线网布线次序对通道布线结果的影响,比较了静态排序和动态排序的优缺点,基于最小生成树,提出了一种动态通道布线算法.在布线过程中,根据通道已布线状态,计算剩余线网加权后各自的最小生成树,优先选择受已布线线网影响最大的线网进行连接,避免连接点距离较远的线网对连接点距离较近的线网的约束.实验结果表明,对同一个布局,采用相同的布线规则,算法占有空间资源少,比商用软件在通道布线方面具有更高的布通率.     

基于最小生成树的点云数据去噪方法

为了保证重建的模型质量或模型配准的精度,提出采用基于最小生成树的聚类算法将点云数据中的噪点去除,并在尸体股骨上对这种骨表面点云数据的获取方法的可行性和噪点去除方法的有效性进行了验证。实验证明,这种数据获取方法是可行的,所采用的噪点去除方法也是有效的。