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

An improved algorithm for Steiner trees

作　　者：余燕平[1] 仇佩亮[1] 

机构地区：[1]浙江大学信息与电子工程学系,浙江杭州310027

出　　处：《通信学报》2002年第11期35-40,共6页Journal on Communications

基　　金：浙江省综合信息网技术重点实验室基金资助项目

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

关 键 词：STEINER树 启发式算法 多播路由算法 MPH算法 NP完全问题 多播树 通信网络 

分 类 号：TN915[电子电信—通信与信息系统]