共查询到10条相似文献,搜索用时 62 毫秒
1.
本文考虑到节点度的代价问题 ,提出了广义最小生成树的概念 ,并分析了最小生成树在实际应用中的局限性 .针对一般遗传算法求解该问题的不足 ,提出了自调整的变异算子和混合选择策略 .通过仿真 ,证明了广义最小生成树模型的适用性 .最后将改进前后两种算法的仿真结果进行比较 ,证明了改进后遗传算法的有效性 . 相似文献
2.
给出了最小生成树问题(MST)的一个基于混合DNA计算的遗传算法模型。在该模型中,为了对最小生成树的解进行编码和解码,通过引入DNA计算,提出了一种最小生成树问题的改进遗传算法编码方案,该方案吸收了DNA计算和遗传算法的优点,具有固定的长度。为了搜索需要的最佳编码,引入遗传算法搜索技术,并给出了自适应的交叉算子和变异算子。最后,根据最小生成树问题的特点,通过实例仿真验证了所提出的基于DNA计算的遗传算法的有效性 相似文献
3.
量子遗传算法求解度约束最小生成树 总被引:1,自引:0,他引:1
度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值.针对度约束最小生成树问题,采用量子遗传算法来求解该问题.并对基本的量子遗传算法进行改进.针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较.取得了良好的效果. 相似文献
4.
罗世亮 《赣南师范学院学报》2007,28(3):38-40
考虑到通信网络系统架设费用存在着不确定性,针对修建费用为模糊数的最小生成树问题,本文根据改进的PR IM算法得到通信网络系统中关于模糊费用的一棵最小生成树.这种新算法充分考虑了架设费用的模糊性,它的时间复杂度为O(n2). 相似文献
5.
6.
《洛阳师范学院学报》2015,(8):57-60
针对通信网络的设计,利用最小生成树的KRUSCAL算法与改进的哈密顿回路等方法,建立了最小生成树模型、结点故障的环形改进模型、链条破坏的环形改进模型,运用MATLAB编程计算,得出兼顾可靠性与成本费用的合理优化铺设方案,通过比较不同可靠程度下边际新增费用大小,给出了边际新增费用最小的优化网络结构,并将规划后的网络结构拓扑图直观呈现. 相似文献
7.
求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。 相似文献
8.
冯俊文 《天津大学学报(英文版)》2001,7(2):101-108
每个具有非对称权重的有向图均可用一个称为“扩展表”的矩阵或表格来表示 .讨论了扩展表中的“圈”和“生成表”的概念及其基本特性 ,给出了一种寻找有向图最小生成树的表格方法——最小生成表法 .研究了最小生成表算法在最优能力集扩展问题中的应用 ,给出了一个算法的具体示例 ,并分析了有关的需研究的问题和可能的拓展 相似文献
9.
网络最小生成树问题的贪心解法 总被引:1,自引:0,他引:1
讨论了最小生成树问题的两种贪心算法:Prim算法和Kruskal算法,给出了算法步骤,设计了算法实现的一般模式,并介绍了它们的几种改进算法及时间效率比较。 相似文献
10.
《东南大学学报》2020,(1)
为了修正分层OWL(web ontology language)本体,通过定义新的冲突分层和基于整数线性规划(ILP)的切割函数扩展了核修正算子.基于ILP的模型考虑了最小化线性目标函数的优化问题,适合于修正本体时移除最少数量的公理.基于该切割函数,提出了一个修正算法,将ILP应用到所有最小的不协调保持子集(MIPS)上.该算法虽然能够经常找到用于移除的最少公理,但计算MIPS非常耗时.因此,又提出另一个改进的修正算法用于逐个处理不可满足概念.实验结果表明:提出的基于ILP的修正算法比经常使用的基于碰集树的算法更加高效;改进的修正算法能够达到更高的效率,但可能会删除更多的公理. 相似文献