度约束欧氏Steiner最小树问题和其求解.pdf

上海理工大学学报 of forScienceand V01．30No．52008 第30卷第5期 J．UniversityShanghai Technology 文章编号：1007—6735(2008)05—0443一06 度约束欧氏Steiner最小树问题及其求解 张瑾1， 丁爱萍2， 马 良1 (1．上海理工大学管理学院，上海200093；2．黄河水利职业技术学院信息3-程系，开封475003) 摘要：在欧氏Steiner最小树的基础上，对每个正则点加上了度约束限制，提出了度约束欧氏Stein— er最小树问题，分析了该问题的特性，给出了该问题的模拟退火和蚂蚁算法求解过程，并使用Del— phi语言编程，在WindowsXP平台上运行通过．通过大量算例的计算结果验证了该问题的实用性 及算法的有效性． 关键词：度约束；欧氏Steiner最小树；算法 中图分类号：022 文献标识码：A the EuclideanSteiner Solvingdegree-constrained minimaltree problem ZHAhl6 3inl，DIIXlG Lian91 Ai．p骨，MA Scienceand 200093，China； (1．FussinessSchool，UniversityofShanghaifor Techno幻gy，Shanghai River Technical ConservancyInstitute，Kaifeng475003，China) 2．DepartmentofInformationEngineering，Yellow Abstract：The EuclideanSteinerminimaltree wasdiscussedbasedonthe degree-constrained problem Euclideanminimaltreewitheach addedwitha constraint．The Steiner point originalbeing degree ofthe was andthe of the propertyproblemanalyzed implementationprocesssolvingproblembyusing and was arecodedin thesimulated theant annealingalgorithm algorithmpresented．Bothalgorithms XP ofnumerical weretestedandtheeffi— andrunoiltheWindowsenvirnment．Series Delphi examples ofthese