| 一种改进的Steiner树启发式算法 |
| |
| 引用本文： | 余燕平,仇佩亮. 一种改进的Steiner树启发式算法[J]. 通信学报, 2002, 23(11): 35-40 |
| |
| 作者姓名： | 余燕平 仇佩亮 |
| |
| 作者单位： | 浙江大学,信息与电子工程学系,浙江,杭州,310027 |
| |
| 基金项目： | 浙江省综合信息网技术重点实验室基金资助项目 |
| |
| 摘 要： | 最小Steiner树问题是NP完全问题，关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在MPH算法基础上，对于经过某些关键节点的短路径优先考虑，提出了KBMPH算法，从而实现更多链路的共享。在随机网络上的仿真结果表明，极大多数情况下，在准Steiner树的网络费用KBMPH算法优于MPH算法，KBMPH算法的复杂度为O（n^3）。
|
| 关 键 词： | Steiner树 启发式算法 多播路由算法 MPH算法 NP完全问题 多播树 通信网络 |
| 文章编号： | 1000-436X(2002)11-0035-06 |
| 修稿时间： | 2001-08-20 |
An improved algorithm for Steiner trees |
| |
| YU Yan-ping,QIU Pei-liang. An improved algorithm for Steiner trees[J]. Journal on Communications, 2002, 23(11): 35-40 |
| |
| Authors: | YU Yan-ping QIU Pei-liang |
| |
| Abstract: | Minimum Steiner tree problem is NP complete problem. There are theoretic and realistic significance to research heuristic for Steiner problem. In this paper, a new algorithm KBMPH in which some short paths which pass through some key nodes are more likely to be chosen first is presented. It is based on MPH algorithm. The simulation results on random networks show that in almost all cases the cost of KBMPH trees is lower than that of MPH algorithm. The complexity of KBMPH is )(3nO. |
| |
| Keywords: | multicast routing algorithm Steiner tree MPH algorithm NP complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
