【正文】 .............................................. 14 . 模型建立與求解、檢驗 ......................................................................................................... 15 6. 結(jié)果表示 ....................................................................................................................................................... 15 . 問題一 .................................................................................................................................................... 15 . 問題二 .................................................................................................................................................... 16 . 問題三 .................................................................................................................................................... 16 7. 模型的評價、優(yōu)化及推廣 ........................................................................................................................ 17 . 模型的評價 ........................................................................................................................................... 17 . 模型的優(yōu)化 ........................................................................................................................................... 18 . 模型的推廣 ........................................................................................................................................... 19 8. 參考文獻 ....................................................................................................................................................... 19 9. 附件清單 ....................................................................................................................................................... 20 1/33 1. 問題重述 . 問題背景 西安某大學(xué)計劃建一個形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美化校園環(huán)境，也是想為其學(xué)生提供更的生活條件。建立模型并給出算法。 故道路長度和為主要考察的對象。 . 問題二的分析 同問題一相比，問題二沒有規(guī)定公園內(nèi)必須通過的點。 顯然，在問題二的基礎(chǔ)上，道路是不能通過人工湖的，因此，問題二可看作問題三的簡化。如果 G 的子圖 G 39。為簡單起見，我們先假設(shè)任意兩點之間都是可以相連的，通過相關(guān)程序，即可算出任意兩點間的距離，并作為距離矩陣輸出。 6/33 對 問題一的 求解過程 用流程圖表示 如下 ： 形成 距離矩陣 利用程序求任意兩點 間的距離 由 kruskal 算法程序 最小樹 最短路徑矩陣 Dijkstra 算法 倍距離矩陣 差距 作為輸入 輸出 作差 ? 倍 最優(yōu)解 調(diào)整 7/33 . 模型建立 與求解、檢驗 . 步驟一： 將數(shù)據(jù)輸入由 kruskal 算法對應(yīng)的程序（見附錄）， 僅僅考慮 生成最小樹 ，得到如下結(jié)果： kruskal 算出來的結(jié)果 ： 邊端點 距離 是否在最小支撐樹 (1,2) 30 √ (1,3) 140 (1,4) +002 (1,5) +002 (1,6) +002 (1,7) +002 (1,8) +001 √ (1,9) +001 (1,10) +001 (1,11) +002 (1,12) +002 (2,3) 110 (2,4) +002 (2,5) +002 (2,6) +002 (2,7) +002 (2,8) +001 (2,9) 75 (2,10) +001 √ (2,11) +001 (2,12) +001 (3,4) +001 √ (3,5) +002 (3,6) +002 (3,7) +002 (3,8) +002 (3,9) +002 (3,10) +002 (3,11) +001 √ (3,12) +001 (4,5) +001 (4,6) +002 (4,7) +002 (4,8) +002 (4,9) +002 8/33 (4,10) +002 (4,11) +001 (4,12) +001 (5,6) 85 (5,7) 110 (5,8) +002 (5,9) +001 (5,10) 100 (5,11) 60 (5,12) +001 √ (6,7) 25 √ (6,8) +001 (6,9) +001 √ (6,10) +001 (6,11) +002 (6,12) +001 (7,8) +001 (7,9) +001 (7,10) +001 (7,11) +002 (7,12) +002 (8,9) +001 (8,10) +001 (8,11) +002 (8,12) +002 (9,10) +001 √ (9,11) +001 (9,12) +001 √ (10,11) 80 (10,12) +001 (11,12) +001 √ （其中，“ √”表示兩端點是連通的，“ ”表示兩端點不連通） 由 上述數(shù)據(jù)， 可得初步 公園道路圖： 9/33 . 步驟二： 步驟一生成的只是 最小樹 ，而不一定滿足題中的要求 —— 任意的兩個入口之間的最短道路長不大于兩點連線的 倍。judge = 由 39。 性質(zhì) 3 若 ? ?12, , , nR v v v? ，則 SRT 中斯坦納點的個數(shù)不大于 2n? 。 引入以下定理： 定理 ? ?? ? 32smLRLR? 下面我們 介紹 最小逐步調(diào)優(yōu)法的原理： 設(shè)正則點集 Z 中有 n 個點 ? ?2n? ，坐標為 ? ?, , 1, 2, ,iix y i n? 。重 算概率分 布，再抽 樣調(diào)優(yōu)，這樣重復(fù)到預(yù)定循環(huán)次數(shù)為止。這一步重復(fù)大約 20 次，擇優(yōu)記錄最好者，若比原來的要好，則替換它，否則 kT 不變。如果有 1 度輔助點被刪除，則會影響相鄰點的度；如果有兩個 3 度輔助點相鄰，則校正了 1 個輔助點成斯坦納點后，另一個輔助點可能又變得不在最佳位置。故只需要添加 一個 道路交叉點使 2 5 6,P P P 這三點滿足兩入口直線距離的 倍這一條件 ，并且使新增的道路總長度最小；經(jīng)分析，該點即為斯坦納點 。本問題中的算法都只是近似算法 , 所得最優(yōu)設(shè)計方案 也只是近似最優(yōu)解； 4) 問題二、三所用算法利用人工擾動精度不高且效率較低； 5) 問題 三求解是在 可利用湖的四邊而不算入所修總路程的假設(shè)下，具 有一定的理想局限性。若能快速訪問到具有最小 D 值的藍點，則可大大減少算法的時間復(fù)雜度。 因為具有 n 個元素的二叉堆是一棵完全二叉樹，其高度為 logn 。每條路徑對應(yīng)從一個終端節(jié)點出發(fā)，直至滿足某個條件終止。 [2] 林小玲，何建農(nóng)，周勇。開封：電腦知識與技術(shù)， 20xx。 count=count+1。 %將構(gòu)成 圈的邊從 index 中除去 if i==len break。,39。)。 end function isfind=findcycle(w,N) %本程序用于判斷 所給的邊能否構(gòu)成圈：有圈，返回 1；否則返回 0 %w：輸入的邊的矩陣 %N：原圖的點數(shù) %原理：不斷除去出現(xiàn)次數(shù)小于 2 的端點所在的邊，最后觀察是否有邊留下 len=length(w(:,1))。 %找到出現(xiàn)次數(shù)小于 2 的端點 count=0。 end end 附件 2 Dijkstra 函數(shù) function [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 23/33 % s: start node % e: end node % initialize n=size(A,1)。 for j=1:n if visit(j) temp=[temp(1:count) D(j)]。 end end end distance=D(e)。 t0 p=parent(t)。])。 30 0 110 300 300 300 300 300 300 300 300 300。 300 300 300 300 300 300 300 300 300 0 300 300。 judge=zeros(8)。Xb,amp。 } if (YaYb+(XaXb)*(YcYb)/(XcXb)) { Xe=(Xa+Xb)/*(YaYb)/2。 printf(Xf=%f,Yf=%f,Xf,Yf)。 j=[2 8 9 4 5 9 7 9]。 300 300 300 300 300 300 85 0 300。 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)。 i=[1 1 2 3 3 5 6 6 9]。 300 300 300 300 300 25 0 85 300 300。 %distance 為任意兩點間距離矩陣 d=zeros(8)。 Kruskal(w,300) x=[20,50,160,200,120,35,10,0,]。 300 300 300 130 0 85 300 300 300 300。