CMST问题的新算法

NEW ALGORITHMS OF CMST PROBLEM

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N^2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.

Two new heuristic algorithms are proposed for the CMST (Constrained Minimum Spanning Tree) problem that given N nodes, the input load of each node, a symmetric cost matrix for the links, and the capacity of each link, a spanning tree structure is constructed, under some constraints, to minimize the cost of the resulting tree. Both algorithms have computational complexities bounded by O(N2). It is demonstrated that the costs of resulting tree obtained with either of these new algorithms are lower than those obtained with several existing heuristic algorithms. Further, the computational time required for new algorithms was much less than that for the existing ones.