共查询到17条相似文献，搜索用时 109 毫秒
1.
量子遗传算法求解度约束最小生成树 总被引：1，自引：0，他引：1
度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值.针对度约束最小生成树问题,采用量子遗传算法来求解该问题.并对基本的量子遗传算法进行改进.针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较.取得了良好的效果. 相似文献
2.
求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。 相似文献
3.
本文考虑到节点度的代价问题 ,提出了广义最小生成树的概念 ,并分析了最小生成树在实际应用中的局限性 .针对一般遗传算法求解该问题的不足 ,提出了自调整的变异算子和混合选择策略 .通过仿真 ,证明了广义最小生成树模型的适用性 .最后将改进前后两种算法的仿真结果进行比较 ,证明了改进后遗传算法的有效性 . 相似文献
4.
冯俊文 《天津大学学报(英文版)》2001,7(2):101-108
每个具有非对称权重的有向图均可用一个称为“扩展表”的矩阵或表格来表示 .讨论了扩展表中的“圈”和“生成表”的概念及其基本特性 ,给出了一种寻找有向图最小生成树的表格方法——最小生成表法 .研究了最小生成表算法在最优能力集扩展问题中的应用 ,给出了一个算法的具体示例 ,并分析了有关的需研究的问题和可能的拓展 相似文献
5.
罗世亮 《赣南师范学院学报》2007,28(3):38-40
考虑到通信网络系统架设费用存在着不确定性,针对修建费用为模糊数的最小生成树问题,本文根据改进的PR IM算法得到通信网络系统中关于模糊费用的一棵最小生成树.这种新算法充分考虑了架设费用的模糊性,它的时间复杂度为O(n2). 相似文献
6.
7.
以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树. 相似文献
8.
网络最小生成树问题的贪心解法 总被引：1，自引：0，他引：1
讨论了最小生成树问题的两种贪心算法：Prim算法和Kruskal算法,给出了算法步骤,设计了算法实现的一般模式,并介绍了它们的几种改进算法及时间效率比较。 相似文献
10.
11.
根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。 相似文献
12.
索红军 《渭南师范学院学报》2012,(10):78-80
文章联系实际问题,结合旅行商问题和中国邮递员问题,提出赋权连通图中最小环路遍历路径以及求解该路径的方案.该方案参考最小生成树的普里姆算法,依据狄杰斯特拉算法,通过往返最短路径逐次比较,在赋权连通图中实现寻找最小环路遍历路径. 相似文献
13.
kruskal算法是一种求连通图的最小生成树的算法,无论是采用"避圈法",还是采用"破圈法",都要用到圈的判断,文章基于此,分析提出一种高效实用的判断树中是否存在圈的方法. 相似文献
14.
15.
由聚类所生成的簇是一组数据对象的集合,在同一个类中的对象之间具有较高的相似度,而不同类中的对象差别较大.图的最小生成树具有最优子结构性质,删除最小生成树的最大边后的两颗子树依然分别是两个子图的最小生成树,因此可由生成图的最小生成树获得聚类.此方法适用于所有欧氏空间数据的聚类. 相似文献
16.
遗传算法在网络动态选路中的应用 总被引：1，自引：0，他引：1
陈皓 《株洲师范高等专科学校学报》2004,9(5):36-38
根据安全传输的要求,提出了一种运用遗传算法来实现网络中动态寻路的方法.且结合运用遗传算法求解图的最小生成树的例子,对一个模拟网络拓扑结构的有权无向图进行了编码,为求解过程建立了相应的模型,并对该模型进行了分析. 相似文献