一种改进的Steiner树启发式算法

被引：16

作者：

余燕平

仇佩亮

机构：

[1] 浙江大学信息与电子工程学系

[2] 浙江大学信息与电子工程学系浙江杭州

[3] 浙江杭州

来源：

通信学报 | 2002年 / 11期

关键词：

多播路由算法; Steiner树; MPH算法; NP完全问题;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

最小Steiner树问题是NP完全问题,关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在 MPH算法的基础上,对于经过某些关键节点的短路径优先考虑,提出了KBMPH算法,从而实现更多链路的共享。在随机网络上的仿真结果表明,极大多数情况下,在准Steiner树的网络费用上KBMPH算法优于MPH算法,KBMPH算法的复杂度为)(3nO。

引用

页码：35 / 40

页数：6