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

Steiner tree heuristic algorithm based on weighted node

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

Minimum Steiner tree problem is a NP complete problem, and widely used in communication network point to multi-point routing. In order to realize more link sharing, reduce the cost of the desired Steiner tree, an algorithm named NWMPH （ Node Weight based Minimum cost Path Heuristic） was proposed to solve the Steiner tree based on weighted node. The algorithm constructed a weighted formula of nonregular points, for each nonregular point weighting value. According to the weights of modifying the link cost. By modifying the cost shortest path in order to connect all regular points, get the minimum tree containing all regular points. For part of the data to calculate STEINLIB standard data set, the results show that： NWMPH algorithm and MPH algorithm used basically the same time. The cost of NWMPH algorithm to get Steiner tree is less than that of MPH algorithm. NWMPH algorithm uses less time and costs less to get Steiner tree than KBMPH algorithm.