期刊论文

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

中文

数学的实践与认识

1000-0984

2015

19

175-185

湖南省高等学校科学研究项目（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 p...