1、裝訂線公園內道路設計最優問題摘 要對于題中所給的道路設計問題，即研究在約束條件下最小生成樹問題。題中所給三個問題，研究在不同現實背景下的最優道路設計問題，根據所給限制條件的增加，層層深入。本文針對題中所述的矩形公園，利用圖論中各種成熟的相關算法，對道路和最短的設計方案進行建模求解：對問題一，分為兩個步驟進行建模求解。步驟一利用算法生成總道路和的最小樹，步驟二用算法對步驟一生成的道路用是否滿足“任意兩入口間最短道路長小于二者連線的1.4倍”這一條件進行驗算，對于個別不滿足的道路進行微調和修改。最終方案中得到的道路總長度為394.5米。對問題二，在問題一的基礎上，我們采用求解歐式距離的斯坦納點最小

2、樹的逐步調優法，根據相應理論通過離散概率隨機抽取相應的斯坦納點進行擾動，直到得到最優解。經驗算確定，最終方案得到的道路總長度為362.1米。對問題三，我們利用題中的限制條件，分析了所給的人工湖位置與入口的坐標的數據特點，先確定了在不加道路交叉點情況下，僅利用湖四周的道路，即可滿足任意入口間最短路徑1.4倍條件的可利用的最短道路，再利用問題二中的方法添加了一個斯坦納點，并在其鄰域內進行擾動后得到最優解。經驗算確定，最終方案得到的道路總長度為324.6米。最后本文還結合實際情況，對模型的優缺點進行了分析與評價，并提出了改進和推廣方向。關鍵詞：最小生成樹；約束條件；算法；算法；求解歐式距離的斯坦納點

3、最小樹的逐步調優法；二叉堆目錄1.問題重述11.1.問題背景11.2.問題要求11.3.問題提出12.問題分析22.1.問題一的分析22.2.問題二的分析22.3.問題三的分析33.模型假設34.符號說明及名詞解釋34.1.基本符號35.模型建立與求解、檢驗45.1.問題一45.1.1.問題解析45.1.2. 模型建立與求解、檢驗75.2. 問題二95.2.1. 問題解析95.2.2. 模型建立與求解、檢驗95.3. 問題三95.3.1. 問題解析95.3.2. 模型建立與求解、檢驗96.結果表示96.1.問題一96.2.問題二96.3.問題三97.模型的評價、優化及推廣97.1.模型的評價9

4、7.2.模型的優化97.3.模型的推廣98.參考文獻99.附件清單91. 問題重述1.1. 問題背景西安某大學計劃建一個形狀為矩形或其他不規則圖形的公園，不僅為了美化校園環境，也是想為其學生提供更的生活條件。假設主要設計對象為一個矩形公園，其相關數據為：長200米，寬100米，1至8各入口的坐標分別為：.根據題目所給數據，運用數學建模方法，將實際復雜的問題理想模型簡化，設計出滿足題目要求的公園內道路，有很重要的現實意義。1.2. 問題要求從實際情況出發，對道路的設計有以下幾個要求：1) 讓任意兩個入口相連（可以利用公園四周的邊，即默認矩形的四條邊上存在已經建好的道路，此道路不計入道路總長）；2

