摘要
在赋权连通网络下,给定多种材料及每种材料的费用和拼接费用,以便寻找赋权网络中的一棵Terminal Steiner树,并用给定材料连接此树,使得总费用及材料根数达到最小,记此问题为多材料Terminal Steiner树拼接问题。为了解决Terminal Steiner树拼接问题,首先分析Terminal Steiner树拼接问题是NP问题,不存在多项式时间算法;然后基于Steiner树问题和变尺寸装箱问题的近似算法及算法复杂度,给出多材料的Terminal Steiner树拼接问题的一个近似算法;最后证明算法的近似值及近似算法的时间复杂度。
In the weighted and connected network, a variety of materials, cost of each material, and the splicing cost are given to look for a Terminal Steiner tree in the weighted network. The given materials are used to connect the Terminal Steiner tree, so as to minimize the total cost and the number of materials. This can be called the multi-material Terminal Steiner tree splicing problem. The Terminal Steiner tree splicing problem is analyzed and determined to be the NP problem, in which the polynomial time algorithm does not exist, and then an approximation algorithm of the muhi-material Terminal Steiner tree splic- ing problem is presented based on the approximation algorithm of Steiner tree problem and variable-sized bin packing problem as well as the eomplexity of the algorithm, so as to resolve the Terminal Steiner tree splicing problem. The approximate value of the algorithm and the time eomplexity of the approximation algorithm are demonstrated.
作者
文永松
朱淑娟
庞一成
WEN Yongsong;ZHU Shujuan;PANG Yicheng(School of Mathematics and Statistics, Guizhou University of Finance and Economics, Guiyang 550025, Chin)
出处
《现代电子技术》
北大核心
2018年第10期28-30,共3页
Modern Electronics Technique
基金
国家自然科学基金(11761018)
贵州省科学技术基金(J[2015]2026)~~
