基本信息
- 项目名称：
- 几类特殊斯坦纳最小树问题的研究
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- A．机械与控制（包括机械、仪器仪表、自动化控 制、工程、交通、建筑等） B．信息技术（包括计算机、电信、通讯、电子等） C．数理（包括数学、物理、地球与空间科学等） D．生命科学（包括生物、农学、药学、医学、健 康、卫生、食品等） E．能源化工（包括能源、材料、石油、化学、化 工、生态、环保等）
- 详细介绍：
- 斯坦纳最小树问题（即对于平面上已知的若干个点，允许添加一些其它点，将它们连接起来，使得总连线长度最小）是组合优化的一个重要问题，它是许多实际问题的某种抽象，具有广泛的应用前景。 本项目通过3个点和4点分布在正方形顶点上的斯坦纳最小树的设计与论证，归纳得到斯坦纳最小树的4条基本性质及其连线总长度的一些结论，并由此得到了斯坦纳最小树的一个判定方法。在此基础上，首先讨论了各种情形的一般的3个点和4个点的斯坦纳最小树，给出其算法并交由MATLAB软件运行；然后分别设计出点分布在若干个正方形或正三角形顶点上的斯坦纳最小树，给出了一些应用实例。同时计算出一些特殊的斯坦纳最小树的连线总长度与它们的最小生成树连线总长度的比值。经比较可知，在点数和布局类似的情况下，一般来说点分布在正三角形网络图的斯坦纳最小树比正方形网络的斯坦纳最小树更优。 基于对若干特殊斯坦纳最小树的研究，本项目最后给出了一般的斯坦纳最小树设计的一些设想，即将已知点近似地分布在一个正三角形网络的顶点上，并在正三角形的中心寻找可能的斯坦纳点。并给出了需进一步讨论的相关问题，比如5点的斯坦纳最小树问题及其算法；由正n边形n个顶点及其中心的这(n+1)点的斯坦纳最小树等。 有关几类特殊的斯坦纳最小树的设计与算法等最优化研究成果可以为国民经济有关决策提供理论依据与实践参考，从而创造社会效益和经济效益。
作品图片
作品专业信息
撰写目的和基本思路
- 斯坦纳最小树是组合优化的重要问题，具有广泛的应用前景。通过本作品研究，探讨斯坦纳最小树的基本性质和判定方法，给出几个点数较少的斯坦纳最小树，设计其算法并交由计算机实现；在此基础上，设计出几类点数规模较大的、点分布在正三角形和正方形顶点上的几类特殊的斯坦纳最小树，并对连线长度的优劣加以讨论。同时力求给出一般的斯坦纳最小树设计的想法，并把这些网络优化设计应用于实际。
科学性、先进性及独特之处
- 本项目在有关研究的基础上，对几个简单斯坦纳最小树进行严格论证，归纳出一般斯坦纳最小树的基本性质和判定方法，构造了几类特殊斯坦纳最小树，并给出算法，该算法经MATLAB软件运行结果与设计图吻合。其独特之处在于：设计了3点和4点的斯坦纳最小树及其算法，给出了全部的点分布在若干个正三角形或正方形顶点上的各种情形（包括部分边长不等或某些顶点不全包括）的斯坦纳最小树，提出了一般斯坦纳最小树的设计思路。
应用价值和现实意义
- 本项目探讨了有关斯坦纳最小树的初步理论及算法，可为斯坦纳最小树的理论方面提供参考，给出的路线安排的最优化研究成果可为有关部门决策提供依据，从而获得直接的社会效益和经济效益。
学术论文摘要
- 斯坦纳最小树问题是组合优化的一个重要问题，它是许多实际问题的某种抽象，具有广泛的应用前景。通过3个点和4点分布在正方形顶点上的斯坦纳最小树的设计与论证，归纳出斯坦纳最小树的4条基本性质及其连线总长度的一些结论。在此基础上，首先讨论了各种情形的一般的3个点和4个点的斯坦纳最小树，给出其算法并交由MATLAB软件运行；然后分别设计出点分布在若干个正方形或正三角形顶点上的斯坦纳最小树，给出了一些应用实例，同时计算出一些特殊的斯坦纳最小树的连线总长度与它们的最小生成树连线总长度的比值，经比较可知，在点数和布局类似的情况下，正三角形网络图的斯坦纳最小树比正方形网络的斯坦纳最小树更优。基于对若干特殊斯坦纳最小树的研究，最后给出了一般的斯坦纳最小树设计的一点设想，即将已知点近似地分布在一个正三角形网络的顶点上，并在正三角形的中心寻找可能的斯坦纳点。
获奖情况
- 1．2010年度浙江省大学生科技创新活动计划（新苗人才计划）立项项目 “几类特殊斯坦纳最小树问题的研究”成果； 2.俞胜涛，交叉口信号配时的优化设计，科学技术与工程，第10卷，第35期2010年12月； 3.张莲莲 黄忠裕 俞胜涛,几类特殊的费马点问题及其初等解法，中国科教创新导刊，2011，第23期； 4.“几类特殊斯坦纳最小树问题的研究”获温州大学第四届“挑战杯”大学生课外学术科技作品竞赛一等奖。
鉴定结果
- 2010年度浙江省大学生科技创新活动计划立项项目 “几类特殊斯坦纳最小树问题的研究” （项目编号：2010R424038），项目负责人张莲莲,成员：俞胜涛 尹秀芬 吴培蕾 朱刘辉，指导老师：黄忠裕）。
参考文献
- [1]张亚明 ，刘玉峰 Steiner问题的研究及进展 燕山大学学报 1996\ 01 [2]堵丁柱 谈谈斯坦纳树 中国科学院应用数学研究所；1998\01 [3]翁稼丰 正多边形顶点集上的斯坦纳最小树 应用数学学报 1985\ 02 [4] 蒋君伟,唐璞山 一种生成直角斯坦纳树的算法 复旦学报(自然科学版) 1986\03 [5]杨凌云 图的steiner最小树问题及其求解 电脑知识与技术 2009\ 25 [6]越民义 程丛电 关于Steiner问题的一个注记—连接五点之最小网络的一种寻优方案(英文) 运筹学学报 2010\ 01 [7]梁兆健 Steiner树问题中正则点分布与Steiner点性质 国防科学技术大学 2005-11-07 [8]堵丁柱 关于Steiner树的Gilbert-Pollak猜想的证明 中国科学院院刊 1993\ 03期 [9]杨凌云 图的steiner最小树问题及其求解 电脑知识与技术 2009\ 25 [10]杨振骏 关于Steiner最短树算法的改进 江苏电机工程 1997\ 01 [11]张瑾,马良 Steiner最小树问题及其应用 科学技术与工程 2008\ 15
同类课题研究水平概述
- 19世纪初，斯坦纳提出了斯坦纳最小树问题（记为SRT），进行了初步研究，得出了相关的性质，并证明添加斯坦纳点的斯坦纳最小树，往往比不添加斯坦纳点的最小生成树的长度更短些，即若以Lm(R)和Ls(R)分别表示点集R的最小生成树和斯坦纳最小树的长度，必有Ls(R)≤Lm(R)。自19世纪以来，很多学者对几类特殊的斯坦纳最小树问题进行了讨论和研究，并发表了相关研究成果。1968年，吉尔伯特和波兰克提出猜想 ，此猜想在1990年被堵丁柱和黄光明利用凸分析方法得以证明。从算法复杂性角度考虑一般的斯坦纳问题，加里、格厄姆和约翰森在1977年证明其属于NP完全问题，即人们不能期望找到求解一般斯坦纳最小树的多项式算法。 R.Courant and H.Robbins在《WHAT IS MATHEMATICS?》一书中提到了几个正三角形网络图的斯坦纳最小树及连线长度的一些结论。杨凌云在《图的Steiner最小树问题及其求解》中主要讨论了图的Steiner最小树问题，并给出了近似算法，该算法是在破圈法的基础上改进的。张亚明和刘玉峰在《Steiner问题的研究及进展》中详细的介绍了Steiner问题及其几个主要研究方向的进展情况，探讨了有关Steiner问题各时期的研究特点，并且给出了一些相关的性质，该文较全面地对一些特殊点集上的SRT发表了自己的想法。F•K•Hwang、丁吉豫、宋国栋、堵丁柱在《欧式斯坦纳最小树的分解定理》中从另一个侧面研究了斯坦纳问题，他们认为现有的算法都不能解多于三个点的这种问题，他们提出分解定理对于扩大可解问题的范围非常有帮助。越民义、程从电在《关于Steiner问题的一个注记——连接五点之最小网络的一种寻优方案》中给出了一个采用简单几何作图方法快速求解的方案。 通过这些文献的阅读及其自身的了解，目前对斯坦纳最小树问题，无论是初等几何法与算法方面都有一定的研究。用初等几何法解决斯坦纳最小树问题比较普遍，也得出了相当多的结论。但对于一些特殊图形的斯坦纳最小树，特别是点分布在若干个正三角形和正方形顶点的斯坦纳最小树的设计，较系统的讨论略显不足，对于不同正三角形网络和正方型网络的斯坦纳最小树连线总长度的优劣的比较未曾涉及，相应的寻找一些特殊的斯坦纳最小树的算法也少有看到，解决一般的斯坦纳最小树的基本想法比较欠缺。这些缺陷都是本作品要努力研究的。