5、) 任意的兩個入口之間的最短道路長不大于兩點連線的1.4倍；3) 公園內新修的道路只能通過8個路口與四周相連；4) 公園內總的道路長度和最小。1.3. 問題提出從實際情況及上述要求出發，依據相關條件和數據解決：問題一 ：假定公園內確定要使用4個道路交叉點為：A(50,75)，B(40,40)，C(120,40)，D(115,70）。問如何設計道路可使公園內道路的總路程最短。建立模型并給出算法。畫出道路設計，計算新修路的總路程。問題二 ：現公園內可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點的坐標，畫出道路設計，計算新修路的總路程。問題三 ：若公園內有一條矩形

6、的湖，新修的道路不能通過，但可以到達題中湖四周的邊。重復完成問題二 的任務。其中矩形湖的相關坐標：R1(140,70),R2(140,45),R3=(165,45),R4=(165,70).2. 問題分析從人性化角度考慮，公園道路應滿足讓任意兩個入口相連，以保證游人不管怎樣都可以走出公園。另外，由于公園內部設有觀賞景點或是休息座椅，所建設道路要經過這些地點。而這些地點又分為修公園前就有的和公園建好后才修建的，還可分為道路可以通過的和不可以通過的（如湖、花壇等），這些情況都對應于不同的道路設計方案。對于校方而言，所建道路在滿足上述設計需要的基礎上，道路長度和越短則消耗的資金越少。故道路

7、長度和為主要考察的對象。2.1. 問題一的分析問題一規定了一些必須經過的點。這來源于實際中所修道路要通向那些在公園建設之前就已存在的觀賞景點的情況。用數學模型分析解決這一問題對此類情況有重要意義。問題一屬于有限制條件的最小樹生成問題。解決最小樹問題，一般采用算法和算法。根據所學知識、題中數據特點和結果要求，我們選擇使用算法解決最小樹問題。為驗算是否滿足題中所給兩點間1.4倍直線距離的要求，我們采用算法解決最短路徑問題。2.2. 問題二的分析同問題一相比，問題二沒有規定公園內必須通過的點。這來源于實際中公園內的景點及設施都是在設計公園道路后才建的情況。用數學模型分析解決這一問題對此類情況有重要意

8、義。問題二屬于斯坦納最小生成樹問題?？紤]到任意兩點之間可以直接相連，我們采用求解歐式距離的斯坦納點最小樹的逐步調優法。2.3. 問題三的分析問題三在問題二的基礎上增加了限制條件，考慮到實際中公園等休閑場所在道路規劃前即有人工湖等情況，問題三即是從這一情形中抽象出來的。因此對于問題三的研究很有現實意義。問題三屬于約束條件下的斯坦納最小樹問題。顯然，在問題二的基礎上，道路是不能通過人工湖的，因此，問題二可看作問題三的簡化?？紤]到重建模型的復雜性和時間的緊迫性，我們利用了問題二所建模型，針對問題二得到的結果，在此基礎上進行了相關優化，直到獲得最優解。3. 模型假設1) 假設所有道路均為直線；2) 假

9、設任意兩點間均可修建道路，即公園內土質及其它條件對修路不產生影響（第三問的湖泊除外）；3) 假設所有道路均為無向的，不存在單行道，即道路為同一條路；4) 對于問題一，假設除了題中所給道路交叉點外，不再另外添加點。5) 對于問題三，假設矩形湖的四周也可以利用，即默認矩形的四條邊上存在已經建好的道路，此道路不計入道路總長。4. 符號說明及名詞解釋4.1. 基本符號符號意義第個入口從第個入口到第個入口的行走路線5. 模型建立與求解、檢驗5.1. 問題一5.1.1. 問題解析該問題給出了四個道路交叉點：A、B、C、D，在所設計道路要讓任意兩個入口相連（可以利用公園的矩形邊），道路只能與公園的8個入口相

10、連而不能與四周其他點相連，任意的兩個入口之間的最短道路長不大于兩點連線的1.4倍，兩點間所建道路為直線的前提下，我們所關心的問題是，如何設計出公園內道路設計的最優方案，使得道路長度和最短。我們將問題一的求解分為兩個步驟：一、使用算法解決最小樹問題；二、采用算法驗算步驟一生成的樹是否滿足題中所給的兩點間1.4倍直線的距離要求并進行人工微調修正。5.1.1.1. 步驟一：通過分析道路長度和最短的要求，我們發現這個問題和最小生成樹問題聯系最為緊密，于是考慮用貪心法求解最小生成樹的算法的一些研究成果以及相關的圖論知識來建立該問題的數學模型。我們先引入最小生成樹的簡單定義：給定一個無向連通帶權圖中的每一

11、條邊權值為。如果的子圖'是一個包含中所有定點的子圖，那么'稱為的生成樹，如果'的邊的權值最小，那么'稱為的最小生成樹。對于算法，其中心思想是每次添加權盡可能小的邊，使新的圖無圈，直到生成最優樹為止，其步驟如下：1) 把內的所有邊按照權的非減次序排列；2) 按1)排列的次序檢查中的每一條邊，如果這條邊與已得到的邊不產生圈，則取這一條邊為解的一部分；3) 若已取得n-1條邊，算法終止。此時以為頂點集，以取到的n-1條邊為邊集的圖即為最優樹。對于問題一，題中僅給定幾個固定點的坐標，并不知道相應的邊。為簡單起見，我們先假設任意兩點之間都是可以相連的，通過相關程序，即可算

