启发式进化规划求解Steiner树问题

Solving Steiner Tree Problem with Heuristic Evolutionary Programming

求解 Steiner树对通信网络点对多点路由优化问题有重要意义 ,已被证明是 NP- complete的 .通过把图形简化技术、进化规划方法和 KMB启发式算法相结合 ,提出了一种求解 Steiner树问题的新方法 ,提高了算法的效率 .仿真结果表明 ,本算法是有效的 ,性能优于传统的启发式算法 .

Searching Steiner tree is important for optimizing the multicast routing in communication networks, which is proved to be NP complete. Combining the KMB heuristic algorithm with evolutionary programming algorithm, this paper presented a heuristic evolutionary programming algorithm to solve the Steiner tree problem. The simulations show that the algorithm is effective.