【正文】 賞景點(diǎn)或是休息座椅，所建設(shè)道路要經(jīng)過(guò)這些地點(diǎn)。給出道路交叉點(diǎn)的坐標(biāo)，畫(huà)出道路設(shè)計(jì)，計(jì)算新修路的總 2/33 路程。建立模型并給出算法。 假設(shè)主要設(shè)計(jì)對(duì)象為一個(gè)矩形公園，其相關(guān)數(shù)據(jù)為：長(zhǎng) 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é)建模方法 ，將實(shí)際復(fù)雜的問(wèn)題理想模型簡(jiǎn)化，設(shè)計(jì) 出 滿(mǎn)足題目要求的公園內(nèi)道路， 有很重要的 現(xiàn)實(shí) 意義。 對(duì)問(wèn)題三， 我們利用題中的限制條件，分析了所給的人工湖位置與入口的坐標(biāo)的數(shù)據(jù)特點(diǎn)， 先確定了在不加道路交叉點(diǎn)情況下 ，僅利用湖四周的道路 ， 即可滿(mǎn)足 任意 入口間 最 短路徑 倍 條件 的 可利用的 最短 道路，再利用問(wèn)題二中的方法添加 了一個(gè) 斯坦納點(diǎn)， 并在其鄰域內(nèi)進(jìn)行 擾動(dòng)后得到最優(yōu)解。步驟一利用 kruskal 算法生成 總 道路和 的 最小樹(shù)，步驟二用 Dijkstra 算法對(duì) 步驟一生成的道路 用是否滿(mǎn)足 “ 任意兩入口間最短道路長(zhǎng)小于二者連線的 倍 ” 這一條件進(jìn)行驗(yàn)算 ，對(duì)于個(gè)別不滿(mǎn)足的道路進(jìn)行微調(diào)和 修改。 公園內(nèi)道路設(shè)計(jì)最優(yōu)問(wèn)題 摘 要 對(duì)于題中所給的道路設(shè)計(jì)問(wèn)題，即研究在約束條件下最小生成樹(shù)問(wèn)題。 最終方案 中 得到的道路總長(zhǎng)度為 米 。 經(jīng)驗(yàn)算確定， 最終方案得到的道路總長(zhǎng)度為 米。 . 問(wèn)題要求 從實(shí)際情況出發(fā)， 對(duì) 道路的設(shè)計(jì)有以下幾個(gè)要求： 1) 讓任意兩個(gè)入口相連（可以利用公園四周的邊， 即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)）； 2) 任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的 倍； 3) 公園內(nèi)新修的道路只能 通過(guò) 8 個(gè)路口 與四周 相連 ； 4) 公園內(nèi) 總的道路長(zhǎng)度和最小 。畫(huà)出道路設(shè)計(jì)，計(jì)算新修路的總路程。 問(wèn)題三 ：若 公園內(nèi)有一條矩形的湖，新修的道路不能通過(guò)，但可以到達(dá)題中湖四周的邊 。而這些地點(diǎn)又分為修公園前就有的和公園建好后才修建的，還可分為道路可以通過(guò)的和不可以通過(guò)的（如湖、花壇等），這些情況都對(duì)應(yīng)于不同的道路設(shè)計(jì)方案。 這來(lái)源于實(shí)際中所修道路要通向那些在公園建設(shè)之前就已存在 的 觀賞景點(diǎn) 的 情況。根據(jù)所學(xué)知識(shí)、題中數(shù)據(jù)特點(diǎn)和結(jié)果要求，我們選擇使用 kruskal 算法解決最小樹(shù)問(wèn)題。用數(shù)學(xué)模型分析解決這一問(wèn)題對(duì)此類(lèi)情況有重要意義。 因 此對(duì)于問(wèn)題三的研究很有現(xiàn)實(shí)意義。 3. 模型 假設(shè) 1) 假設(shè)所有道路均為直線； 2) 假設(shè) 任意兩點(diǎn)間均可 修建 道路 ，即公園內(nèi)土質(zhì)及其它條件對(duì)修路不產(chǎn)生影響（第三問(wèn)的湖泊除外）； 3) 假設(shè)所有道路均為無(wú)向的， 不存在單行道， 即道路 ? ? ? ?,i j j iP P P P和 道 路為同一 條路； 4) 對(duì)于問(wèn)題一，假設(shè)除了 題中 所給 道路交叉 點(diǎn)外，不 再 另 外添加點(diǎn)。 . 步驟 一： 通過(guò)分析道路長(zhǎng)度和最短的要求， 我們發(fā)現(xiàn)這個(gè)問(wèn)題和最小生成樹(shù)問(wèn)題聯(lián)系最為緊密，于是考慮用 貪心法求解最小生成樹(shù) 的 kruskal 算法 的一些研究成果以及相關(guān)的圖論知識(shí)來(lái)建立該問(wèn)題的數(shù)學(xué)模型。稱(chēng)為 G 的 生成樹(shù) ，如果G 39。此時(shí)以 V 為頂點(diǎn)集，以取到的 n1條邊為邊集的圖即為最優(yōu)樹(shù)。 此時(shí)，可將距離 矩陣作為 kruskal 算 法 的加權(quán)矩陣，進(jìn)行輸入，即可得到由 kruskal 算法處理的最小樹(shù)。 Dijkstra 算法是按長(zhǎng)度遞增的次序生成從源點(diǎn) s 到其他定點(diǎn)的最短路徑，則當(dāng)前正在生成的最短路徑上除終點(diǎn)以外，其余的頂點(diǎn)的最短路徑均已生成（將源點(diǎn)的最短路徑看作是已生成的源點(diǎn)到其自身的長(zhǎng)度為 0 的路徑）。 經(jīng)過(guò)合理地 分析與嘗試， 我們將 修改后的 公園內(nèi)道路 確定 為： 下面對(duì)修改后的道路進(jìn)行合理化 的 驗(yàn)證。D 矩陣和 倍的 distance 矩陣進(jìn)行作差，得到矩陣 39。 . 問(wèn)題二 . 問(wèn)題 解析 同問(wèn)題一相比，問(wèn)題二沒(méi)有規(guī) 定公園內(nèi)必須通過(guò)的點(diǎn)，屬于斯坦納最小生成樹(shù)問(wèn)題。 由于本問(wèn)題可以自由 添 加道路交叉點(diǎn)，我們引入 SRT 的一些性質(zhì)： 性質(zhì) 1 SRT 上每個(gè)點(diǎn)之多關(guān)聯(lián)三條邊，而每個(gè)斯坦納點(diǎn)恰好關(guān) 聯(lián)三條邊。 添加斯坦納點(diǎn)的斯坦納最小樹(shù)，往往會(huì)比 不添加斯坦納點(diǎn)的最優(yōu)樹(shù)的長(zhǎng)度更短些。因此，? ?? ? 3 0 .8 6 62smLRLR ??。 根據(jù)性質(zhì) 4，輔助點(diǎn)的投放范圍可以控制在矩形? ? ? ?m i n , m a x m i n , m a xR X X Y Y??之內(nèi)。然后按此分布隨機(jī)抽樣，樹(shù)長(zhǎng)越短，被抽 中 的概率就越大。上述過(guò)程完成后，還需做最后的調(diào)整 ： 刪掉 1 度和 2 度的輔助點(diǎn) （ 若有的話 ） ，利用 求解斯坦納點(diǎn)坐標(biāo)的計(jì)算 式，并把 3 度輔助點(diǎn)調(diào)整到最優(yōu) 位置 ，使其變?yōu)樗固辜{點(diǎn)。 1||k kS T?，21kk njjSPS???? ， ? ?1, 2, , 2kn??，這樣得到了一個(gè)離散的概率分布，并記1kkiiqP???， ? ?1, 2, , 2kn??。 *T 中輔助點(diǎn)的度。按照斯坦納點(diǎn)的坐標(biāo)計(jì)算公式，把該 3 度輔助點(diǎn)移動(dòng)到該坐標(biāo)位置上，調(diào)整后得到新的 *T 。 14/33 . 模型建立 與求解、檢驗(yàn) 根據(jù)上述的逐步調(diào)優(yōu)法，由本題 8n? ，隨機(jī)分布 k ? ?1,2, ,6k ? 個(gè)斯坦納點(diǎn)，通過(guò)離散概率隨機(jī)抽取相應(yīng)的斯坦納點(diǎn)進(jìn)行擾動(dòng)，直到得到最優(yōu)解 ，并解出新修路的總長(zhǎng)度為 米 。為此，我們?cè)诜治隽藬?shù)據(jù)特點(diǎn)及湖位置的基礎(chǔ)上，根據(jù)問(wèn)題一中的計(jì)算任意兩入口間折線距離的方法，我們 確定了 在不添加道路交叉點(diǎn)的情況下 就可滿(mǎn)足折線距離小于兩入口直線距離 倍的條件的 幾條 邊 。 . 模型建立 與求解、檢驗(yàn) 根據(jù)問(wèn)題二的理論依據(jù)，因?yàn)?有 2 5 6,P P P 三個(gè)點(diǎn)，故只需要添加一個(gè)斯坦納點(diǎn)即可。 6. 結(jié)果表示 . 問(wèn)題一 16/33 道路設(shè)計(jì)圖： 問(wèn)題一方案 新修路的總路程： 米 . 問(wèn)題二 道路設(shè)計(jì)圖： 問(wèn)題二方案 新修路的總長(zhǎng)度： 米 . 問(wèn)題三 道路設(shè)計(jì)圖： 17/33 問(wèn)題三方案 新修路的總長(zhǎng)度： 米 7. 模型的評(píng)價(jià) 、優(yōu)化及 推廣 . 模型的評(píng)價(jià) 1) 問(wèn)題一的求解思路是先用 kruskal 算法得到是不帶環(huán)的最小樹(shù)， 把 邊加入最小樹(shù)再利用 Dijkstra 算法 依據(jù)題中條件進(jìn)行驗(yàn)算，這樣得到的結(jié)果可能不是最優(yōu)解； 2) 問(wèn)題一中，模型一 利用 kruskal 算法 和 Dijkstra 算法 分兩個(gè)步驟得到精確最優(yōu)解的前提是假設(shè)所修道路均為直線， 公園內(nèi)部有且僅有給出的四個(gè)道路交叉點(diǎn) 。 經(jīng)查閱相關(guān)文獻(xiàn) [2]后，我們認(rèn)為利用二叉堆來(lái)進(jìn)行優(yōu)化，便可快速訪問(wèn)到具有最小值的點(diǎn)，時(shí)間代價(jià)僅為 ? ?logOn。經(jīng)過(guò)一次循環(huán)后，紅點(diǎn)集 ??Ss??? ，其余各點(diǎn)的估計(jì)最短距離 D 值更新為該點(diǎn)到源點(diǎn)而中間不經(jīng)過(guò)任何點(diǎn)的邊的權(quán)值。在 Dijkstra 算法中，由于累計(jì)權(quán)值決定的最短路徑具有優(yōu)先程度差異特征，所以若將未被處理的頂點(diǎn)的最短路徑 D 值構(gòu)造優(yōu)先級(jí)隊(duì)列，則可大大提高算法的效率。堆有最大堆和最小堆兩種。 所以，將未被處理的頂點(diǎn)以 D 值大小為順序保存在一個(gè)最小堆中，可以使用 ? ?logOn次搜索找出下一個(gè)最近頂點(diǎn)。針對(duì)這一問(wèn)題， 可以采用 多路徑并行搜索蟻群算法的并行搜索機(jī)制進(jìn)行相關(guān)優(yōu)化。若當(dāng)前螞蟻的所有的路徑都終止時(shí)，螞蟻在該輪 迭代中搜索節(jié)點(diǎn)的過(guò)程也終止。求解歐式距離斯坦納最小樹(shù)的逐步調(diào)優(yōu)法。福州 ：福州大學(xué)學(xué)報(bào)（自然科學(xué)版）， 20xx。 [4] 楊凌云。 附件 1 Kruskal函數(shù) function Kruskal(w,MAX) %此程序?yàn)樽钚≈螛?shù)的 Kruskal算法實(shí)現(xiàn) %w 為無(wú)向圖的距離矩陣，故為對(duì)稱(chēng)矩陣 %MAX 為距離矩陣 中∞的實(shí)際輸入值 %時(shí)間： 20xx 年 6 月 22 日 0:07:53 len=length(w)。 edge(count,2)=i。 %去掉無(wú)用邊 [~,index]=sort(edge(:,1))。 %若構(gòu)成圈，則將該邊對(duì)應(yīng)的 index 項(xiàng)標(biāo)記為 0，以便除去 else i=i+1。 %截短 index 矩陣，保留前 len1 項(xiàng) %%%%%%%%%%%% 結(jié)果顯示 %%%%%%%%%%%%% s=sprintf(39。,39。)。,edge_tmp(2),edge_tmp(3),edge_tmp(1),39。\n \t (%d,%d)\t %d\t %s\t39。 end s=strcat(s,s_tmp)。 while 1 num=length(index)。 end index_tmp=zeros(1,num)。 index_tmp(count)=index(i)。 %更新 index end end if isempty(index) %若最后剩下的邊數(shù)為 0，則無(wú)圈 isfind=0。 % distance vector path=[]。 % parent node % the shortest distance for i=1:n1 % BlueSet has n1 nodes temp=zeros(1,n)。 end count=count+1。 for k=1:n if D(k)D(j)+A(j,k) D(k)=D(j)+A(j,k)。 end path=zeros(1,2*n)。 while t~=s amp。 t=p。,... 39。 path=path(1:count)。 j=[2 8 10 4 11 12 7 9 10 12 12]。 300 300 300 0 130 300 300 300 300 300 300 300。 300 300 300 300 300 300 85 0 300 300 300 300。 300 300 300 300 300 300 300 300 300 300 300 0]。 end 25/33 distance=zeros(length(x))。 d(p,q)=dijkstra(dist,p,q)。Xa,amp。Xc,amp。 Xd=(Xa+Xc)/*(YaYc)/2。 Xd=(Xa+Xc)/2+*(YaYc)/2。 Xf=((Kbd*XbYb)(Kce*XcYc))/(KbdKce)。 } 附件 5 問(wèn)題二中部分斯坦納點(diǎn)擾動(dòng)過(guò)程 一個(gè)點(diǎn)修改（ ， ） 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 85 0 25 300 300。 s=sqrt((x(i)x(j)).^2+(y(i)y(j)).^2)。 %distance 為任意兩點(diǎn)間距離矩陣 d=zeros(8)。 judge(p,q)=*distance(p,q)d(p,q)。 Kruskal(w,300) x=[20,50,160,200,120,35,10,0,]。 dist =[ 0 30 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 0 300。 28/33 dist(j(k),i(k))=s(k)。 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)。0,0,0,50,100,100,100,25,]。 i=[1 1 2 3 3 5 6 6 9]。 300 110 0 300 300 300 300 300 300 300。 300 300 300 300 300 25 0 85 300 30