一种基于边交换的贪心算法求解md-MST问题  

A Greedy Algorithm to solve md-MST Problem Based on Edgeexchange

作　　者：赵磊[1] 刘辉[1] 魏书堤[1] 陈坚祯[1] 林睦纲[1] 

机构地区：[1]衡阳师范学院计算机系,湖南衡阳421001

出　　处：《数学的实践与认识》2015年第19期175-185,共11页Mathematics in Practice and Theory

基　　金：湖南省高等学校科学研究项目(14C0159);衡阳市工业支撑计划项目(2012KG74);湖南省科技计划项目(2014FJ3061)

摘　　要：通过对最小度限制最小生成树(md-MST)问题性质进行分析,提出了一种基于边交换的贪心算法.算法先用贪心算法生成一棵生成树ST,然后对生成树ST经过边交换调整,得到满足问题约束条件的可行解,再对生成树ST进行进一步边交换优化,得到md-MST问题的最优解或接近最优解的近似解.实验证明,算法能在短对间内求出大规模顶点随机图的md-MST,是一种非常实用的求解md-MST问题的精确算法.Analyzing the md-MST problem,a greedy algorithm is put forward.The algorithm uses the greedy algorithm to generate a spanning tree ST,adjusts the spanning tree ST by edge exchange and gets a feasible solution to meet the problem constraints,then optimizes the spanning tree ST by further edge exchange and gets optimal solution or close to the optimal approximate solution.Experiments show that,this algorithm can calculate the mass random graph of md-MST vertices in a short period of time,it is a very practical and accurate algorithm for solving md-MST problems.

关 键 词：最小度限制最小生成树 贪心 边交换 最优解 

分 类 号：O157.5[理学—数学]