现代电子技术2018，Vol.41Issue(10)：28-30,3.DOI:10.16652/j.issn.1004⁃373x.2018.10.007
多材料Terminal Steiner树拼接问题的近似算法研究
Research on approximation algorithm for multi-material Terminal Steiner tree splicing
摘要
Abstract
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 multi-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 complexity of the algorithm,so as to resolve the Terminal Steiner tree splicing problem. The approximate value of the algorithm and the time complexity of the approximation algorithm are demonstrated.关键词
TerminalSteiner树/拼接问题/变尺寸装箱/近似算法/绝对近似比/时间复杂度Key words
Terminal Steiner tree/splicing problem/variable-sized bin packing/approximation algorithm/absolute approx-imate ratio/time complexity分类
信息技术与安全科学引用本文复制引用
文永松,朱淑娟,庞一成..多材料Terminal Steiner树拼接问题的近似算法研究[J].现代电子技术,2018,41(10):28-30,3.基金项目
国家自然科学基金(11761018) （11761018）
贵州省科学技术基金(J[2015]2026)Project Supported by National Natural Science Foundation of China(11761018),Science and Technology Foundation of Guizhou Province(J[2015]2026) （J[2015]2026）
