基本信息
- 項目名稱：
- 幾類特殊斯坦納最小樹問題的研究
- 小類：
- 數(shù)理
- 大類：
- 自然科學類學術論文
- 簡介：
- A．機械與控制（包括機械、儀器儀表、自動化控 制、工程、交通、建筑等） B．信息技術（包括計算機、電信、通訊、電子等） C．數(shù)理（包括數(shù)學、物理、地球與空間科學等） D．生命科學（包括生物、農學、藥學、醫(yī)學、健 康、衛(wèi)生、食品等） E．能源化工（包括能源、材料、石油、化學、化 工、生態(tài)、環(huán)保等）
- 詳細介紹：
- 斯坦納最小樹問題（即對于平面上已知的若干個點，允許添加一些其它點，將它們連接起來，使得總連線長度最小）是組合優(yōu)化的一個重要問題，它是許多實際問題的某種抽象，具有廣泛的應用前景。 本項目通過3個點和4點分布在正方形頂點上的斯坦納最小樹的設計與論證，歸納得到斯坦納最小樹的4條基本性質及其連線總長度的一些結論，并由此得到了斯坦納最小樹的一個判定方法。在此基礎上，首先討論了各種情形的一般的3個點和4個點的斯坦納最小樹，給出其算法并交由MATLAB軟件運行；然后分別設計出點分布在若干個正方形或正三角形頂點上的斯坦納最小樹，給出了一些應用實例。同時計算出一些特殊的斯坦納最小樹的連線總長度與它們的最小生成樹連線總長度的比值。經比較可知，在點數(shù)和布局類似的情況下，一般來說點分布在正三角形網絡圖的斯坦納最小樹比正方形網絡的斯坦納最小樹更優(yōu)。 基于對若干特殊斯坦納最小樹的研究，本項目最后給出了一般的斯坦納最小樹設計的一些設想，即將已知點近似地分布在一個正三角形網絡的頂點上，并在正三角形的中心尋找可能的斯坦納點。并給出了需進一步討論的相關問題，比如5點的斯坦納最小樹問題及其算法；由正n邊形n個頂點及其中心的這(n+1)點的斯坦納最小樹等。 有關幾類特殊的斯坦納最小樹的設計與算法等最優(yōu)化研究成果可以為國民經濟有關決策提供理論依據(jù)與實踐參考，從而創(chuàng)造社會效益和經濟效益。
作品圖片
作品專業(yè)信息
撰寫目的和基本思路
- 斯坦納最小樹是組合優(yōu)化的重要問題，具有廣泛的應用前景。通過本作品研究，探討斯坦納最小樹的基本性質和判定方法，給出幾個點數(shù)較少的斯坦納最小樹，設計其算法并交由計算機實現(xiàn)；在此基礎上，設計出幾類點數(shù)規(guī)模較大的、點分布在正三角形和正方形頂點上的幾類特殊的斯坦納最小樹，并對連線長度的優(yōu)劣加以討論。同時力求給出一般的斯坦納最小樹設計的想法，并把這些網絡優(yōu)化設計應用于實際。
科學性、先進性及獨特之處
- 本項目在有關研究的基礎上，對幾個簡單斯坦納最小樹進行嚴格論證，歸納出一般斯坦納最小樹的基本性質和判定方法，構造了幾類特殊斯坦納最小樹，并給出算法，該算法經MATLAB軟件運行結果與設計圖吻合。其獨特之處在于：設計了3點和4點的斯坦納最小樹及其算法，給出了全部的點分布在若干個正三角形或正方形頂點上的各種情形（包括部分邊長不等或某些頂點不全包括）的斯坦納最小樹，提出了一般斯坦納最小樹的設計思路。
應用價值和現(xiàn)實意義
- 本項目探討了有關斯坦納最小樹的初步理論及算法，可為斯坦納最小樹的理論方面提供參考，給出的路線安排的最優(yōu)化研究成果可為有關部門決策提供依據(jù)，從而獲得直接的社會效益和經濟效益。
學術論文摘要
- 斯坦納最小樹問題是組合優(yōu)化的一個重要問題，它是許多實際問題的某種抽象，具有廣泛的應用前景。通過3個點和4點分布在正方形頂點上的斯坦納最小樹的設計與論證，歸納出斯坦納最小樹的4條基本性質及其連線總長度的一些結論。在此基礎上，首先討論了各種情形的一般的3個點和4個點的斯坦納最小樹，給出其算法并交由MATLAB軟件運行；然后分別設計出點分布在若干個正方形或正三角形頂點上的斯坦納最小樹，給出了一些應用實例，同時計算出一些特殊的斯坦納最小樹的連線總長度與它們的最小生成樹連線總長度的比值，經比較可知，在點數(shù)和布局類似的情況下，正三角形網絡圖的斯坦納最小樹比正方形網絡的斯坦納最小樹更優(yōu)。基于對若干特殊斯坦納最小樹的研究，最后給出了一般的斯坦納最小樹設計的一點設想，即將已知點近似地分布在一個正三角形網絡的頂點上，并在正三角形的中心尋找可能的斯坦納點。
獲獎情況
- 1．2010年度浙江省大學生科技創(chuàng)新活動計劃（新苗人才計劃）立項項目 “幾類特殊斯坦納最小樹問題的研究”成果； 2.俞勝濤，交叉口信號配時的優(yōu)化設計，科學技術與工程，第10卷，第35期2010年12月； 3.張蓮蓮 黃忠裕 俞勝濤,幾類特殊的費馬點問題及其初等解法，中國科教創(chuàng)新導刊，2011，第23期； 4.“幾類特殊斯坦納最小樹問題的研究”獲溫州大學第四屆“挑戰(zhàn)杯”大學生課外學術科技作品競賽一等獎。
鑒定結果
- 2010年度浙江省大學生科技創(chuàng)新活動計劃立項項目 “幾類特殊斯坦納最小樹問題的研究” （項目編號：2010R424038），項目負責人張蓮蓮,成員：俞勝濤 尹秀芬 吳培蕾 朱劉輝，指導老師：黃忠裕）。
參考文獻
- [1]張亞明 ，劉玉峰 Steiner問題的研究及進展 燕山大學學報 1996\ 01 [2]堵丁柱 談談斯坦納樹 中國科學院應用數(shù)學研究所；1998\01 [3]翁稼豐 正多邊形頂點集上的斯坦納最小樹 應用數(shù)學學報 1985\ 02 [4] 蔣君偉,唐璞山 一種生成直角斯坦納樹的算法 復旦學報(自然科學版) 1986\03 [5]楊凌云 圖的steiner最小樹問題及其求解 電腦知識與技術 2009\ 25 [6]越民義 程叢電 關于Steiner問題的一個注記—連接五點之最小網絡的一種尋優(yōu)方案(英文) 運籌學學報 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世紀以來，很多學者對幾類特殊的斯坦納最小樹問題進行了討論和研究，并發(fā)表了相關研究成果。1968年，吉爾伯特和波蘭克提出猜想 ，此猜想在1990年被堵丁柱和黃光明利用凸分析方法得以證明。從算法復雜性角度考慮一般的斯坦納問題，加里、格厄姆和約翰森在1977年證明其屬于NP完全問題，即人們不能期望找到求解一般斯坦納最小樹的多項式算法。 R.Courant and H.Robbins在《WHAT IS MATHEMATICS?》一書中提到了幾個正三角形網絡圖的斯坦納最小樹及連線長度的一些結論。楊凌云在《圖的Steiner最小樹問題及其求解》中主要討論了圖的Steiner最小樹問題，并給出了近似算法，該算法是在破圈法的基礎上改進的。張亞明和劉玉峰在《Steiner問題的研究及進展》中詳細的介紹了Steiner問題及其幾個主要研究方向的進展情況，探討了有關Steiner問題各時期的研究特點，并且給出了一些相關的性質，該文較全面地對一些特殊點集上的SRT發(fā)表了自己的想法。F?K?Hwang、丁吉豫、宋國棟、堵丁柱在《歐式斯坦納最小樹的分解定理》中從另一個側面研究了斯坦納問題，他們認為現(xiàn)有的算法都不能解多于三個點的這種問題，他們提出分解定理對于擴大可解問題的范圍非常有幫助。越民義、程從電在《關于Steiner問題的一個注記——連接五點之最小網絡的一種尋優(yōu)方案》中給出了一個采用簡單幾何作圖方法快速求解的方案。 通過這些文獻的閱讀及其自身的了解，目前對斯坦納最小樹問題，無論是初等幾何法與算法方面都有一定的研究。用初等幾何法解決斯坦納最小樹問題比較普遍，也得出了相當多的結論。但對于一些特殊圖形的斯坦納最小樹，特別是點分布在若干個正三角形和正方形頂點的斯坦納最小樹的設計，較系統(tǒng)的討論略顯不足，對于不同正三角形網絡和正方型網絡的斯坦納最小樹連線總長度的優(yōu)劣的比較未曾涉及，相應的尋找一些特殊的斯坦納最小樹的算法也少有看到，解決一般的斯坦納最小樹的基本想法比較欠缺。這些缺陷都是本作品要努力研究的。
