摘要
传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。
The traditional algorithm of minimum spanning tree algorithm is invalidation facing the minimum spanning tree question confined in degree, the minimum spanning tree question in dynamic condition and the minimum spanning tree question confined in edge set, in practice. Genetic algorithm can solve the minimum spanning tree confined in degree, but it take on poor efficiency and complex coding. The models of the minimum spanning tree algorithm confined in conditions are generated. The three minimum spanning tree algorithms confined in conditions is put forward based on traditional algorithm. The algorithms are validated and compared, and show the minimum spanning tree algorithm confined in conditions is completely feasible and effective.
出处
《西安科技大学学报》
CAS
北大核心
2008年第4期771-774,共4页
Journal of Xi’an University of Science and Technology
基金
国家自然科学基金资助项目(40572165)
陕西省教育厅专项科研计划项目(08JK354)
关键词
最小支撑树
邻接矩阵
度约束
边约束
minimum spanning tree
adjacency matrix
degree confining
edge set confining