12、出任意兩點間的距離，并作為距離矩陣輸出。其中，將任意兩點間的距離即作為該邊的權。 此時，可將距離矩陣作為算法的加權矩陣，進行輸入，即可得到由算法處理的最小樹。附注：利用該算法時，不考慮由外矩形邊框所引入的圈。5.1.1.2. 步驟二：通過分析題中要求，任意的兩個入口之間的最短路徑不大于兩點間連線的1.4倍，我們采用算法對于步驟一生成的樹進行驗算。我們先引入算法的簡單定義：算法是解決關于帶權圖(權為非負數)的單源最短路徑問題的一種貪心算法，它要一個一個地按路徑長度遞增序找出從某個源點出發到所有其他頂點的最短路徑。算法是按長度遞增的次序生成從源點到其他定點的最短路徑，則當前正在生成的最短路徑上除終

13、點以外，其余的頂點的最短路徑均已生成（將源點的最短路徑看作是已生成的源點到其自身的長度為0的路徑）?？衫盟惴▽Σ襟E一所生成的道路中任意兩入口間的最短距離進行求解得到一個矩陣，再與這兩入口間距離的矩陣的1.4倍進行作差，找出負數（即不符合要求）對應的道路，進行人工合理化調整修改后即可得到最優結果。對問題一的求解過程用流程圖表示如下：形成距離矩陣利用程序求任意兩點間的距離由kruskal算法程序最小樹最短路徑矩陣Dijkstra算法1.4倍距離矩陣差距作為輸入輸出作差倍最優解調整.模型建立與求解、檢驗5.1.1.1. 步驟一：將數據輸入由算法對應的程序（見附錄），僅僅考慮生成最小樹，得到如下結果

14、：算出來的結果：邊端點距離 是否在最小支撐樹 (1,2) 30 (1,3) 140 × (1,4) 1.868154e+002 × (1,5) 1.414214e+002 × (1,6) 1.011187e+002 × (1,7) 1.004988e+002 × (1,8) 3.201562e+001 (1,9) 8.077747e+001 × (1,10) 4.472136e+001 × (1,11) 1.077033e+002 × (1,12) 1.180042e+002 × (2,3) 110 &#

15、215; (2,4) 1.581139e+002 × (2,5) 1.220656e+002 × (2,6) 1.011187e+002 × (2,7) 1.077033e+002 × (2,8) 5.590170e+001 × (2,9) 75 × (2,10) 4.123106e+001 (2,11) 8.062258e+001 × (2,12) 9.552487e+001 × (3,4) 6.403124e+001 (3,5) 1.077033e+002 × (3,6) 1.600781e+002

16、× (3,7) 1.802776e+002 × (3,8) 1.619413e+002 × (3,9) 1.331353e+002 × (3,10) 1.264911e+002 × (3,11) 5.656854e+001 (3,12) 8.321658e+001 × (4,5) 9.433981e+001 × (4,6) 1.724094e+002 × (4,7) 1.964688e+002 × (4,8) 2.015564e+002 × (4,9) 1.520691e+002 ×

17、(4,10) 1.603122e+002 × (4,11) 8.062258e+001 × (4,12) 8.732125e+001 × (5,6) 85 × (5,7) 110 × (5,8) 1.415097e+002 × (5,9) 7.433034e+001 × (5,10) 100 × (5,11) 60 × (5,12) 3.041381e+001 (6,7) 25 (6,8) 8.276473e+001 × (6,9) 2.915476e+001 (6,10) 6.020797e+

18、001 × (6,11) 1.040433e+002 × (6,12) 8.544004e+001 × (7,8) 7.566373e+001 × (7,9) 4.716991e+001 × (7,10) 6.708204e+001 × (7,11) 1.252996e+002 × (7,12) 1.092016e+002 × (8,9) 7.071068e+001 × (8,10) 4.272002e+001 × (8,11) 1.209339e+002 × (8,12) 1.234

19、909e+002 × (9,10) 3.640055e+001 (9,11) 7.826238e+001 × (9,12) 6.519202e+001 (10,11) 80 × (10,12) 8.077747e+001 × (11,12) 3.041381e+001 （其中，“”表示兩端點是連通的，“×”表示兩端點不連通）由上述數據，可得初步公園道路圖：算法得出的最小樹對應的路徑圖（初步結果）5.1.1.2. 步驟二：步驟一生成的只是最小樹，而不一定滿足題中的要求任意的兩個入口之間的最短道路長不大于兩點連線的1.4倍。下面先對步驟一所生成的各

