共查询到17条相似文献,搜索用时 78 毫秒
1.
《信阳师范学院学报(自然科学版)》2015,(4):597-600
针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案. 相似文献
2.
孙小军 《内蒙古师范大学学报(自然科学版)》2016,(4):445-448
针对一类度约束最小生成树问题,基于传统最小生成树问题的Prim算法,设计了一种求解算法.该算法在保证网络中指定节点的度不变的前提下,构造了网络关于指定节点的最大度最小生成树.与经典的Gloveklingman算法进行了仿真比较,结果表明,该算法是求解度约束最小生成树问题的一种有效算法. 相似文献
3.
图的最小生成树已经有了好算法,但当图增加或删去几条边或少数几条边的边调整时,最小生成树的边、权可能发生变化,用原算法寻找最小生成树时,显得比较麻烦.利用破回路算法给出一个简单的 方法.并给出了相应的示例. 相似文献
4.
最小生成树问题是运筹学网络优化中一个常见的基本问题.提出了一种新的求最小生成树的矩阵算法,此算法可以不必在原图上进行操作而得到最小生成树,过程简单易懂. 相似文献
5.
提出了一种关于最小生成树的生成法,该算法与传统的prim算法及kruskal算法比较,有更低的计算复杂性. 相似文献
6.
提出了一种关于最小生成树的生成法,该算法与传统的prim算法及kruskal算法比较,有更低的计算复杂性. 相似文献
7.
武继刚 《烟台大学学报(自然科学与工程版)》1994,(1):32-35
利用Kruskal和Prim算法的优点,从图的每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法。算法的最坏复杂度为O(m-n)logm),平均复杂度为O((m-n)logn),就复杂度的常数因子而言,均优于Kruskal算法与kim算法,其中m为图的边数,n为图的顶点数。 相似文献
8.
最小生成树的应用及有效算法 总被引:1,自引:0,他引:1
计算机的应用将现代数学理论引入了工程技术中。通过最小生成树在矿井通风设计和改造最优化方面的作用,阐明了最小生成树的广泛应用,并且结出了求解最小生成的简单易行的算法。 相似文献
9.
Kruskal算法和Prim算法是求最小生成树的常用算法.设计了这两种算法的C语言程序,并通过实例表明了算法的应用. 相似文献
10.
随着天然气输配管网规模的大型化,管网系统进一步优化对提高运行的经济效益和利用率显得非常重要.采用受限最小生成树算法对城镇燃气管网布局进行优化,并将该算法与最小生成树算法(prim)进行了比较.仿真表明,该算法实用性强,对城镇天然气系统工程投资的评估预算有重要的参考价值. 相似文献
11.
在图的一种双链式存储结构的基础上提出了一种扩展的双链式存储结构.并用这种存储结构实现了图的最小生成树算法,与其它存储结构相比具有更好的灵活性. 相似文献
12.
目的给出无向图G(V,E),|V|=n的最小生成树在单指令流多数据流(SIMD)机器、Incomplete-hypercube上的并行算法.方法利用有p个处理器的不完全超立方网络,求加权无向连通图G(V,E),|V|=n的最小生成树.结果与结论若处理器的个数为p,则其时间复杂性为t(n)=O(n2/p·(lbp)),成本C(n)=O(n2(lbp)),它几乎是最优的. 相似文献
13.
以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树. 相似文献
14.
探讨了如何将遗传算法应用于度约束的最小生成树问题,并给出了相应的算法.实验结果表明,这种用遗传算法解决度约束的最小生成树问题是有效的. 相似文献
15.
度、半径约束最小生成树问题及其算法 总被引:1,自引:0,他引:1
成鹰 《沈阳大学学报:自然科学版》2012,24(4):63-65,73
提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果. 相似文献
16.
基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log~2n+Klogn~*)时间及O(n~2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n~2)处理器,这里n 是图的顶点数. 相似文献
17.
提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果. 相似文献