共查询到18条相似文献，搜索用时 390 毫秒
1.
2.
以图论和遗传算法为基础,给出了一个改进的求最小生成树的算法,提出了"无性生殖"的方式,舍弃了逆转算子,改进了换位算子,调整了选择算子,更简单,因而编程更容易,效率更高.使用该算法可以在较短的时间内以较高的概率获得一组最小或次小生成树,而传统算法一般只能得到一个最小生成树. 相似文献
3.
本文对于有向图的存储模式进行了研究。在邻接矩阵和邻接表的基础之上，提出了一种新的有向图存储结构一扩展邻接矩阵，并研究了建立该矩阵的算法。扩展邻接矩阵存储模式同时具有邻接矩阵、邻接表和十字链表三种传统存储结构分别可以快速从有向图获得不同信息的优点。扩展邻接矩阵为有向图的应用，提供了一种高效的存储方案。 相似文献
4.
最小生成树问题的Kruscal算法的一种实现方法 总被引：1，自引：0，他引：1
本文讨论了针对带权连通图的一种可行性存储结构———单链表结构的构造问题 ,并研究了在该结构上构造最小生成树的算法 .算法已在机器上得到了实现 相似文献
5.
求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。 相似文献
6.
根据数据结构中求一个带权无向连通图的最小生成树算法的特点,文章给出了Kruskal算法的一个简便而完整的C语言实现。特别是对不连通子图的刻画,只引进了一个一维数组就解决了问题。 相似文献
7.
本文考虑到节点度的代价问题 ,提出了广义最小生成树的概念 ,并分析了最小生成树在实际应用中的局限性 .针对一般遗传算法求解该问题的不足 ,提出了自调整的变异算子和混合选择策略 .通过仿真 ,证明了广义最小生成树模型的适用性 .最后将改进前后两种算法的仿真结果进行比较 ,证明了改进后遗传算法的有效性 . 相似文献
8.
9.
给出了最小生成树问题（MST）的一个基于混合DNA计算的遗传算法模型。在该模型中,为了对最小生成树的解进行编码和解码,通过引入DNA计算,提出了一种最小生成树问题的改进遗传算法编码方案,该方案吸收了DNA计算和遗传算法的优点,具有固定的长度。为了搜索需要的最佳编码,引入遗传算法搜索技术,并给出了自适应的交叉算子和变异算子。最后,根据最小生成树问题的特点,通过实例仿真验证了所提出的基于DNA计算的遗传算法的有效性 相似文献
10.
量子遗传算法求解度约束最小生成树 总被引：1，自引：0，他引：1
度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值.针对度约束最小生成树问题,采用量子遗传算法来求解该问题.并对基本的量子遗传算法进行改进.针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较.取得了良好的效果. 相似文献
11.
研究了给定一个连通图,如何确定其Wiener数最小的生成树问题。Dobrynin等构造了超立方体的两类Wiener数“很小”的生成树,并进一步猜想这两类树都是Wiener数最小的生成树。利用归纳推理及递归关系,对更一般的且具有良好拓扑性质和较高网络模型应用价值的乘积图,如G1×G2、Kmn等,构造了相应的生成树并计算了它们的Wiener数的值,以期获得这些乘积图Wiener数最小的生成树。这些结果推广了Dobrynin关于超立方体的结果。 相似文献
12.
kruskal算法是一种求连通图的最小生成树的算法,无论是采用"避圈法",还是采用"破圈法",都要用到圈的判断,文章基于此,分析提出一种高效实用的判断树中是否存在圈的方法. 相似文献
13.
遗传算法在网络动态选路中的应用 总被引：1，自引：0，他引：1
陈皓 《株洲师范高等专科学校学报》2004,9(5):36-38
根据安全传输的要求,提出了一种运用遗传算法来实现网络中动态寻路的方法.且结合运用遗传算法求解图的最小生成树的例子,对一个模拟网络拓扑结构的有权无向图进行了编码,为求解过程建立了相应的模型,并对该模型进行了分析. 相似文献
14.
针对Apriori算法寻找频繁项集问题,提出了一种基于有向图的频繁集挖掘算法DGFM,该算法将事务数据库表示成二进制矩阵,利用有向图的思想,将频繁项的二进制位串作为有向图的权值,再将二进制矩阵用邻接表存储,通过搜索邻接表来生成频繁项集,最后试验证明该方法比Apriori算法具有更高的效率和性能. 相似文献
15.
李兴芳 《四川职业技术学院学报》2011,21(6):101-103
将动态时间弯曲距离（DTW）的差异矩阵一一对应于点阵,按DTW定义的行走规则对该点阵连线定向,使所对应点阵成为一个有向图,然后使用一个加权技巧对该有向图的边加权后得到一个加权有向图,于是把求DTW的精确计算问题等价地转化为求一个有向图起点到终点的最短路长,从而使图论中求两点间最短路径的方法如目前公认的经典Dijkstra算法均可用于求DTW,因此间接地找到了精确计算DTW的一个新方法. 相似文献
16.
针对Glover-Klingman算法运行时间长的缺点,对Glover-Klingman算法进行了改进,改进后的算法能快速地找到最小度限制树.仿真结果表明了新算法的有效的性,且仿真结果与新算法的预期效果是一致的. 相似文献
17.
样本数据分类是医学研究中常见的工具。本文提出了一种新的数据分类思想和方法。在分析分类过程及其主要矛盾的基础上，提出了极大λ-截子图的概念。作为示范，建立了三个基于最小生成树的图论模型，并分析了其在研究营养与疾病的关系以及基因分类中的应用。最后讨论了图论在医学中的应用前景。 相似文献
18.
解释结构模型被广泛应用于医疗、教育等领域,但相关理论发展较为缓慢。为加快解释结构模型的计算速度,丰富解释结构模型相关理论,通过对系统各要素所对应有向图的本质关系进行分析,对该模型中的级间划分方法作更深一步解析并给出优化算法,发现有向图中若不存在回路,则有向图汇点对应的是最高级要素集合中的要素,因此汇点可以从缩减可达矩阵中直接找出,从而能对复杂系统要素更快地进行分层。对应的优化算法相比传统方法减少了一倍左右的计算量,并通过实证分析进行验证。该研究结果为解释结构模型方法优化提供了一种新诠释。 相似文献