共查询到18条相似文献,搜索用时 62 毫秒
1.
2.
3.
4.
《信阳师范学院学报(自然科学版)》2015,(4):597-600
针对当赋权连通图中存在权值相同的多条边时,传统的Kruskal算法不能计算出全部的最小生成树,提出了求解最小生成树的改进算法.实验结果表明,改进算法可以得到一个赋权连通图的所有最小生成树,进而为决策者提供更全面的最优决策方案. 相似文献
5.
给定一个(有向)连通图G=(V,E),寻找k棵支撑树(边可以重复),满足树中的边在k棵树中出现的次数不超过其容量,考虑2个问题:①k棵支撑树的费用之和尽可能小;②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法,同时应用该算法,问题②是是近似的。 相似文献
6.
7.
传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。 相似文献
8.
最小生成树的应用及有效算法 总被引:1,自引:0,他引:1
计算机的应用将现代数学理论引入了工程技术中。通过最小生成树在矿井通风设计和改造最优化方面的作用,阐明了最小生成树的广泛应用,并且结出了求解最小生成的简单易行的算法。 相似文献
9.
为了简化对运筹学中最小支撑树模型编写简单计算机程序来实现求解,设计了一种新的简便算法----"节点列表判定法"。该算法是用节点来表述网络图的边,并从节点列表中找到了构成圈的特征结构,以此作为判定条件来确定网络图是否有圈存在。在最小支撑树模型的求解过程中,选择网络图中权数最小的边为支撑树的边。每选择一条边就判定一次,若判定有圈存在则放弃最后选择的边,反复选择边并判断,直到所有已选择的边都不构成圈且总边数等于点数-1,那么新确定的支撑树就是一个最小支撑树。这种新的算法已经Excel-BVA编制求解程序验证了其正确性、实用性和快捷性。 相似文献
10.
11.
根据图论的要求和模糊集合的原理对现代城域通信网络进行优化,以连接距离最短、网络建设费用最少、网络可靠性最高为目标建立模型,并且保证网络连通性、辐射状运行等约束条件,得到通信网络架设规化的近似最优解.研究了网络建设中一些界限不分明的因素,建立了模糊最小生成树模型,它具有简单、实用、实时性强等特点,在现代城域网络建设中有很强的适用性. 相似文献
12.
在图的一种双链式存储结构的基础上提出了一种扩展的双链式存储结构.并用这种存储结构实现了图的最小生成树算法,与其它存储结构相比具有更好的灵活性. 相似文献
13.
为了解决伪装技术的设计难题,并实现伪装图像与环境背景高度融合的设计目的,提出了均值漂移与最小生成树相结合的图像分割方法.利用该方法不仅能够准确提取基于背景的迷彩斑点图案,而且相比其他方法其运算速度也有很大提高;这样既保证了整个迷彩设计的准确性,也增强了伪装效果的实时性.通过量化颜色直方图提取背景的主色,将其作为迷彩图案的显示颜色.最后将斑块与颜色相结合生成最终的迷彩图像.实验结果验证了该方法的有效性. 相似文献
14.
最小生成树的又一种生成法 总被引:2,自引:0,他引:2
提出一种关于最小生成树的生成法, 此方法是在一个给定的网络中,首先找到一条权最大的边,判断此边的 2个结点在不经过此边的情况下是否有另路相通,若相通则删除此边.否则, 保留此边,再寻找所剩余的权最大的边, 作类似的处理,直到在原网络中剩下的边为顶点数减 1 为止, 由此即得最小生成树.与传统的 Prim 算法及 Kruskal 算法相比较, 此法在点多而边数相对较少的网络中,能迅速地找到它的最小生成树. 相似文献
15.
16.
以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树. 相似文献
17.
Kruskal算法和Prim算法是求最小生成树的常用算法.设计了这两种算法的C语言程序,并通过实例表明了算法的应用. 相似文献
18.
通过Prim算法的研究寻找局部最优解的迭代过程,用布尔向量U和V-U表示集合中的边,根据权值的关系找到快速有效的算法来构造最小生成树.从理论上分析了算法的性质和时间复杂度.通过实例分析, 证明了该算法有效性并在现实生活中得到的广泛应用. 相似文献