【正文】 根據(jù)它們的樹 長(zhǎng)，計(jì)算出一個(gè)概率分布 ， 樹長(zhǎng)越短者，相應(yīng)的概率越大。 R 中的點(diǎn)為 SRT 上的固定點(diǎn)， S 中的點(diǎn)稱為 SRT 上的斯坦納點(diǎn) ，簡(jiǎn)稱為 斯坦納點(diǎn) 。 我們先引入 Dijkstra 算法的簡(jiǎn)單定義： Dijkstra 算法 是解決關(guān)于帶權(quán)圖 (權(quán)為非負(fù)數(shù) )的單源最短路徑問題的一種貪心算法，它要一個(gè)一個(gè)地按路徑長(zhǎng)度遞增序找出從某個(gè)源點(diǎn)出發(fā)到所有其他頂點(diǎn)的最短路徑 。 我們將問題一的求解分為兩個(gè)步驟： 一、 使用 kruskal 算法解決最小樹問題 ；二、 采用 Dijkstra 算法 驗(yàn)算步驟一生成的樹是否滿足題中所給的兩點(diǎn)間 倍直線的距離要求 并進(jìn)行人工 微調(diào) 修正 。解決 最小樹 問題，一般采用kruskal 算法和 prim 算法。建立模型并給出算法。 公園內(nèi)道路設(shè)計(jì)最優(yōu)問題 摘 要 對(duì)于題中所給的道路設(shè)計(jì)問題，即研究在約束條件下最小生成樹問題。畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。根據(jù)所學(xué)知識(shí)、題中數(shù)據(jù)特點(diǎn)和結(jié)果要求，我們選擇使用 kruskal 算法解決最小樹問題。 . 步驟 一： 通過分析道路長(zhǎng)度和最短的要求， 我們發(fā)現(xiàn)這個(gè)問題和最小生成樹問題聯(lián)系最為緊密，于是考慮用 貪心法求解最小生成樹 的 kruskal 算法 的一些研究成果以及相關(guān)的圖論知識(shí)來建立該問題的數(shù)學(xué)模型。 Dijkstra 算法是按長(zhǎng)度遞增的次序生成從源點(diǎn) s 到其他定點(diǎn)的最短路徑，則當(dāng)前正在生成的最短路徑上除終點(diǎn)以外，其余的頂點(diǎn)的最短路徑均已生成（將源點(diǎn)的最短路徑看作是已生成的源點(diǎn)到其自身的長(zhǎng)度為 0 的路徑）。 由于本問題可以自由 添 加道路交叉點(diǎn)，我們引入 SRT 的一些性質(zhì)： 性質(zhì) 1 SRT 上每個(gè)點(diǎn)之多關(guān)聯(lián)三條邊，而每個(gè)斯坦納點(diǎn)恰好關(guān) 聯(lián)三條邊。然后按此分布隨機(jī)抽樣，樹長(zhǎng)越短，被抽 中 的概率就越大。按照斯坦納點(diǎn)的坐標(biāo)計(jì)算公式，把該 3 度輔助點(diǎn)移動(dòng)到該坐標(biāo)位置上，調(diào)整后得到新的 *T 。 6. 結(jié)果表示 . 問題一 16/33 道路設(shè)計(jì)圖： 問題一方案 新修路的總路程： 米 . 問題二 道路設(shè)計(jì)圖： 問題二方案 新修路的總長(zhǎng)度： 米 . 問題三 道路設(shè)計(jì)圖： 17/33 問題三方案 新修路的總長(zhǎng)度： 米 7. 模型的評(píng)價(jià) 、優(yōu)化及 推廣 . 模型的評(píng)價(jià) 1) 問題一的求解思路是先用 kruskal 算法得到是不帶環(huán)的最小樹， 把 邊加入最小樹再利用 Dijkstra 算法 依據(jù)題中條件進(jìn)行驗(yàn)算，這樣得到的結(jié)果可能不是最優(yōu)解； 2) 問題一中，模型一 利用 kruskal 算法 和 Dijkstra 算法 分兩個(gè)步驟得到精確最優(yōu)解的前提是假設(shè)所修道路均為直線， 公園內(nèi)部有且僅有給出的四個(gè)道路交叉點(diǎn) 。堆有最大堆和最小堆兩種。求解歐式距離斯坦納最小樹的逐步調(diào)優(yōu)法。 edge(count,2)=i。,39。 end s=strcat(s,s_tmp)。 %更新 index end end if isempty(index) %若最后剩下的邊數(shù)為 0，則無圈 isfind=0。 for k=1:n if D(k)D(j)+A(j,k) D(k)=D(j)+A(j,k)。,... 39。 300 300 300 300 300 300 85 0 300 300 300 300。Xa,amp。 Xf=((Kbd*XbYb)(Kce*XcYc))/(KbdKce)。 300 300 300 300 85 0 25 300 300。 Kruskal(w,300) x=[20,50,160,200,120,35,10,0,]。 28/33 dist(j(k),i(k))=s(k)。 300 110 0 300 300 300 300 300 300 300。 judge(p,q)=*distance(p,q)d(p,q)。 300 300 300 130 0 85 300 300 300 300。 %distance 為任意兩點(diǎn)間距離矩陣 d=zeros(8)。 i=[1 1 2 3 3 5 6 6 9]。 300 300 300 300 300 300 85 0 300。 printf(Xf=%f,Yf=%f,Xf,Yf)。Xb,amp。 300 300 300 300 300 300 300 300 300 0 300 300。])。 end end end distance=D(e)。 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)。 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))。,39。 count=count+1。 [2] 林小玲，何建農(nóng)，周勇。 因?yàn)榫哂?n 個(gè)元素的二叉堆是一棵完全二叉樹，其高度為 logn 。本問題中的算法都只是近似算法 , 所得最優(yōu)設(shè)計(jì)方案 也只是近似最優(yōu)解； 4) 問題二、三所用算法利用人工擾動(dòng)精度不高且效率較低； 5) 問題 三求解是在 可利用湖的四邊而不算入所修總路程的假設(shè)下，具 有一定的理想局限性。如果有 1 度輔助點(diǎn)被刪除，則會(huì)影響相鄰點(diǎn)的度；如果有兩個(gè) 3 度輔助點(diǎn)相鄰，則校正了 1 個(gè)輔助點(diǎn)成斯坦納點(diǎn)后，另一個(gè)輔助點(diǎn)可能又變得不在最佳位置。重 算概率分 布，再抽 樣調(diào)優(yōu)，這樣重復(fù)到預(yù)定循環(huán)次數(shù)為止。 性質(zhì) 3 若 ? ?12, , , nR v v v? ，則 SRT 中斯坦納點(diǎn)的個(gè)數(shù)不大于 2n? 。 6/33 對(duì) 問題一的 求解過程 用流程圖表示 如下 ： 形成 距離矩陣 利用程序求任意兩點(diǎn) 間的距離 由 kruskal 算法程序 最小樹 最短路徑矩陣 Dijkstra 算法 倍距離矩陣 差距 作為輸入 輸出 作差 ? 倍 最優(yōu)解 調(diào)整 7/33 . 模型建立 與求解、檢驗(yàn) . 步驟一： 將數(shù)據(jù)輸入由 kruskal 算法對(duì)應(yīng)的程序（見附錄）， 僅僅考慮 生成最小樹 ，得到如下結(jié)果： kruskal 算出來的結(jié)果 ： 邊端點(diǎn) 距離 是否在最小支撐樹 (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 . 步驟二： 步驟一生成的只是 最小樹 ，而不一定滿足題中的要求 —— 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍。如果 G 的子圖 G 39。 . 問題二的分析 同問題一相比，問題二沒有規(guī)定公園內(nèi)必須通過的點(diǎn)。建立模型并給出算法。 本文針對(duì)題中所述的矩形公園 ， 利用圖論中 各 種 成熟的相關(guān)算法，對(duì)道路和最短的設(shè)計(jì)方案進(jìn)行建模求解 ： 對(duì) 問題一， 分為兩個(gè)步驟 進(jìn)行建模 求解 。 . 問題提出 從實(shí)際情況及上述要求出發(fā)，依據(jù)相關(guān)條件和數(shù)據(jù) 解決 ： 問題一 ：假定公園內(nèi)確 定要使用 4個(gè)道路交叉點(diǎn)為： A(50,75)， B(40,40)，C(120,40)， D(115,70）。用數(shù)學(xué)模型分析解決這一問題對(duì)此類情況有重要意義。 5) 對(duì)于問題三，假設(shè)矩形湖的四周也可以 利用， 即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)。附注：利用該算法時(shí)，不考慮由外矩形邊框所引入的圈?？紤]到任意兩點(diǎn)之間可以直接相連，我們采用求解歐式距離的斯坦納點(diǎn)最小樹的逐步調(diào)優(yōu)法。 本文逐步調(diào)優(yōu)法的思路是這樣的 ： 首先求出正則點(diǎn)集 Z 的最小生成樹 0T ,相應(yīng)的樹長(zhǎng)為 0||T 。 *T 的輔助點(diǎn)。利用迭代 思想 ，在該點(diǎn)的鄰域內(nèi)進(jìn)行擾動(dòng) ，添加道路交叉點(diǎn)使 2 5 6,P P P 這三點(diǎn)滿足兩入口直線距離的 倍 ，并且使道路 總長(zhǎng)度盡可能小 。用堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列是很自然的。螞蟻在這步操作完成之后即得到一個(gè)節(jié)點(diǎn)的集合，該集合由這 m條路徑上的所有節(jié)點(diǎn)構(gòu)成，包括了所有終端節(jié)點(diǎn)和當(dāng)前螞蟻認(rèn)為必要的一些中間節(jié)點(diǎn)，這個(gè)過程極為螞蟻選擇節(jié)點(diǎn)的過程。 %圖的點(diǎn)數(shù) edge=zeros(len*(len1),3)。\n\t%s\t%s\t %s\t39。,edge_tmp(2),edge_tmp(3),edge_tmp(1),39。 end end if num==count %當(dāng)沒有邊被被除去時(shí)，循環(huán)停止 index=index_tmp(1:count)。 end [value,index]=min(temp)。 count=count+1。 300 300 300 130 0 85 300 300 300 300 300 300。 judge(p,q)=*distance(p,q)d(p,q)。 Yd=(Ya+Yc)/