建模論文__公園內(nèi)道路設(shè)計(jì)-文庫(kù)吧資料
2025-02-12 07:10本頁(yè)面
【正文】 int delta_plus。 class Node { int x。 import .*。 import .*。 八 參考文 獻(xiàn) 【 1】《 MATLAB 程序設(shè)計(jì)及應(yīng)用》許麗佳 穆炯 清華大學(xué)出版社 2021 【 2】《最優(yōu)化理論與方法》傅英定 成孝予 唐應(yīng)輝 國(guó)防工業(yè)出版社2021 【 3】《優(yōu)化技術(shù)與 MATLAB 工具箱》趙繼俊 機(jī)械工業(yè)出版社 2021 【 4】《最優(yōu)化方法 —— MATLAB 應(yīng)用》黃雍檢 陶冶 錢祖平 人民郵電出版社 2021 【 5】《運(yùn)籌學(xué)（數(shù)學(xué)規(guī)劃篇）》呂蓬 潘志 清華大學(xué)出版社北京交通大學(xué)出版社 22 附錄 /********************************************/ /* */ /* Copyright (C) 1997, 1998, 2021 K. Ikeda */ /********************************************/ import .*。 解決該問題時(shí)，我們查閱了有關(guān)數(shù)學(xué)建模和運(yùn)籌學(xué)最優(yōu)化的相關(guān)書籍，該模型中所提到的 Floyd 算法，歐拉回路和動(dòng)態(tài)規(guī)劃的相關(guān)方 21 法均可以直接使用，利用這些方法可以快速方便地解決諸如求最短路徑等一些城市規(guī)劃與園林建設(shè)中的實(shí)際問題。 模型建立時(shí)忽略了題目所未給出的人為因素和自然因素對(duì)公園內(nèi)道路總和的影響，在實(shí)際中時(shí)建議考慮人為因素和自然因素對(duì)所設(shè)計(jì)的道路結(jié) 果的影響。 (Dijkstra 算 法見附錄三） 20 如圖所示即為最短的道路設(shè)計(jì)方法。當(dāng)平面中有 k 個(gè)凸障礙物并且其邊界至多相交兩次時(shí)， Rohnert 給出的算法能找到平面中任意兩點(diǎn)之間的最短路徑，其時(shí)間復(fù)雜性為 O(nlogn+k^2)。 Rohnert 還給出平面中避開 k個(gè)凸障礙物最短路徑的 O(knlogn)時(shí)間和 O(n)空間的算法。這個(gè)時(shí)間限界在 O(k^2logn+n)時(shí)間和 O(n+k^2)空間預(yù)處理障礙物的條件下達(dá)到。平面上沒有最短路徑的 0(n^2)算法能處理避開 n 條任意相交的線段。當(dāng) n 是平行線段集合時(shí)， Lee 和 Preparata 提出 θ(nlogn) 平面掃描算法。 注意 ， 如果使用可視圖方法，那么對(duì)限界 0(n^2)將不可能改進(jìn)。Welzl 等人利用可視圖給出了求解平面上 n 條線段的 ESPO 問題的算 19 法，該算法要求 0(n^2)時(shí)間。 下面結(jié)合最短路徑問題簡(jiǎn)單介紹一下 Dijkstra 算法： 18 最短路徑問題： 在聯(lián)結(jié)圖 G=(V,E)中， 頂點(diǎn)集 E R+（即是權(quán)值為正） ，在點(diǎn)集 V中的固定頂點(diǎn) s，尋找 s 到 V 中各頂點(diǎn) v 的最短路徑 . Dijkstra 算法 : Dijkstra 算法是一種解決最短路徑問題的非常有效的算法，時(shí)間復(fù)雜度為 O(|V|2)： i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v u0. If |V| = 1 then stop, otherwise go to step 2. each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v. a vertex v which minimizes {L(v): v in V\Si}, say ui+1. Si+1 = Si cup {ui+1}. i by i+1. If i=|V|1 then stop, otherwise go to step i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v u0. If |V| = 1 then stop, otherwise go to step 2. 對(duì)于該問題還有一些更好的算法，下面作一些簡(jiǎn)單的介紹： 利用最短路徑映射 SPM(s,Ω) 在 O(n(k+logn))時(shí)間內(nèi)求解任意多邊形障礙物的 ESPO 問題的方法是 由 Reif 和 Storer 提出的。利用 Dijkstra 的最短路算法和可視圖算法可以求解ESPO 問題，其時(shí)間復(fù)雜性為 0(n^2)。 (見圖三 ) 平面中的 ESPO 問題在多項(xiàng)式時(shí)間內(nèi)可以求解，而 E^3(三維空間 )中具有多面體障礙物時(shí)確定最短路徑長(zhǎng)度的問題是 NP 難的 ,問題三不考慮此問題 。 17 最后答案 如圖所示即為最短的道路設(shè)計(jì)方法。 2） 根據(jù)各點(diǎn)間相互到達(dá)信息知 35 36VV? 、 49 45VV? 、 34 39VV? 間沒有直接通路，不符合完全圖條件；用第一步得到的從 iV 到 jV 的最短路徑 (程序源代碼見附件 3)去替換使不等式不成立的那些弧長(zhǎng) ijW ，使原網(wǎng) 絡(luò)圖轉(zhuǎn)化為增廣完全圖，得到最優(yōu)化路線。 16 1）根據(jù)給出的各點(diǎn)位置坐標(biāo)及互相到達(dá)信息，用 MATLAB 編程求解各 點(diǎn)之 間的距離，用 Floyd 算法得到任意兩點(diǎn)間的最短距離（ Floyd 算法源程序見附件 1） 上述解法中的 Floyd 算法用于求任意兩點(diǎn)間的最短距離，其程序流程如下：（注： D(i， j)—— i 到 j 的距離； R(i， j)—— i 到 j 的插入點(diǎn)。 而具有這種回路的圖稱為歐拉圖 (簡(jiǎn)稱 E 圖 ).或者：一副圖，尋找一條只通過每條邊一次的路徑叫做歐拉路徑．如果這條路徑的起點(diǎn)和終點(diǎn)是同一點(diǎn)，那么這條路徑叫做歐拉回路． 有關(guān)的問題即是歐拉回路問題，建議參考哥尼斯堡七橋問題或一筆畫問題。 現(xiàn)定義一個(gè) n 階方陣序列 D（ 1）， D（ 0）， D（ 1），…， D（ k），…， D（ n1） 其中 D（ 1） [i][j]=arcs[i][j] D（ k） [i][j]=Min{ D（ k1） [i][j], D（ k1） [i][k]+D（ k1） [k][j]} 15 0≤ k≤ n1 上述公式中， D（ 1） [i][j]是從 Vi 到 Vj 的中間頂點(diǎn)序號(hào)不大于 k 的最短路徑長(zhǎng)度； D（ n1） [i][j]是從 Vi 到 Vj 的最短路徑長(zhǎng)度。 經(jīng)過 n 次比較之后，最后求得的便是從 Vi 到 Vj 的最短路徑。 然后，再增加一個(gè)頂點(diǎn) V2 繼續(xù)進(jìn)行這個(gè)試探過程。 在此路徑上再增加一個(gè)頂點(diǎn) V1，也就是說(shuō)，如果（ Vi，… V1）和（ V1，… Vj）分別是當(dāng)前找到的中間頂點(diǎn)序號(hào)不大于 0 的最短路徑，那么，（ Vi，… V1，… Vj）就有可能是從 Vi 到 Vj 的中間頂點(diǎn)序號(hào)不大于 1 的最短路徑。首先考慮從 Vi 到 Vj 經(jīng)過中間頂點(diǎn) V0 的路徑（ Vi， V0， Vj） 14 是否存在，也就是判斷弧（ Vi， V0）和（ V0， Vj）是否存在。弗洛伊德算法依次找從 Vi 到 Vj，中間經(jīng)過結(jié)點(diǎn)序號(hào)不大于 0 的最短路徑，不大于 1 的最短路徑，…直到中間頂點(diǎn)序號(hào)不大于 n1 的最短路徑，從中選取最小值，即為 Vi到 Vj 的最短路徑。 定義 算法 算法的數(shù)據(jù)結(jié)構(gòu) Floyd 算法采用圖的帶權(quán)鄰接矩陣存儲(chǔ)結(jié)構(gòu)。 分析題目可知，問題二沒有給出確定的交叉點(diǎn)，也就是說(shuō)公園內(nèi)道路的交叉點(diǎn)可以在任意位置。建立模型并給出算法。 7 ⑴ 假設(shè)選取 P1 作為入口點(diǎn)，其他作為出口點(diǎn) ① 都經(jīng)過至少一個(gè)交叉點(diǎn) 當(dāng) k=2 時(shí)： 由結(jié)點(diǎn) A 到達(dá)出口有 f2(S2=A） =min｛ ， ｝ = （選擇 P6） 由結(jié)點(diǎn) B 到達(dá)出口有 f2(S2=B） =min｛ ， 41｝ =41 （選擇 P2） 由結(jié)點(diǎn) C 到達(dá)出口有 f2(S2=C） =min｛ ， ｝ = （選擇 P3） 由結(jié)點(diǎn) D 到達(dá)出口有 f2(S2=D） =min｛ ， ｝ = （選擇 P5） 當(dāng) k=1 時(shí)： f1（ S1=B） =min｛ ｝ = （選擇 B 點(diǎn)） ② 不經(jīng)過交
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1