20、道路中任意兩入口間最短的折線距離利用算法進行求解，儲存到矩陣中，設這個矩陣用表示，=設儲存這兩入口間直線距離的矩陣用表示，=將矩陣和1.4倍的矩陣進行作差，得到矩陣，將矩陣和1.4倍的矩陣作差得到矩陣，=找出中的負數（即不符合要求）對應的道路，即和兩條折線道路大于兩入口直線距離的1.4倍，需要進行人工合理化調整修改。經過合理地分析與嘗試，我們將修改后的公園內道路確定為：修正后的公園道路設計圖（優化結果）下面對修改后的道路進行合理化的驗證。修改后再利用算法新生成的公園道路中任意兩入口間的最短距離進行求解，得到新的矩陣，記為，=任意兩入口的直線距離所儲存的矩陣不變，仍為=同理，再將矩陣和1.4倍的

21、矩陣進行作差，得到矩陣，=由中再無負數元素，可驗證得到修改后的道路滿足題中各條件，即為最優解。5.2. 問題二. 問題解析同問題一相比，問題二沒有規定公園內必須通過的點，屬于斯坦納最小生成樹問題。考慮到任意兩點之間可以直接相連，我們采用求解歐式距離的斯坦納點最小樹的逐步調優法。我們先引入斯坦納最小樹的定義：定義已知歐式平面上任給的有限點集 ，欲求出一個點集，使點集的連線長度最短所構成的圖，必然是邊數最少的連通圖，因此它為樹，稱為斯坦納最小樹，記為。中的點為上的固定點，中的點稱為上的斯坦納點，簡稱為斯坦納點。由于本問題可以自由添加道路交叉點，我們引入的一些性質：性質1上每個點之多關聯三條邊，而每

22、個斯坦納點恰好關聯三條邊。性質2上，關聯于同一點的任何兩邊的夾角不小于；關聯于同一斯坦納點的任何兩邊的夾角恰為。性質3 若，則中斯坦納點的個數不大于。性質4歐式斯坦納最小樹的每個斯坦納點都必定包含在全部正則點的最小凸包內。添加斯坦納點的斯坦納最小樹，往往會比不添加斯坦納點的最優樹的長度更短些。即若以和分別表示點集的最優樹和斯坦納最小樹的長度，必有。例如，給出三點、，組成邊長為1的正三角形。對點集的斯坦納最小樹的長度為，而最優樹長度為2。因此，。也就是說，添加斯坦納點后可以節省約13%的長度。引入以下定理：定理下面我們介紹最小逐步調優法的原理：設正則點集中有個點，坐標為。并記，。根據性質4，輔助

23、點的投放范圍可以控制在矩形之內。本文逐步調優法的思路是這樣的： 首先求出正則點集的最小生成樹,相應的樹長為。設表示輔助點數，讓分別取值1到，對于每一個值，在范圍內隨機投放個輔助點，產生輔助點集，然后用算法計算出由個點組成的集的最小生成樹。這樣就獲得棵樹，根據它們的樹長，計算出一個概率分布，樹長越短者，相應的概率越大。然后按此分布隨機抽樣，樹長越短，被抽中的概率就越大。對被抽中的樹，對其每個輔助點，在一個小領域范圍內隨機作擾動，產生一個新的近似解，這樣重復多次擇優記錄最好者，若比原來的要好，則替換它，否則不變。重算概率分布，再抽樣調優，這樣重復到預定循環次數為止。這里不直接選樹長最短者來調優，是

24、為了避免算法陷入局部極值，不是最短的樹也有機會被抽中。上述過程完成后，還需做最后的調整：刪掉1度和2度的輔助點（若有的話），利用求解斯坦納點坐標的計算式，并把3度輔助點調整到最優位置，使其變為斯坦納點。完成以上過程后，獲得一個近似最優解，若樹長，則輸出，否則輸出。下面我們闡述一下逐步調優法的實施步驟：1.用算法求出正則點集的最小生成樹。2.依次讓k取值1到，在矩形R內隨機投放k個輔助點，產生輔助點集，然后用算法計算出由個點組成的集的最小生成樹，樹長記為。3.記，這樣得到了一個離散的概率分布，并記，。4.產生一個0，1均勻分布的隨機數，若滿足，則對的輔助點位置作擾動，不是隨機重投，而是每個輔助點

