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