【正文】 )).^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)。 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)。 300 300 300 300 300 300 300 300 0 300。 dist =[ 0 30 300 300 300 300 300 300 300 300。 judge(p,q)=*distance(p,q)d(p,q)。 s=sqrt((x(i)x(j)).^2+(y(i)y(j)).^2)。 300 110 0 300 300 300 300 300 300 300。0,0,0,50,100,100,100,25,]。 dist(j(k),i(k))=s(k)。 300 300 300 0 130 300 300 300 300。 w=dist(a)。 } Kce=(YcYe)/(XcXe)。 if (YaYb+(XaXb)*(YcYb)/(XcXb)) { Xe=(Xa+Xb)/2+*(YaYb)/2。 end end 附件 4 求斯坦納點(diǎn)的代碼： include void main() { float Xa,Ya,Xb,Yb,Xc,Yc,Xd,Yd,Xe,Ye,Xf,Yf,Kce,Kbd。 for k=1:1:length(i) dist(i(k),j(k))=s(k)。 300 300 300 300 85 0 25 300 300 300 300 300。 y=[0,0,0,50,100,100,100,25,75,40,40,70]。 end if count=2*n error([39。 path(1)=t。 j=index。 % node visibility visit(s)=0。 %更新 index break。 %用于存儲(chǔ)各點(diǎn)的出現(xiàn)的次數(shù)（一條邊對(duì)應(yīng)兩個(gè)端點(diǎn)） 22/33 for i=1:num %統(tǒng)計(jì)各點(diǎn)的出現(xiàn)次數(shù) p(w(index(i),2))=p(w(index(i),2))+1。39。 if ~isempty(find(index==i,1)) s_tmp=sprintf(39。,39。 %其實(shí)測(cè)試邊數(shù)為 3 條（ 3 條以下無法構(gòu)成圈，即無需檢測(cè)） while 1 x=findcycle(edge(index(1:i),:),len)。 %用于存儲(chǔ)圖中的邊 count=1。 Steiner 最小樹問題及其應(yīng)用。 . 模型的推廣 由于本題采用圖論模型的方法求解 ， 分析了在不同的限制條件下道路長(zhǎng)度和最短的數(shù)學(xué)模型及求解， 并提出能夠找到該近似算法或原則，可 以較好的推廣到解決 交通網(wǎng)絡(luò)、輸油管道、 災(zāi)情巡視線路、投遞、旅行商等實(shí)際問題 。 為了實(shí)現(xiàn)優(yōu) 19/33 先更新需要將每個(gè) 頂點(diǎn)連同它的數(shù)組下標(biāo)存儲(chǔ)在堆中，其時(shí)間復(fù)雜度在算法實(shí)現(xiàn)部分分析。 堆是一種抽 象數(shù)據(jù)結(jié)構(gòu)，由一系列元素集合構(gòu)成，每個(gè)元素有個(gè)實(shí)數(shù)類型的關(guān)鍵字。初始化時(shí)，只有源點(diǎn) s 的最短距離是已知的( ( ) 0)Ds? ? ? ，其余各點(diǎn)的估計(jì)最短距離 D 值均設(shè)為無窮大。經(jīng)多次驗(yàn)算，我們確定了一個(gè)斯坦納點(diǎn) ? ?55,80S 。所得到的 judge 矩陣為： 由于矩陣中無負(fù)元素，故 檢驗(yàn)得 所求道路滿足題目要求。若有 1 度輔助點(diǎn)，則顯然應(yīng)把該點(diǎn)連同關(guān)聯(lián)邊刪去；若有 2 度輔助點(diǎn)，則應(yīng)把該點(diǎn)連同關(guān)聯(lián)邊刪去，但要添加一條連接兩個(gè)鄰點(diǎn)的邊。 下面我們闡述一下 逐步調(diào)優(yōu)法的實(shí)施 步驟 ： Prim 算法求出正則點(diǎn)集 Z 的最小生成樹 0T 。 設(shè) k 表示輔助點(diǎn)數(shù)，讓 k 分別取值 1 到 2n? ，對(duì)于 每 一個(gè) k 值，在范圍 R 內(nèi)隨機(jī)投放 k 個(gè) 輔助點(diǎn)，產(chǎn)生輔 助 點(diǎn)集 F ， 然后用 Prim 算法計(jì)算出由 nk? 個(gè)點(diǎn)組成的集 ZU? 的最小生成樹。例如，給出三點(diǎn) A 、 B 、 C ， 組成邊長(zhǎng)為 1 的正三角形。 我們先引入斯坦納最小樹的定義： 定義 已知 歐式平面上任給 的 有限點(diǎn)集 ? ?12, , , nR v v v? ，欲求出一個(gè) 點(diǎn) 集? ?12, , , kS s s s? ， 使 點(diǎn)集 RS? 的連線 長(zhǎng)度最短 所構(gòu)成 的圖，必然是邊數(shù)最少的連通圖，因此它為樹，稱為 斯坦納最小樹 ，記為 SRT 。D ， 39。 . 步驟二： 通過分析題中要求， 任意的兩個(gè)入口之間的最短路徑 不大于兩點(diǎn) 間 連線的 倍，我們采用 Dijkstra 算法 對(duì)于步驟一生成的樹進(jìn)行驗(yàn)算 。稱為 G 的 最小生成樹 。 4. 符號(hào)說明及名詞解釋 . 基本符號(hào) 符號(hào) 意義 iP 第 i 個(gè)入口 ijPP? 從第 i 個(gè)入口到第 j 個(gè)入口的行走路線 4/33 5. 模型建立 與求解、檢驗(yàn) . 問題一 . 問題 解析 該問題給出了 四個(gè) 道路交叉點(diǎn) ： A、 B、 C、 D，在 ○ 1 所設(shè)計(jì) 道路 要 讓任意兩個(gè)入口相連 （可以利用公園的矩形邊）， ○ 2 道路只能與公園的 8 個(gè)入口相連而不能與四周其他點(diǎn)相連， ○ 3 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍 ， ○ 4 兩點(diǎn)間所建道路為直線的前提下，我們所關(guān)心的問題是，如何設(shè)計(jì)出公園內(nèi)道路設(shè)計(jì)的最優(yōu)方案，使得道路長(zhǎng)度和最短。考慮到任意兩點(diǎn)之間可以直接相連，我 3/33 們采用求解歐式距離的斯坦納點(diǎn)最小樹的逐步調(diào)優(yōu)法。 問題一屬于有限制條件的最小樹生成問題。 其中矩形湖的相關(guān)坐標(biāo)： R1(140,70) , R2(140,45) , R3=(165,45) , R4=(165,70). 2. 問題分析 從人性化角度考慮，公園道路應(yīng)滿足 讓任意兩個(gè)入口相連 ，以保證游人不管怎樣都可以走出公園 。問如何設(shè)計(jì)道路可使公園內(nèi)道路的總路程最短。 經(jīng)驗(yàn)算確定， 最終方案得到的道路總長(zhǎng)度為 米。題中所給三個(gè)問題，研究在不同現(xiàn)實(shí)背景下的最優(yōu)道路設(shè)計(jì)問題，根據(jù)所給限制條件的增加，層層深入。 最后本文還結(jié)合實(shí)際情況，對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了分析與評(píng)價(jià)，并提出了改進(jìn) 和推廣 方向。 問題二 ：現(xiàn) 公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。 對(duì)于校方而言，所建道路在滿足上述設(shè)計(jì)需要的基礎(chǔ)上，道路長(zhǎng)度和越短則消耗的資金越少。為 驗(yàn)算是否滿足題中所給兩點(diǎn)間 倍直線距離的要求，我們采用 Dijkstra 算法 解決最短路徑問題 。 問題三屬于約束條件下的斯坦納最小樹問題。 我們先引入 最小生成樹的簡(jiǎn)單定義： 給定一 個(gè) 無向 連 通帶權(quán)圖 ? ?,GVE 中的每一條邊 ? ?,VW 權(quán)值 為 ? ?,CVW 。 5/33 對(duì)于問題一，題中僅給定幾個(gè)固定點(diǎn)的坐標(biāo)，并不知道相應(yīng)的邊。 可利用 Dijkstra 算法對(duì)步驟一所生成的道路中任意兩入口間的 最短 距離進(jìn)行求解得 到 一 個(gè) 矩陣，再與這兩入口間距離 的矩陣的 倍 進(jìn)行作差，找出負(fù)數(shù)（即不符合要求）對(duì)應(yīng)的道路，進(jìn)行人工合理化調(diào)整修改 后即可得到最優(yōu)結(jié)果 。judge ， 修正后的公園道路設(shè)計(jì)圖（優(yōu)化結(jié)果） 11/33 39。 性質(zhì) 2 SRT 上，關(guān)聯(lián)于同一點(diǎn)的任何兩邊的夾角不小于 120 ；關(guān)聯(lián)于同一斯坦納點(diǎn)的任何兩邊的夾角恰為 120 。也就是說，添加斯坦納點(diǎn) 后可以節(jié)省約 13%的長(zhǎng)度。對(duì)被抽中的樹，對(duì)其每個(gè)輔助點(diǎn)，在一個(gè)小領(lǐng)域范圍內(nèi)隨機(jī)作擾動(dòng)，產(chǎn)生一個(gè)新的近似解，這樣重復(fù)多次擇優(yōu)記錄最好者， 若比原來的要好，則替換它，否則不變。 [0， 1]均勻分布的隨機(jī)數(shù) r ，若滿足 1kkq r q? ?? ，則對(duì) kT 的輔助點(diǎn)位置作擾動(dòng)，不是隨機(jī)重投，而是每個(gè)輔助點(diǎn)在一個(gè)半徑為 h 的鄰域內(nèi)隨機(jī)走一步（當(dāng)然不能走出 R 的范圍）。 6 和 7，大約 10 次， 若 最后 樹長(zhǎng) * 0| | | |TT? ， 則輸出 *T ，否則輸出0T 。 經(jīng) 過 分析 ， 只有入口 25PP? 和 入口 26PP? 在不添加道路交叉點(diǎn)的情況下不 能 滿足題中要求。而事實(shí)上 是可以再添加道路交叉點(diǎn)的 ， 此類 問題 便同問題二一樣 屬于 NP 難問題，也就是說 ,，當(dāng)問題含有其他約束條件時(shí) ,，要想求得真正的最優(yōu)解是不現(xiàn)實(shí)的，為此， 必需采取靈活多樣的方式和方法 , 求近似得最優(yōu)解； 3) 問題二在問題一的基礎(chǔ)上 可隨意添加道路交叉點(diǎn)，添加點(diǎn)的個(gè)數(shù)和位置均不確定， 成為 NP 難問題，無法找到精確最優(yōu)解。若路徑不存在則仍為無窮大； 在藍(lán)點(diǎn)集中選擇一個(gè)最短距離最小的藍(lán)點(diǎn) k 來擴(kuò)充紅點(diǎn)集是Dijkstra 算法的關(guān)鍵。 最小堆結(jié)構(gòu)必須滿足以下性質(zhì)：除了根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的值不小于其父節(jié)點(diǎn)的值．這樣，堆中的最小元素就存在根節(jié)點(diǎn)中 。其具體原理 如下： 多路徑并行搜索蟻群算法將每只螞蟻的求解過程分解為 m條路徑并行的搜索，其中 m為終端節(jié)點(diǎn)的個(gè)數(shù)。廣州：華南理工大學(xué)理學(xué)院， 20xx。圖的 steiner 最小樹問題及其求解。 edge(count,3)=j。 %若沒有構(gòu)成圈，則 i加 1，加入下一邊檢測(cè) end index=index(index0)。距離 39。√39。 end disp(s)。 %記錄除去出現(xiàn)次數(shù)小于 2 的端點(diǎn)所在的邊的邊的下標(biāo)集合 discard=find(p2)。 else isfind=1。 count=0。 parent(k)=j。amp。Please redefine path preallocation parameter.39。 dist = [ 0 30 300 300 300 300 300 300 300 300 300 300。 300 300 300 300 300 300 300 300 0 300 300 300。 %distance 為任意兩點(diǎn)間距離矩陣 d=zeros(8)。Ya,amp。 Yd=(Ya+Yc)/2+*(XaYc)/2。 26/33 Yf=Yb+Kbd*(XfXb)。 i=[1 1 2 3 3 5 6 6]。 300 300 300 300 300 25 0 85 300。 judge=zeros(8)。 y=[0,0,0,50,100,100,100,25,]。 300 300 300 300 85 0 25 300 300 300。 end distance=zeros(length(x))。 w=dist(a)。 300 300 300 0 130 300 300 300 300 300。 for k=1:1:length(i) dist(i(k),j(k))=s(k)。 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 = ==================================== ============================