论文摘要
最小生成树问题历史悠久,1926年由Boruvka首次提出,目的是寻求电力线网络的最优经济布局.而度约束最小生成树（Degree-Constrained Minimum Spanning Tree, DCMST）问题仅产生于上世纪八十年代初,由Narula和Ho提出.在现实生活中度约束最小生成树问题很常见,如通讯网络设计中,为防止某些重要节点发生网络故障,导致整个网络处于瘫痪状态,需要对这些重要节点所连接线路的条数加以限制.研究度约束最小生成树问题很有必要.度约束最小生成树的构造型求解方法主要分为两类：一类为古典型的构造方法,如分支限界法,这类方法主要特点是时间复杂度较高,因此很少被采用；另一类为智能型的构造方法,这类方法主要通过智能优化算法来实现,如遗传算法、蚁群算法等.智能型的构造方法近些年中被广泛地采用.本文把遗传算法应用到度约束最小生成树算法的实现过程中,给出一个求度约束最小生成树的WCJ遗传算法.在求度约束最小生成树的遗传算法中,遗传编码起到举足轻重的作用,本文设计的Prufer编码方式以及设置的一个不定长度集合D,可以充分保证产生完全可行的初始种群；设计的校正交叉操作,保证产生可行的子代染色体；设计的打乱式变异、补充变异、两点逆转变异三种变异操作,保证产生可行的子代染色体,拓展搜索空间,有效地防止搜索陷入局部最优状态.算法收敛性分析从理论上保证新算法是可行的,仿真试验的结果则表明新算法效果良好,是有效算法.
论文目录
相关论文文献
- [1].基于最小生成树和聚类算法的旅游线路规划[J]. 测绘技术装备 2016(04)
- [2].改进最小生成树算法在移动自组织网络路由选择中的应用[J]. 沈阳化工大学学报 2016(01)
- [3].一种基于遗传算法的度约束最小生成树求解方法[J]. 曲阜师范大学学报(自然科学版) 2010(01)
- [4].基于遗传算法的广义最小生成树求解与应用[J]. 西华大学学报(自然科学版) 2010(03)
- [5].遗传算法在度约束最小生成树问题中的应用[J]. 湖南环境生物职业技术学院学报 2009(03)
- [6].不确定图最小生成树算法[J]. 智能计算机与应用 2019(06)
- [7].基于最小生成树的G地区铺设光纤优化布局模型[J]. 市场周刊 2018(06)
- [8].基于高维空间稀疏最小生成树自适应覆盖模型的一类分类算法[J]. 模式识别与人工智能 2011(03)
- [9].一种基于似最小生成树的空间聚类算法[J]. 武汉大学学报(信息科学版) 2010(11)
- [10].无线传感网络改进的最小生成树算法[J]. 河南科学 2017(04)
- [11].基于二次最小生成树的光纤布线——以福建师范大学福清分校为例[J]. 内江师范学院学报 2017(08)
- [12].基于最小生成树相似测度的耳廓匹配[J]. 微型机与应用 2014(12)
- [13].基于最小生成树的二维图像深度分配[J]. 数学的实践与认识 2018(09)
- [14].基于最小生成树的网络故障定位算法研究[J]. 山西大同大学学报(自然科学版) 2017(04)
- [15].基于两轮最小生成树的股票网络模型构建[J]. 计算机应用与软件 2017(11)
- [16].基于最小生成树算法的建筑物聚类[J]. 测绘 2017(06)
- [17].基于高阶最小生成树的脑网络分析及对阿兹海默氏症患者的分类[J]. 计算机应用 2017(11)
- [18].基于DCMSTP问题的算法综述[J]. 福建电脑 2015(03)
- [19].基于最小生成树的动态贪婪多播路由算法研究[J]. 硅谷 2009(08)
- [20].最小生成树在动态贪婪多播路由算法中的应用[J]. 重庆文理学院学报(自然科学版) 2009(05)
- [21].基于最小生成树聚类的中文版面分割法[J]. 计算机工程 2008(15)
- [22].新增结点下最小生成树研究[J]. 数学杂志 2010(06)
- [23].一种求解度约束最小生成树问题的优化算法[J]. 软件学报 2010(12)
- [24].基于高序最小生成树的磁共振成像分类方法[J]. 计算机工程与设计 2018(06)
- [25].赋权连通图最小生成树分析研究[J]. 渭南师范学院学报 2015(14)
- [26].度、半径约束最小生成树问题及其算法[J]. 沈阳大学学报(自然科学版) 2012(04)
- [27].蚁群算法求解直径约束最小生成树问题[J]. 红河学院学报 2012(04)
- [28].空间数据的零初始化与障碍空间下的最小生成树实现方法[J]. 武汉大学学报(信息科学版) 2009(01)
- [29].最小生成树在管道铺设中的应用[J]. 信息与电脑(理论版) 2015(19)
- [30].求解广义最小生成树问题的元启发式算法[J]. 交通信息与安全 2012(02)
标签：度约束最小生成树论文; 遗传算法论文; 编码论文; 操作论文; 仿真论文;