分区合并Steiner算法

大规模图低耗时

针对大规模图的Steiner树问题，采用分区-合并策略，在大型实例上超越现有最佳算法。

孙明 · Xinyu, Wu · Zhou, Yi · Hao, Jin-Kao · 付樟华

Tsinghua Science and Technology 2025

技术优势

专治大规模图

将输入网络切分成小规模子图分别处理，再自底向上合并，避免了直接在大图上进行全局搜索的高昂代价。

局部优化提质量

在合并过程中对子图内的部分Steiner树进行高效的局部优化，使最终解的质量得到提升。

大规模实例领先

在广泛的基准测试中，该算法在大型实例上优于已知最佳算法，在中小型实例上与之相当。

应用场景

• 大规模网络优化：能对超大规模网络实例高效求解Steiner树，支撑骨干网等核心优化任务。
• 无线传感器网络路由：在大型传感器网络中快速构建最小代价路由骨干，延长网络寿命。
• 通信骨干网设计：为大规模通信网络规划骨干链路，降低布线成本并保证终端全覆盖。
• 卫星网络拓扑：为卫星网络构造连通所有卫星的最小代价连接拓扑，节省星间链路资源。