摘要
最小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.
出处
《通信学报》
EI
CSCD
北大核心
2002年第11期35-40,共6页
Journal on Communications
基金
浙江省综合信息网技术重点实验室基金资助项目
