附有条件的最小支撑树算法

被引：2

作者：

厍向阳

罗晓霞

机构：

[1] 西安科技大学计算机科学与技术学院

来源：

西安科技大学学报 | 2008年 / 28卷 / 04期

关键词：

最小支撑树; 邻接矩阵; 度约束; 边约束;

D O I：

10.13800/j.cnki.xakjdxxb.2008.04.035

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。

引用

页码：771 / 774

页数：4

共 7 条

[1] 多风机通风系统的网络图自动生成 [J].

吴奉亮 ;

常心坦 ;

李龙清 .

西安科技大学学报, 2006, (03) :293-295+305

[2] 通讯网络中的生成树 [J].

刘联会 .

西安矿业学院学报, 1990, (01) :56-60

[3]

遗传算法与工程设计[M]. 科学出版社 , (日)玄光男,程润伟著, 2000

[4]

数据结构[M]. 清华大学出版社 , 严蔚敏,吴伟民编著, 1997

[5]

运筹学[M]. 清华大学出版社 , 钱颂迪主编, 1990

[6]

On the shortest spanning subtree of a graph and the traveling salesman problem[J] . Joseph B. Kruskal.proc . 1956 (1)

[7]

Shortest connection networks and some generations. Prim R C. The Bell System Technical Journal . 1957

← 1 →