| 图的Steiner最小树的竞争决策算法 |
| |
| 引用本文： | 熊小华,刘艳芳,宁爱兵.图的Steiner最小树的竞争决策算法[J].上海理工大学学报,2012,34(5):461-465. |
| |
| 作者姓名： | 熊小华 刘艳芳 宁爱兵 |
| |
| 作者单位： | 1. 上海第二工业大学计算机与信息学院,上海,201209
2. 上海理工大学管理学院,上海,200093 |
| |
| 基金项目： | 国家自然科学基金资助项目，上海市重点学科建设资助项目 |
| |
| 摘 要： | 图的Steiner最小树问题是一个著名的NP难题,在通讯网络、VLSI等工程实践中有着重要的应用.在分析图的Steiner最小树问题数学性质的基础上,提出了图的Steiner最小树的竞争决策算法.为了验证算法的有效性,求解了OR-Library中的基准问题,测试结果表明了算法具有较好的求解效果.
|
| 关 键 词： | 竞争决策算法 Steiner最小树 图 降阶 |
Competitive Decision Algorithm for the Steiner Minimal
Tree Problem in Graphs |
| |
| XIONG Xiao hu,LIU Yan fang and NING Ai bing.Competitive Decision Algorithm for the Steiner Minimal
Tree Problem in Graphs[J].Journal of University of Shanghai For Science and Technology,2012,34(5):461-465. |
| |
| Authors: | XIONG Xiao hu LIU Yan fang and NING Ai bing |
| |
| Affiliation: | 1College of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China; 2 Business School,University of Shanghai for Science and Technology,Shanghai 200093,China) |
| |
| Abstract: | The Steiner minimal tree problem in graphs(GSTP) is a well known NP hard problem.Its applications can be found in many areas,such as telecommunication network design,VLSI design,etc.A competitive decision algorithm was developed to solve the GSTP.The mathematical properties of GSTP were analysed,which can be used to scale down the size of original problem and accelerate the algorithm.To assess the efficiency of the proposed competitive decision algorithm,it was applied to a set of benchmark problems in the OR Library.In terms of computation times,our algorithm clearly outperforms other heuristics for the Steiner problem in graphs,while obtaining better or comparable solutions. |
| |
| Keywords: | competitive decision algorithm Steiner minimal tree problem graph reduction |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《上海理工大学学报》浏览原始摘要信息 |
|
点击此处可从《上海理工大学学报》下载全文 |
|
