量子遗传算法求解度约束最小生成树  

QUANTUM GENETIC ALGORITHM FOR DEGREE-CONSTRAINED MINIMUM SPANNING TREE

作　　者：朱晓虹[1] 

机构地区：[1]福建对外经济贸易职业技术学院,福建福州350001

出　　处：《巢湖学院学报》2010年第6期38-42,共5页Journal of Chaohu University

摘　　要：度约束最小生成树问题属于NP完全问题,但在现实中具有非常重要的应用价值。针对度约束最小生成树问题,采用量子遗传算法来求解该问题。并对基本的量子遗传算法进行改进。针对度约束最小生成树问题的特征,设计了一种新的量子编码方式,保证算法获得可行解;并与深度优先搜索的思想结合,保证得到树的连通性;通过数值试验验证新算法的可行性,并与其他算法进行比较,取得了良好的效果。Degree-constrained minimum spanning tree problem is NP complete,but in reality has very important value.degree-constrained minimum spanning tree problem using quantum genetic algorithm to solve the problem.And the basic quantum genetic algorithm is improved.For degree-constrained minimum spanning tree problem characteristics,the design of a new quantum encoding algorithm to ensure access to feasible solutions;and ideas with the combination of depth-first search,which guarantees connectivity of the tree;through numerical tests validate the new algorithm is feasible sex,compared with other algorithms,and achieved good results.

关 键 词：最小生成树 量子遗传算法 网络优化 

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