25、在一個半徑為的鄰域內隨機走一步（當然不能走出的范圍）。這一步重復大約20次，擇優記錄最好者，若比原來的要好，則替換它，否則不變。5.重復步驟3和4，知道大道預設的最大迭代次數位置，此時的最好解記為。6.統計中輔助點的度。7.檢查和優化的輔助點。若有1度輔助點，則顯然應把該點連同關聯邊刪去；若有2度輔助點，則應把該點連同關聯邊刪去，但要添加一條連接兩個鄰點的邊。若有3度輔助點，一般它不是斯坦納點，需要矯正。按照斯坦納點的坐標計算公式，把該3度輔助點移動到該坐標位置上，調整后得到新的。8.重復步驟6和7，大約10次，若最后樹長，則輸出，否則輸出。如果有1度輔助點被刪除，則會影響相鄰點的度；如果有兩

26、個3度輔助點相鄰，則校正了1個輔助點成斯坦納點后，另一個輔助點可能又變得不在最佳位置。因此，第6、7步的重復是必要的，反復多次調優，才能逐步逼近最優位置。5.2.2.模型建立與求解、檢驗根據上述的逐步調優法，由本題，隨機分布個斯坦納點，通過離散概率隨機抽取相應的斯坦納點進行擾動，直到得到最優解，并解出新修路的總長度為363.1米。其對應的公園道路設計圖如下：利用問題一中相同的算法對結果進行驗算，看所求得道路是否滿足1.4倍這一條件。所得到的矩陣為：由于矩陣中無負元素，故檢驗得所求道路滿足題目要求。5.3.問題三. 問題解析問題三在問題二的基礎上增加了約束條件不能經過道路的區域，這也給題目增加了

27、很大的難度。為此，我們在分析了數據特點及湖位置的基礎上，根據問題一中的計算任意兩入口間折線距離的方法，我們確定了在不添加道路交叉點的情況下就可滿足折線距離小于兩入口直線距離1.4倍的條件的幾條邊。經過分析，只有入口和入口在不添加道路交叉點的情況下不能滿足題中要求。故只需要添加一個道路交叉點使這三點滿足兩入口直線距離的1.4倍這一條件，并且使新增的道路總長度最??；經分析，該點即為斯坦納點。在問題二的基礎上，利用歐式距離斯坦納最小樹的逐步調優法進行相關擾動，最終確定斯坦納點并進行驗算。. 模型建立與求解、檢驗根據問題二的理論依據，因為有三個點，故只需要添加一個斯坦納點即可。利用迭代思想，在該點的鄰

28、域內進行擾動，添加道路交叉點使這三點滿足兩入口直線距離的1.4倍，并且使道路總長度盡可能小。經多次驗算，我們確定了一個斯坦納點。計算可得道路長度和為324.6米，其相應的公園道路設計圖為：同問題一、問題二一樣的驗算原理，可算得此設計滿足題中各要求。6. 結果表示6.1. 問題一道路設計圖：問題一方案新修路的總路程：394.5米6.2. 問題二道路設計圖：問題二方案新修路的總長度：363.1米6.3. 問題三道路設計圖：問題三方案新修路的總長度：324.6米7. 模型的評價、優化及推廣7.1. 模型的評價1) 問題一的求解思路是先用算法得到是不帶環的最小樹，把邊加入最小樹再利用算法依據題中條件進

29、行驗算，這樣得到的結果可能不是最優解；2) 問題一中，模型一利用算法和算法分兩個步驟得到精確最優解的前提是假設所修道路均為直線，公園內部有且僅有給出的四個道路交叉點。而事實上是可以再添加道路交叉點的，此類問題便同問題二一樣屬于難問題，也就是說,，當問題含有其他約束條件時,，要想求得真正的最優解是不現實的，為此，必需采取靈活多樣的方式和方法, 求近似得最優解；3) 問題二在問題一的基礎上可隨意添加道路交叉點，添加點的個數和位置均不確定，成為難問題，無法找到精確最優解。本問題中的算法都只是近似算法, 所得最優設計方案也只是近似最優解；4) 問題二、三所用算法利用人工擾動精度不高且效率較低；5) 問

30、題三求解是在可利用湖的四邊而不算入所修總路程的假設下，具有一定的理想局限性。7.2. 模型的優化我們發現，在問題一的步驟二中用算法對最短路徑進行驗算的時間代價較高，若用傳統的方法通過掃描整個網絡圖的頂點來搜索最小值，總時間代價為，如果將模型應用到頂點數多的環境中，那么效率將非常低。經查閱相關文獻2后，我們認為利用二叉堆來進行優化，便可快速訪問到具有最小值的點，時間代價僅為。具體思路如下：設為最短距離已確定的頂點集（看作紅點集），是最短距離尚未確定的頂點集（看作藍點集）。初始化時，只有源點的最短距離是已知的，其余各點的估計最短距離值均設為無窮大。用數組記錄從源點到達外中間不經過任何藍點（若有中間

