Steiner最小树问题及其应用.pdfVIP

Vo l8　No15　 A ug. 　2008 第 8卷 　第 15期 　2008年 8月 科 　学 　技 　术 　与 　工 　程 　 (2008) Science Technology and Engineering 　2008　Sci TechEngng 综 　述 数 　学 Ste iner最小树问题及其应用 张 　瑾 1, 2 　马 　良1 ( 1 2 ) 上海理工大学 管理学院 ,上海 200093;河南大学 计算机与信息工程学院 ,开封 475001 摘 　要 　Steiner最小树问题是一个历史悠久的经典的组合优化问题 , 由于应用广泛 ,多年来一直受到研究者的广泛关注 。介 绍了各种 Steiner树问题及其求解算法和实际应用 。 关键词 　Steiner最小树 　　精确算法 　　启发式算法 　　应用 中图法分类号 　O224; 　　　　文献标志码 　A 　　现实生活中经常要求解决这样的问题 , 即将若 后经多位数学家扩展补充 ,最后以瑞士数学家 Stei 干给定点相连并使连线的总长最短 。在网络通信 ner的名字命名为 Steiner 问题 。近年的数学史研究 领域中 ,该问题被一般化地提为 :如果要在 n 个区域 又表明 , Steiner 问题还被大数学家 Gau ss研究过 , 间铺设通信网 , 使得各区域之间能实现信息的共 Gau ss有个做铁路工程师的儿子曾经问过其父亲如 享 ,那么应如何铺设才能使通信线路的总长最短 ? 何用最短的铁路将四座城市连起来 , Gau ss在回信 一般首先想到的可能就是求连接这 n 个点的最小生 中给出了详尽的解答 。 ( ) 由于 Steiner最小树问题在现代生产生活中应 成树 M in im um Sp ann ing Tree—M ST 这种做法 ,但 如果不拘泥于这 n 个点 ,而引入除这 n 个点之外的 用十分广泛 , 因而多年来都是研究者关注的焦点 。 另外几个点的话 ,则有可能使连接各区域的通信线 经典 Steiner树 问题大体包括欧氏的、绝对值距离 路的总长更短 。这是 Steiner 最小树 问题 ( Steiner 的、图的等几个重要方面 ,其中图的 Steiner树应用 M in im um Tree Prob lem ,简记为 SM TP) 的来源 。 范围最广 。 Steiner最小树问题是经典的组合优化问题 ,最 早可以追溯到 17 世纪初 。1634 年 , 数学家 Ferm at 1　平面上的 Ste iner最小树问题 提出这样一个问题 :在欧氏平面上有三个点 , 寻找 一个点使得由该点连接这三个点的距离之和最小 。 11　问题定义 目前研究最多的是平面上的 Steiner最小树 问 ( ) 2008年 4 月 2 1 日收到 国家自然科学基金项目 、