求解度约束最小生成树问题的启发式算法研究

发布时间：2021-09-28 06:47

　　带有度约束的最小生成树问题存在于工业界的很多应用场景中,如电路芯片设计、通信工程、运输工程、管道工程、排水系统等领域。此外,带有度约束的最小生成树问题与很多重要的问题有着千丝万缕的关系,例如当生成树的度约束变得极为松弛时,该问题就转变成图论中常见的最小生成树问题;然而当生成树中的每一个顶点的度约束固定为2时,该问题则转变为经典的旅行商问题。从计算复杂度方面来讲,带有度约束的最小生成树问题已被证明为NP难度问题,因此不存在多项式时间复杂度的精确算法对其进行求解。本文将围绕求解有度约束的最小生成树问题的高效启发式算法展开研究。针对带有度约束的最小生成树问题的特殊问题结构,本文提出一种基于多目标的禁忌搜索算法对其进行求解。本文的主要工作和创新点包括:首先将关于度的硬约束条件转换为目标函数中的一级目标,使原问题转化为带有二级目标函数的最小生成树问题。其次,设计了基于边交换的邻域动作用于求解该问题。邻域动作每次尽可能改进目标函数中的一级目标或者二级目标,提高了算法的搜索效率。再次,提出了禁忌搜索策略,以达到搜索到全局最优解的目的。当满足解禁策略时,则采用解禁策略接受禁忌动作。最后,采用所提出了的... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：55 页

【学位级别】：硕士

【部分图文】：

算法流程图

图 3-3 边交换动作：a)一棵生成树 b)添加边{1,2}c)删除边{5,8}生成新的生成树至此，我们完成了对 DCMST 问题硬约束的转化、邻域空间的定义、邻域动作的设计等重要问题的讨论。在简单实例中，由权重矩阵可求出该图的最小生成树如图 3-4 所示，图中只有节点 4 违反度约束，对每一条非树边进行检测，当该非树边加入该生成树时，在形成的环中优先去掉减少度约束冲突的边，然后在度约束冲突减少相同的情况下才去掉权重改变最小的边。

【参考文献】：
期刊论文
[1]A new algorithm for degree-constrained minimum spanning tree based on the reduction technique[J]. Aibing Ning a, Liang Ma a, Xiaohua Xiong b a School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China b College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, China.  Progress in Natural Science. 2008(04)



本文编号：3411431