| 度约束欧氏Steiner最小树问题及其求解 |
| |
| 引用本文： | 张瑾,丁爱萍,马良.度约束欧氏Steiner最小树问题及其求解[J].上海理工大学学报(社会科学版),2008,30(5). |
| |
| 作者姓名： | 张瑾 丁爱萍 马良 |
| |
| 作者单位： | [1]上海理工大学管理学院,上海200093 [2]黄河水利职业技术学院信息工程系,开封475003 |
| |
| 基金项目： | 国家自然科学基金资助项目(70471065,70871081); 上海市重点学科建设资助项目(T0502); 河南省科技厅资助项目(072400440310) |
| |
| 摘 要： | 在欧氏Steiner最小树的基础上，对每个正则点加上了度约束限制，提出了度约束欧氏Steiner最小树问题，分析了该问题的特性，给出了该问题的模拟退火和蚂蚁算法求解过程，并使用Delphi语言编程，在Windows XP平台上运行通过．通过大量算例的计算结果验证了该问题的实用性及算法的有效性．
|
| 关 键 词： | 度约束 欧氏Steiner最小树 算法 |
Solving the degree-constrained Euclidean Steiner minimal tree problem |
| |
| ZHANG Jin,DING Ai-ping,MA Liang.Solving the degree-constrained Euclidean Steiner minimal tree problem[J].Journal of University of Shanghai For Science and Technilogy(Social Science),2008,30(5). |
| |
| Authors: | ZHANG Jin DING Ai-ping MA Liang |
| |
| Abstract: | The degree-constrained Euclidean Steiner minimal tree problem was discussed based on the Euclidean Steiner minimal tree with each original point being added with a degree constraint.The property of the problem was analyzed and the implementation process of solving the problem by using the simulated annealing algorithm and the ant algorithm was presented.Both algorithms are coded in Delphi and run on the Windows XP envirnment.Series of numerical examples were tested and the efficiency of these algorithms wer... |
| |
| Keywords: | degree-constrained Euclidean Steiner minimal tree algorithm |
|
| 点击此处可从《上海理工大学学报(社会科学版)》浏览原始摘要信息 |
| 点击此处可从《上海理工大学学报(社会科学版)》下载免费的PDF全文 |
