【正文】 1/33 1. 問題重述 . 問題背景 西安某大學(xué)計劃建一個形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美化校園環(huán)境，也是想為其學(xué)生提供更的生活條件。 經(jīng)驗算確定， 最終方案得到的道路總長度為 米。 本文針對題中所述的矩形公園 ， 利用圖論中 各 種 成熟的相關(guān)算法，對道路和最短的設(shè)計方案進行建模求解 ： 對 問題一， 分為兩個步驟 進行建模 求解 。題中所給三個問題，研究在不同現(xiàn)實背景下的最優(yōu)道路設(shè)計問題，根據(jù)所給限制條件的增加，層層深入。 對問題二， 在問題一的基礎(chǔ)上， 我們采用求解歐式距離的斯坦納點最小樹的逐步調(diào)優(yōu)法 ，根據(jù)相應(yīng)理論 通過離散概率隨機抽取相應(yīng)的斯坦納點進行擾動，直到得到最優(yōu)解 。 最后本文還結(jié)合實際情況，對模型的優(yōu)缺點進行了分析與評價，并提出了改進 和推廣 方向。 . 問題提出 從實際情況及上述要求出發(fā)，依據(jù)相關(guān)條件和數(shù)據(jù) 解決 ： 問題一 ：假定公園內(nèi)確 定要使用 4個道路交叉點為： A(50,75)， B(40,40)，C(120,40)， D(115,70）。 問題二 ：現(xiàn) 公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。重復(fù)完成問題二 的任務(wù)。 對于校方而言，所建道路在滿足上述設(shè)計需要的基礎(chǔ)上，道路長度和越短則消耗的資金越少。用數(shù)學(xué)模型分析解決這一問題對此類情況有重要意義。為 驗算是否滿足題中所給兩點間 倍直線距離的要求，我們采用 Dijkstra 算法 解決最短路徑問題 。 問題二屬于斯坦納最小生成樹問題。 問題三屬于約束條件下的斯坦納最小樹問題。 5) 對于問題三，假設(shè)矩形湖的四周也可以 利用， 即默認矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長。 我們先引入 最小生成樹的簡單定義： 給定一 個 無向 連 通帶權(quán)圖 ? ?,GVE 中的每一條邊 ? ?,VW 權(quán)值 為 ? ?,CVW 。的邊的權(quán)值最小 ， 那么 G 39。 5/33 對于問題一，題中僅給定幾個固定點的坐標，并不知道相應(yīng)的邊。附注：利用該算法時，不考慮由外矩形邊框所引入的圈。 可利用 Dijkstra 算法對步驟一所生成的道路中任意兩入口間的 最短 距離進行求解得 到 一 個 矩陣，再與這兩入口間距離 的矩陣的 倍 進行作差，找出負數(shù)（即不符合要求）對應(yīng)的道路，進行人工合理化調(diào)整修改 后即可得到最優(yōu)結(jié)果 。 修改后再 利用 Dijkstra 算法新生成的公園道路中任意兩入口間的最短距離進行求解，得到新的矩陣，記為 39。judge ， 修正后的公園道路設(shè)計圖（優(yōu)化結(jié)果） 11/33 39?？紤]到任意兩點之間可以直接相連，我們采用求解歐式距離的斯坦納點最小樹的逐步調(diào)優(yōu)法。 性質(zhì) 2 SRT 上，關(guān)聯(lián)于同一點的任何兩邊的夾角不小于 120 ；關(guān)聯(lián)于同一斯坦納點的任何兩邊的夾角恰為 120 。即若以 ? ?mLR和 ? ?sLR分別表示點集 R 的最優(yōu)樹和斯坦納最小樹的長 12/33 度，必有 ? ? ? ?smL R L R? 。也就是說，添加斯坦納點 后可以節(jié)省約 13%的長度。 本文逐步調(diào)優(yōu)法的思路是這樣的 ： 首先求出正則點集 Z 的最小生成樹 0T ,相應(yīng)的樹長為 0||T 。對被抽中的樹，對其每個輔助點，在一個小領(lǐng)域范圍內(nèi)隨機作擾動，產(chǎn)生一個新的近似解，這樣重復(fù)多次擇優(yōu)記錄最好者， 若比原來的要好，則替換它，否則不變。 13/33 完成以上過程后，獲得一個近似最優(yōu)解 *T ，若樹長 * 0| | | |TT? ， 則輸出 *T ，否則輸出 0T 。 [0， 1]均勻分布的隨機數(shù) r ，若滿足 1kkq r q? ?? ，則對 kT 的輔助點位置作擾動，不是隨機重投，而是每個輔助點在一個半徑為 h 的鄰域內(nèi)隨機走一步（當然不能走出 R 的范圍）。 *T 的輔助點。 6 和 7，大約 10 次， 若 最后 樹長 * 0| | | |TT? ， 則輸出 *T ，否則輸出0T 。其對應(yīng)的 公園道路設(shè)計圖 如下： 利用問題一中相同 的 Dijkstra 算法 對結(jié)果進行驗算，看所求得道路是否滿足 倍這一條件。 經(jīng) 過 分析 ， 只有入口 25PP? 和 入口 26PP? 在不添加道路交叉點的情況下不 能 滿足題中要求。利用迭代 思想 ，在該點的鄰域內(nèi)進行擾動 ，添加道路交叉點使 2 5 6,P P P 這三點滿足兩入口直線距離的 倍 ，并且使道路 總長度盡可能小 。而事實上 是可以再添加道路交叉點的 ， 此類 問題 便同問題二一樣 屬于 NP 難問題，也就是說 ,，當問題含有其他約束條件時 ,，要想求得真正的最優(yōu)解是不現(xiàn)實的，為此， 必需采取靈活多樣的方式和方法 , 求近似得最優(yōu)解； 3) 問題二在問題一的基礎(chǔ)上 可隨意添加道路交叉點，添加點的個數(shù)和位置均不確定， 成為 NP 難問題，無法找到精確最優(yōu)解。具體思路如下： 設(shè) S 為最短距離已確定的頂點集（看作紅點集）， VS? 是最短距離尚未確定的頂點集（看作藍點集）。若路徑不存在則仍為無窮大； 在藍點集中選擇一個最短距離最小的藍點 k 來擴充紅點集是Dijkstra 算法的關(guān)鍵。用堆來實現(xiàn)優(yōu)先級隊列是很自然的。 最小堆結(jié)構(gòu)必須滿足以下性質(zhì)：除了根節(jié)點，每個節(jié)點的值不小于其父節(jié)點的值．這樣，堆中的最小元素就存在根節(jié)點中 。 每次改變 ??Dx值時， 都可以通過先刪除再重新插入的方法改變頂點菇在堆中的位 置。其具體原理 如下： 多路徑并行搜索蟻群算法將每只螞蟻的求解過程分解為 m條路徑并行的搜索，其中 m為終端節(jié)點的個數(shù)。螞蟻在這步操作完成之后即得到一個節(jié)點的集合，該集合由這 m條路徑上的所有節(jié)點構(gòu)成，包括了所有終端節(jié)點和當前螞蟻認為必要的一些中間節(jié)點，這個過程極為螞蟻選擇節(jié)點的過程。廣州：華南理工大學(xué)理學(xué)院， 20xx。 [3] 張瑾，馬良。圖的 steiner 最小樹問題及其求解。 %圖的點數(shù) edge=zeros(len*(len1),3)。 edge(count,3)=j。 %所有邊按升序排序 21/33 i=3。 %若沒有構(gòu)成圈，則 i加 1，加入下一邊檢測 end index=index(index0)。\n\t%s\t%s\t %s\t39。距離 39。 for i=1:count1 edge_tmp=edge(i,:)?！?9。,edge_tmp(2),edge_tmp(3),edge_tmp(1),39。 end disp(s)。 %邊數(shù) p=zeros(1,N)。 %記錄除去出現(xiàn)次數(shù)小于 2 的端點所在的邊的邊的下標集合 discard=find(p2)。 end end if num==count %當沒有邊被被除去時，循環(huán)停止 index=index_tmp(1:count)。 else isfind=1。 % path vector visit=ones(1,n)。 count=0。 end [value,index]=min(temp)。 parent(k)=j。 % path preallocation 24/33 t=e。amp。 count=count+1。Please redefine path preallocation parameter.39。 附件 3 x=[20,50,160,200,120,35,10,0,50,40,120,115]。 dist = [ 0 30 300 300 300 300 300 300 300 300 300 300。 300 300 300 130 0 85 300 300 300 300 300 300。 300 300 300 300 300 300 300 300 0 300 300 300。 s=sqrt((x(i)x(j)).^2+(y(i)y(j)).^2)。 %distance 為任意兩點間距離矩陣 d=zeros(8)。 judge(p,q)=*distance(p,q)d(p,q)。Ya,amp。Yc)。 Yd=(Ya+Yc)/2+*(XaYc)/2。 Yd=(Ya+Yc)/*(XaYc)/2。 26/33 Yf=Yb+Kbd*(XfXb)。0,0,0,50,100,100,100,25,]。 i=[1 1 2 3 3 5 6 6]。 300 110 0 300 300 300 300 300 300。 300 300 300 300 300 25 0 85 300。 for k=1:1:length(i) dist(i(k),j(k))=s(k)。 judge=zeros(8)。 27/33 end end ========================= judge = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 w(1,8)+w(2,9)+w(5,9)+w(3,5)+w(3,4)+w(6,9) ans = ================================= ================================= 兩個點（ ， ），（ ， ） a=[20,50,160,200,120,35,10,0,。 y=[0,0,0,50,100,100,100,25,]。 30 0 110 300 300 300 300 300 300 300。 300 300 300 300 85 0 25 300 300 300。 300 300 300 300 300 300 300 300 300 0]。 end distance=zeros(length(x))。 d(p,q)=dijkstra(dist,p,q)。 w=dist(a)。 j=[2 8 9 4 10 10 7 9 10]。 300 300 300 0 130 300 300 300 300 300。 300 300 300 300 300 300 85 0 300 300。 for k=1:1:length(i) dist(i(k),j(k))=s(k)。 judge=zeros(8)。 end end ================================== 結(jié)果： judge = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 w(1,8)+w(2,9)+w(3,4)+w(3,10)+w(5,10)+w(6,9)+w(9,10) 30/33 ans = ==================================== ============================