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

摘要

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