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