【正文】 300 300 300。 y=[0,0,0,50,100,100,100,25,]。 judge=zeros(8)。 300 300 300 300 300 300 85 0 300 300。 j=[2 8 9 4 10 10 7 9 10]。 d(p,q)=dijkstra(dist,p,q)。 300 300 300 300 300 300 300 300 0]。 dist =[ 0 30 300 300 300 300 300 300 300。 return 0。 Ye=(Ya+Yb)/2+*(XaYb)/2。Yb,amp。 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 300 300 0 300。 300 110 0 300 300 300 300 300 300 300 300 300。 end path(1)=s。 path=[p path(1:count)]。 % the shortest distance path if parent(e)==0 return。 else temp=[temp(1:count) inf]。 % node number D=A(s,:)。 %記錄剩余的邊數(shù) for i=1:num %判斷各邊是否有僅出現(xiàn)一次端點(diǎn) —— 沒有，則記錄其序號于 index_tmp if~(~isempty(find(discard==w(index(i),2),1)) || ~isempty(find(discard==w(index(i),3),1))) count=count+1。 index=1:len。 else s_tmp=sprintf(39。是否在最小支撐樹 39。 %找到符合條件的點(diǎn)數(shù)減一條的邊，即找到一個最小支撐樹 end end index=index(1:len1)。 end end end edge=edge(1:count1,:)。 20/33 9. 附件清單 1. 附件 1： kruskal 算法求最小生成樹的 MATLAB 代碼 及結(jié)果顯示； 2. 附件 2： 求已知道路的情況下任意兩入口間最短距離的 Dijkstra 函數(shù) MATLAB代碼 ； 3. 附件 3： 構(gòu)造的距離矩陣 dist ， dist 為只包含聯(lián)通邊的距離矩陣； 4. 附件 4： 求解 斯坦納 點(diǎn)的 C 語言代碼； 5. 附件 5：問題二中部分斯坦納點(diǎn)擾動過程 6. 附件 6：利用外矩形邊框驗算任意兩點(diǎn)間距離的 倍條件 的 C 語言代碼； 7. 附件 7： 問題二最優(yōu)解情況下路徑生成及驗算代碼； 8. 附件 8： 針對問題三 的 斯坦納點(diǎn)的擾動代碼 。帶限制條件的最短路徑算法與實現(xiàn)。利 用該方法路徑搜索的終止條件是剛訪問過的節(jié)點(diǎn)已經(jīng)出現(xiàn)在其他路徑上，即當(dāng)前路徑與其他路徑發(fā)生相交，則當(dāng)前路徑設(shè)置為不活躍狀態(tài)，本路徑終止搜索節(jié)點(diǎn)。 所以對于二叉堆的操作例如 insert (插入 )和removemin (從堆中刪除并返回最有最小關(guān)鍵字的元素 )，其作用時間至多與樹的高度成正比，為 ? ?logOn。若用傳統(tǒng)的方法通過掃描整個網(wǎng)絡(luò)圖的頂點(diǎn)（即窮舉法）來搜索最小值，總時間代價為 ? ?2On 。 18/33 . 模型的優(yōu)化 我們發(fā)現(xiàn)，在問題一的步驟二中用 Dijkstra 算法 對最短路徑進(jìn)行驗算 的 時間代價較高， 若用傳統(tǒng)的方法通過掃描整個網(wǎng)絡(luò)圖的頂點(diǎn)來搜索最小值，總時間代價為 ? ?2On ，如果將模型應(yīng)用到頂點(diǎn)數(shù)多的環(huán)境中，那么效率將非常低。在 問題二 的基礎(chǔ)上，利用 歐式距離斯坦納最小樹的逐步調(diào)優(yōu)法進(jìn)行相關(guān) 擾動 ， 最終 確定斯坦納點(diǎn) 并進(jìn)行驗算 。 因此，第 7 步的重復(fù)是必要的，反復(fù)多次調(diào)優(yōu)，才能逐步逼近最優(yōu)位置。 3 和 4，知道大道預(yù)設(shè)的最大迭代次數(shù)位置，此時的最好解記為*T 。這里不直接選樹長最短者來調(diào)優(yōu)，是為了避免算法陷入 局部極值，不是 最短的樹也有機(jī)會被抽中。并記? ?m in m in | 1 , 2 ,iX x i n??， ? ?m a x m a x | 1 , 2 ,iX x i n??， ? ?m in m in | 1, 2 ,iY y i n??， ? ?m a x m a x | 1 , 2 ,iY y i n??。 性質(zhì) 4 歐式斯坦納最小樹的每個斯坦納點(diǎn)都 必定包含在全部正則點(diǎn)的最小凸包內(nèi)。judge 中再無負(fù)數(shù)元素，可驗證得到修改后的道路滿足 題中各 條件， 即為最優(yōu)解。 下面先 對步驟一所生成的 各 道路中任意兩入口間 最短 的 折線距離 利用Dijkstra 算法進(jìn)行 求解，儲存到矩陣中，設(shè)這個矩陣用 D 表示 ， D = 設(shè)儲存這兩入口間 直線 距離的矩陣用 distance 表示 ， distance = 將 D 矩陣和 倍的 distance 矩陣 進(jìn)行作差， 得到矩陣 judge ， 將矩陣 D 和 倍的 矩陣 distance 作差得到矩陣 judge ， judge = 找出 judge 中的 負(fù)數(shù)（即不符合要求）對應(yīng)的道路， 即 15PP? 和 25PP? 兩kruskal 算法得出的最小樹 對應(yīng)的 路徑圖 （初步結(jié)果） 10/33 條折線道路大于兩入口直線距離的 倍，需要進(jìn)行 人工合理化調(diào)整修改。 其中，將任意兩點(diǎn)間的距離即作為該邊的權(quán)。是一個包含 G 中所有定點(diǎn)的子圖，那么 G 39。 考慮 到 重建模型的復(fù)雜性和時間的緊迫性， 我們利用了問題二所建模型， 針對問題二得到的結(jié)果，在此基礎(chǔ)上進(jìn)行 了 相關(guān)優(yōu)化，直到 獲得 最優(yōu)解。 這來源于實際中公園內(nèi)的景點(diǎn)及設(shè)施都是在設(shè)計公園道路后才建的情況。 . 問題一 的 分析 問題一規(guī) 定了一些必須經(jīng)過的點(diǎn) 。給出道路交叉點(diǎn)的坐標(biāo)，畫出道路設(shè)計，計算新修路的總 2/33 路程。 假設(shè)主要設(shè)計對象為一個矩形公園，其相關(guān)數(shù)據(jù)為：長 200 米，寬 100 米，1 至 8 各入口的坐標(biāo)分別為： ? ? ? ? ? ? ? ?1 2 3 42 0 , 0 , 5 0 , 0 , 1 6 0 , 0 , 2 0 0 , 5 0 ,P P P P? ? ? ? ? ? ? ?5 6 7 81 2 0 , 1 0 0 , 3 5 , 1 0 0 , 1 0 , 1 0 0 , 0 , 2 5P P P P. 根據(jù)題目所給數(shù)據(jù)，運(yùn)用數(shù)學(xué)建模方法 ，將實際復(fù)雜的問題理想模型簡化，設(shè)計 出 滿足題目要求的公園內(nèi)道路， 有很重要的 現(xiàn)實 意義。步驟一利用 kruskal 算法生成 總 道路和 的 最小樹，步驟二用 Dijkstra 算法對 步驟一生成的道路 用是否滿足 “ 任意兩入口間最短道路長小于二者連線的 倍 ” 這一條件進(jìn)行驗算 ，對于個別不滿足的道路進(jìn)行微調(diào)和 修改。 最終方案 中 得到的道路總長度為 米 。 . 問題要求 從實際情況出發(fā)， 對 道路的設(shè)計有以下幾個要求： 1) 讓任意兩個入口相連（可以利用公園四周的邊， 即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長）； 2) 任意的兩個入口之間的最短道路長不大于兩點(diǎn)連線的 倍； 3) 公園內(nèi)新修的道路只能 通過 8 個路口 與四周 相連 ； 4) 公園內(nèi) 總的道路長度和最小 。 問題三 ：若 公園內(nèi)有一條矩形的湖，新修的道路不能通過，但可以到達(dá)題中湖四周的邊 。 這來源于實際中所修道路要通向那些在公園建設(shè)之前就已存在 的 觀賞景點(diǎn) 的 情況。用數(shù)學(xué)模型分析解決這一問題對此類情況有重要意義。 3. 模型 假設(shè) 1) 假設(shè)所有道路均為直線； 2) 假設(shè) 任意兩點(diǎn)間均可 修建 道路 ，即公園內(nèi)土質(zhì)及其它條件對修路不產(chǎn)生影響（第三問的湖泊除外）； 3) 假設(shè)所有道路均為無向的， 不存在單行道， 即道路 ? ? ? ?,i j j iP P P P和 道 路為同一 條路； 4) 對于問題一，假設(shè)除了 題中 所給 道路交叉 點(diǎn)外，不 再 另 外添加點(diǎn)。稱為 G 的 生成樹 ，如果G 39。 此時，可將距離 矩陣作為 kruskal 算 法 的加權(quán)矩陣，進(jìn)行輸入，即可得到由 kruskal 算法處理的最小樹。 經(jīng)過合理地 分析與嘗試， 我們將 修改后的 公園內(nèi)道路 確定 為： 下面對修改后的道路進(jìn)行合理化 的 驗證。 . 問題二 . 問題 解析 同問題一相比，問題二沒有規(guī) 定公園內(nèi)必須通過的點(diǎn)，屬于斯坦納最小生成樹問題。 添加斯坦納點(diǎn)的斯坦納最小樹，往往會比 不添加斯坦納點(diǎn)的最優(yōu)樹的長度更短些。 根據(jù)性質(zhì) 4，輔助點(diǎn)的投放范圍可以控制在矩形? ? ? ?m i n , m a x m i n , m a xR X X Y Y??之內(nèi)。上述過程完成后，還需做最后的調(diào)整 ： 刪掉 1 度和 2 度的輔助點(diǎn) （ 若有的話 ） ，利用 求解斯坦納點(diǎn)坐標(biāo)的計算 式，并把 3 度輔助點(diǎn)調(diào)整到最優(yōu) 位置 ，使其變?yōu)樗固辜{點(diǎn)。 *T 中輔助點(diǎn)的度。 14/33 . 模型建立 與求解、檢驗 根據(jù)上述的逐步調(diào)優(yōu)法，由本題 8n? ，隨機(jī)分布 k ? ?1,2, ,6k ? 個斯坦納點(diǎn)，通過離散概率隨機(jī)抽取相應(yīng)的斯坦納點(diǎn)進(jìn)行擾動，直到得到最優(yōu)解 ，并解出新修路的總長度為 米 。 . 模型建立 與求解、檢驗 根據(jù)問題二的理論依據(jù)，因為 有 2 5 6,P P P 三個點(diǎn)，故只需要添加一個斯坦納點(diǎn)即可。 經(jīng)查閱相關(guān)文獻(xiàn) [2]后，我們認(rèn)為利用二叉堆來進(jìn)行優(yōu)化，便可快速訪問到具有最小值的點(diǎn)，時間代價僅為 ? ?logOn。在 Dijkstra 算法中，由于累計權(quán)值決定的最短路徑具有優(yōu)先程度差異特征，所以若將未被處理的頂點(diǎn)的最短路徑 D 值構(gòu)造優(yōu)先級隊列，則可大大提高算法的效率。 所以，將未被處理的頂點(diǎn)以 D 值大小為順序保存在一個最小堆中，可以使用 ? ?logOn次搜索找出下一個最近頂點(diǎn)。若當(dāng)前螞蟻的所有的路徑都終止時，螞蟻在該輪 迭代中搜索節(jié)點(diǎn)的過程也終止。福州 ：福州大學(xué)學(xué)報（自然科學(xué)版）， 20xx。 附件 1 Kruskal函數(shù) function Kruskal(w,MAX) %此程序為最小支撐樹的 Kruskal算法實現(xiàn) %w 為無向圖的距離矩陣，故為對稱矩陣 %MAX 為距離矩陣 中∞的實際輸入值 %時間： 20xx 年 6 月 22 日 0:07:53 len=length(w)。 %去掉無用邊 [~,index]=sort(edge(:,1))。 %截短 index 矩陣，保留前 len1 項 %%%%%%%%%%%% 結(jié)果顯示 %%%%%%%%%%%%% s=sprintf(39。)。\n \t (%d,%d)\t %d\t %s\t39。 while 1 num=length(index)。 index_tmp(count)=index(i)。 % distance vector path=[]。 end count=count+1。 end path=zeros(1,2*n)。 t=p。 path=path(1:count)。 300 300 300 0 130 300 300 300 300 300 300 300。 300 300 300 300 300 300 300 300 300 300 300 0]。 d(p,q)=dijkstra(dist,p,q)。Xc,amp。 Xd=(Xa+Xc)/2+*(YaYc)/2。 } 附件 5 問題二中部分斯坦納點(diǎn)擾動過程 一個點(diǎn)修改（ ， ） a=[20,50,160,200,120,35,10,0,。 30 0 110 300 300 300 300 300 300。 s=sqrt((x(i)x(j)).^2+(y(i)y(j)).^2)。 judge(p,q)=*distance(p,q)d(p,q)。 dist =[ 0 30 300 300 300 300 300 300 300 300。 300 300 300 300 300 300 300 300 0 300。 for p=1:1:8 for q=(p+1):1:8 distance(p,q)=sqrt((x(p)x(q