31、點，則必為紅點）的“最短”路徑長度（簡稱估計距離）。經過一次循環后，紅點集 ，其余各點的估計最短距離值更新為該點到源點而中間不經過任何點的邊的權值。若路徑不存在則仍為無窮大；在藍點集中選擇一個最短距離最小的藍點來擴充紅點集是算法的關鍵。若能快速訪問到具有最小值的藍點，則可大大減少算法的時間復雜度。若用傳統的方法通過掃描整個網絡圖的頂點（即窮舉法）來搜索最小值，總時間代價為。在算法中，由于累計權值決定的最短路徑具有優先程度差異特征，所以若將未被處理的頂點的最短路徑值構造優先級隊列，則可大大提高算法的效率。用堆來實現優先級隊列是很自然的。堆是一種抽象數據結構，由一系列元素集合構成，每個元素有個實數

32、類型的關鍵字。而二叉堆是一種最普及的數據結構，它可被視為一棵完全二叉樹。堆有最大堆和最小堆兩種。最小堆結構必須滿足以下性質：除了根節點，每個節點的值不小于其父節點的值這樣，堆中的最小元素就存在根節點中。因為具有個元素的二叉堆是一棵完全二叉樹，其高度為。所以對于二叉堆的操作例如(插入)和(從堆中刪除并返回最有最小關鍵字的元素)，其作用時間至多與樹的高度成正比，為。所以，將未被處理的頂點以值大小為順序保存在一個最小堆中，可以使用次搜索找出下一個最近頂點。每次改變值時，都可以通過先刪除再重新插入的方法改變頂點菇在堆中的位置。為了實現優先更新需要將每個頂點連同它的數組下標存儲在堆中，其時間復雜度在算法

33、實現部分分析。對于問題二采用的求斯坦納最小樹的逐步調優法，由于離散概率的不確定性，所以采用迭代的次數較多，過程較繁，相應地，效率也就降低了。針對這一問題，可以采用多路徑并行搜索蟻群算法的并行搜索機制進行相關優化。其具體原理如下：多路徑并行搜索蟻群算法將每只螞蟻的求解過程分解為m條路徑并行的搜索，其中m為終端節點的個數。每條路徑對應從一個終端節點出發，直至滿足某個條件終止。利用該方法路徑搜索的終止條件是剛訪問過的節點已經出現在其他路徑上，即當前路徑與其他路徑發生相交，則當前路徑設置為不活躍狀態，本路徑終止搜索節點。若當前螞蟻的所有的路徑都終止時，螞蟻在該輪迭代中搜索節點的過程也終止。螞蟻在這步操

34、作完成之后即得到一個節點的集合，該集合由這m條路徑上的所有節點構成，包括了所有終端節點和當前螞蟻認為必要的一些中間節點，這個過程極為螞蟻選擇節點的過程。7.3. 模型的推廣由于本題采用圖論模型的方法求解，分析了在不同的限制條件下道路長度和最短的數學模型及求解，并提出能夠找到該近似算法或原則，可以較好的推廣到解決交通網絡、輸油管道、災情巡視線路、投遞、旅行商等實際問題。8. 參考文獻1 林健良，施美珍，朱曉清，何明芳。求解歐式距離斯坦納最小樹的逐步調優法。廣州：華南理工大學理學院，2011。2 林小玲，何建農，周勇。帶限制條件的最短路徑算法與實現。福州：福州大學學報（自然科學版），2004。3

35、張瑾，馬良。最小樹問題及其應用。上海，開封：科學技術與工程，2008。4 楊凌云。圖的最小樹問題及其求解。開封：電腦知識與技術，2009。9. 附件清單1. 附件1：算法求最小生成樹的代碼及結果顯示；2. 附件2：求已知道路的情況下任意兩入口間最短距離的函數代碼；3. 附件3：構造的距離矩陣，為只包含聯通邊的距離矩陣；4. 附件4：求解斯坦納點的C語言代碼；5. 附件5：問題二中部分斯坦納點擾動過程6. 附件6：利用外矩形邊框驗算任意兩點間距離的1.4倍條件的C語言代碼；7. 附件7：問題二最優解情況下路徑生成及驗算代碼；8. 附件8：針對問題三的斯坦納點的擾動代碼。附件1Kruskal函數f

