摘要
度约束最小树问题属于NP-完全问题,是一类比较难解的问题,但在现实中具有非常重要的应用价值。探讨了如何将基于prüfer数的遗传算法应用于该问题,并给出了相应的算法。采用C语言和MATLAB的混合编程实现该算法,数值分析的结果显示了遗传算法求解该问题的有效性及其应用价值。
The Degree-Constrained Minimum Spanning Tree problem（DCMST） is difficult to be solved because of its NP-hard complexity.But it’s very important because of its value in practice.In this paper,we discuss how to solve this problem by means of genetic algorithm based on prüfer number.We present it by using C and MATLAB programs.The numerical analysis shows the effectiveness of the genetic algorithm in practice.
出处
《计算机工程与应用》
CSCD
北大核心
2008年第12期53-56,共4页
Computer Engineering and Applications
基金
国家自然科学基金(the National Natural Science Foundation of China under Grant No.70671095)
关键词
prüfer数
遗传算法
最小生成树
度约束
prüfer number
Genetic Algorithm（GA）
Minimum Spanning Tree（MST）
degree-constrained
