度约束欧氏Steiner最小树问题及其求解  

Solving the degree-constrained Euclidean Steiner minimal tree problem

作　　者：张瑾[1] 丁爱萍[2] 马良[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]黄河水利职业技术学院信息工程系,开封475003

出　　处：《上海理工大学学报》2008年第5期443-448,共6页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(70471065,70871081);上海市重点学科建设资助项目(T0502);河南省科技厅资助项目(072400440310)

摘　　要：在欧氏Steiner最小树的基础上,对每个正则点加上了度约束限制,提出了度约束欧氏Steiner最小树问题,分析了该问题的特性,给出了该问题的模拟退火和蚂蚁算法求解过程,并使用Delphi语言编程,在Windows XP平台上运行通过.通过大量算例的计算结果验证了该问题的实用性及算法的有效性.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 were validated.

关 键 词：度约束 欧氏Steiner最小树 算法 

分 类 号：O22[理学—运筹学与控制论]