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

摘要：

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

关键词：MPH算法、加权节点、Steiner树、启发式算法、最短路径

所属期刊栏目：34

分类号：TP393.2(计算技术、计算机技术)

在线出版日期：2015-02-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：3414-3416,3457