基于prüfer数的遗传算法求解度约束最小树问题  

Genetic algorithm based on prüfer number for solving Degree-Constrained Minimum Spanning Tree Problem

作　　者：牧云志[1] 周根贵[1] 

机构地区：[1]浙江工业大学经贸管理学院,杭州310023

出　　处：《计算机工程与应用》2008年第12期53-56,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(the National Natural Science Foundation of China under Grant No.70671095)

摘　　要：度约束最小树问题属于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.

关 键 词：prüfer数 遗传算法 最小生成树 度约束 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]