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

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