摘要
度约束最小生成树问题属于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.
出处
《巢湖学院学报》
2010年第6期38-42,共5页
Journal of Chaohu University
关键词
最小生成树
量子遗传算法
网络优化
Minimum spanning tree
quantum genetic algorithm
network optimization
