基于加权节点的Steiner树启发式算法

• 作者: 王小龙 赵礼峰
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: MPH算法 加权节点 Steiner树 启发式算法 最短路径
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 网络与通信
• 页码范围: 3414-3416,3457
• 页数: 4页
• 分类号: TP393.2
• 字数: 3519字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2014.12.3414

摘要

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择.为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法.该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树.对STEINLIB标准数据集中的部分数据进行计算,结果表明:NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	王小龙	南京邮电大学理学院	2	9	2.0	2.0