36、unction Kruskal(w,MAX)%此程序為最小支撐樹的Kruskal算法實現%w為無向圖的距離矩陣，故為對稱矩陣%MAX為距離矩陣中的實際輸入值%時間：2011年6月22日0:07:53len=length(w); %圖的點數edge=zeros(len*(len-1),3); %用于存儲圖中的邊count=1; %圖中的邊數for i=1:len-1 %循環距離矩陣，記錄存儲邊for j=i+1:lenif w(i,j)=MAXedge(count,1)=w(i,j);edge(count,2)=i;edge(count,3)=j;count=count+1;endendende

37、dge=edge(1:count-1,:); %去掉無用邊,index=sort(edge(:,1); %所有邊按升序排序i=3; %其實測試邊數為3條（3條以下無法構成圈，即無需檢測）while 1x=findcycle(edge(index(1:i),:),len); %檢測這些邊是否構成圈if xindex(i)=0; %若構成圈，則將該邊對應的index項標記為0，以便除去elsei=i+1; %若沒有構成圈，則i加1，加入下一邊檢測endindex=index(index>0); %將構成圈的邊從index中除去if i=lenbreak; %找到符合條件的點數減一條的邊，即找

38、到一個最小支撐樹endendindex=index(1:len-1); %截短index矩陣，保留前len-1項% 結果顯示 %s=sprintf('nt%st%st %st','邊端點','距離','是否在最小支撐樹');for i=1:count-1edge_tmp=edge(i,:);if isempty(find(index=i,1)s_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp(2),edge_tmp(3),edge_tmp(1),'');els

39、es_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp(2),edge_tmp(3),edge_tmp(1),'×');ends=strcat(s,s_tmp);enddisp(s);endfunction isfind=findcycle(w,N)%本程序用于判斷所給的邊能否構成圈：有圈，返回1；否則返回0%w：輸入的邊的矩陣%N：原圖的點數%原理：不斷除去出現次數小于2的端點所在的邊，最后觀察是否有邊留下len=length(w(:,1);index=1:len;while 1num=length(index)

40、; %邊數p=zeros(1,N); %用于存儲各點的出現的次數（一條邊對應兩個端點）for i=1:num %統計各點的出現次數p(w(index(i),2)=p(w(index(i),2)+1;p(w(index(i),3)=p(w(index(i),3)+1;endindex_tmp=zeros(1,num); %記錄除去出現次數小于2的端點所在的邊的邊的下標集合discard=find(p<2); %找到出現次數小于2的端點count=0; %記錄剩余的邊數for i=1:num%判斷各邊是否有僅出現一次端點沒有，則記錄其序號于index_tmpif(isempty(find(d

41、iscard=w(index(i),2),1) | isempty(find(discard=w(index(i),3),1)count=count+1;index_tmp(count)=index(i);endendif num=count %當沒有邊被被除去時，循環停止index=index_tmp(1:count); %更新indexbreak;elseindex=index_tmp(1:count); %更新indexendendif isempty(index) %若最后剩下的邊數為0，則無圈isfind=0;elseisfind=1;endend附件2Dijkstra函數funct

42、ion distance,path=dijkstra(A,s,e)% DISTANCE,PATH=DIJKSTRA(A,S,E)% returns the distance and path between the start node and the end node.% A: adjcent matrix% s: start node% e: end node% initializen=size(A,1); % node numberD=A(s,:); % distance vectorpath=; % path vectorvisit=ones(1,n); % node visibili

43、tyvisit(s)=0; % source node is unvisibleparent=zeros(1,n); % parent node% the shortest distancefor i=1:n-1 % BlueSet has n-1 nodes temp=zeros(1,n); count=0; for j=1:n if visit(j) temp=temp(1:count) D(j); else temp=temp(1:count) inf; end count=count+1; end value,index=min(temp); j=index; visit(j)=0;

44、for k=1:n if D(k)>D(j)+A(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end endenddistance=D(e);% the shortest distance pathif parent(e)=0 return;endpath=zeros(1,2*n); % path preallocationt=e; path(1)=t; count=1;while t=s && t>0 p=parent(t); path=p path(1:count); t=p; count=count+1;endif count>

45、;=2*n error('The path preallocation length is too short.',. 'Please redefine path preallocation parameter.');endpath(1)=s;path=path(1:count);附件3x=20,50,160,200,120,35,10,0,50,40,120,115;y=0,0,0,50,100,100,100,25,75,40,40,70;i=1 1 2 3 3 5 6 6 9 11 9;j=2 8 10 4 11 12 7 9 10 12 12;dist

46、= 0 30300300300300300300300300300300; 300110 0300300300300300300300300300; 300300300130 0 85300300300300300300; 300300300300 85 0 25300300300300300; 300300300300300 25 0 85300300300300; 300300300300300300 85 0300300300300; 300300300300300300300300 0300300300; 300300300300300300300300300 0300300; 300

47、300300300300300300300300300 0300; 300300300300300300300300300300300 0;s=sqrt(x(i)-x(j).2+(y(i)-y(j).2);for k=1:1:length(i) dist(i(k),j(k)=s(k); dist(j(k),i(k)=s(k);enddistance=zeros(length(x); %distance為任意兩點間距離矩陣d=zeros(8);judge=zeros(8);for p=1:1:8 for q=(p+1):1:8 distance(p,q)=sqrt(x(p)-x(q).2+(y(

48、p)-y(q).2); d(p,q)=dijkstra(dist,p,q); judge(p,q)=1.4*distance(p,q)-d(p,q); endend附件4求斯坦納點的代碼：#include <stdio.h>void main()   float Xa,Ya,Xb,Yb,Xc,Yc,Xd,Yd,Xe,Ye,Xf,Yf,Kce,Kbd;   scanf("%f%f%f%f%f%f",&Xa,&Ya,&Xb,&Yb,&Xc,&Yc);   if

49、 (Ya>Yb+(Xa-Xb)*(Yc-Yb)/(Xc-Xb)          Xe=(Xa+Xb)/2+1.717*(Ya-Yb)/2;       Ye=(Ya+Yb)/2-1.717*(Xa-Yb)/2;       Xd=(Xa+Xc)/2-1.717*(Ya-Yc)/2;       Yd=(Ya+Yc)/2+1.717

50、*(Xa-Yc)/2;       if (Ya<Yb+(Xa-Xb)*(Yc-Yb)/(Xc-Xb)          Xe=(Xa+Xb)/2-1.717*(Ya-Yb)/2;       Ye=(Ya+Yb)/2+1.717*(Xa-Yb)/2;       Xd=(Xa+Xc)/2+1.717*(Ya-Yc)/2; 

51、0;     Yd=(Ya+Yc)/2-1.717*(Xa-Yc)/2;       Kce=(Yc-Ye)/(Xc-Xe);   Kbd=(Yb-Yd)/(Xb-Xd);   Xf=(Kbd*Xb-Yb)-(Kce*Xc-Yc)/(Kbd-Kce);   Yf=Yb+Kbd*(Xf-Xb);   printf("Xf=%f,Yf=%f",Xf,Yf);   return 0;附件5問題

52、二中部分斯坦納點擾動過程一個點修改（68.31，49.84）a=20,50,160,200,120,35,10,0,68.31;0,0,0,50,100,100,100,25,49.84;w=dist(a);Kruskal(w,300)x=20,50,160,200,120,35,10,0,68.31;y=0,0,0,50,100,100,100,25,49.84;i=1 1 2 3 3 5 6 6;j=2 8 9 4 5 9 7 9;dist = 0 30 300 300 300 300 300 300 300;30 0 110 300 300 300 300 300 300; 300 11

53、0 0 300 300 300 300 300 300; 300 300 300 0 130 300 300 300 300; 300 300 300 130 0 85 300 300 300; 300 300 300 300 85 0 25 300 300; 300 300 300 300 300 25 0 85 300; 300 300 300 300 300 300 85 0 300; 300 300 300 300 300 300 300 300 0;s=sqrt(x(i)-x(j).2+(y(i)-y(j).2);for k=1:1:length(i) dist(i(k),j(k)=s(k); dist(j(k),i(k)=s(k);enddistance=zeros(length(x); %distance為任意兩點間距離矩陣d=zeros(8);judge=zeros(8);for p=1:1:8 for q=(p+1):1:8 distance(p,q)=sqrt(x(p)-x(q).2+(y(p)-y(q).2); d(p,q)=dijkstra(dist,p,q); judge(p,q)=1.4*distance(p,q)-d(p,q); e