建模論文公園內(nèi)道路設(shè)計(jì)

1、參賽隊(duì)編號(hào)：XjdB題 公園內(nèi)道路設(shè)計(jì)一 摘要隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人們生活水平的提高，人們對(duì)最優(yōu)化的要求越來(lái)越高，對(duì)于公園道路的設(shè)計(jì)問(wèn)題也要考慮到很多。本文就針對(duì)所給的路線，要求設(shè)計(jì)最佳路線的問(wèn)題展開(kāi)研究，運(yùn)用Floyd算法，運(yùn)籌學(xué)最優(yōu)化原理，動(dòng)態(tài)規(guī)劃，圖論對(duì)各問(wèn)題進(jìn)行求解。對(duì)于問(wèn)題一，先在公園任意門(mén)作為入口，分別以其他7個(gè)門(mén)作為出口，運(yùn)用窮舉法求得出入口兩地點(diǎn)間且要經(jīng)過(guò)公園內(nèi)的道路交叉點(diǎn)的最短距離。模型一建立TSP問(wèn)題圖論模型，找到增廣完全圖作為精確最優(yōu)解，并由此求得最短路程為。對(duì)于問(wèn)題二，采用Floyd算法計(jì)算出任意兩個(gè)點(diǎn)之間的最短距離，再根據(jù)歐拉回路原理，以及動(dòng)態(tài)規(guī)劃原理，運(yùn)用matla

2、b軟件運(yùn)行處相應(yīng)的圖，求得符合條件的最短路徑，提高了運(yùn)算的效率和科學(xué)性。對(duì)于問(wèn)題三，要求在問(wèn)題二的基礎(chǔ)上進(jìn)行改進(jìn)，方法與問(wèn)題二的解決方法類(lèi)似，最后再依據(jù)運(yùn)籌學(xué)中的動(dòng)態(tài)規(guī)劃原理，運(yùn)用歐幾里得方法，在公園內(nèi)道路不通過(guò)湖的條件下，設(shè)計(jì)出最短路徑。最后本文還結(jié)合實(shí)際情況，對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了分析與評(píng)價(jià)，并提出了改進(jìn)方向。 關(guān)鍵字： 動(dòng)態(tài)規(guī)劃 Floyd算法 圖論 最優(yōu)化原理 逆推法 歐幾里得算法二 問(wèn)題重述1.問(wèn)題背景隨著經(jīng)濟(jì)的發(fā)展和人民生活水平的提高，公園的道路設(shè)計(jì)以及美化越來(lái)越重要。對(duì)設(shè)計(jì)師而言，設(shè)計(jì)出最經(jīng)濟(jì)美觀的道路已經(jīng)成為必不可少的本領(lǐng)。而對(duì)大學(xué)而言，設(shè)計(jì)出最合理的道路已經(jīng)成為彰顯大學(xué)文化氣息

3、和人文精神的一點(diǎn)?；谏鲜銮闆r，根據(jù)題目所給數(shù)據(jù)，運(yùn)用數(shù)學(xué)建模方法，對(duì)公園道路進(jìn)行設(shè)計(jì)。制定出合理的路線，使得公園內(nèi)道路路徑總和最小，獲得最優(yōu)化的解決辦法，具有重大的實(shí)際意義。2.實(shí)際現(xiàn)狀對(duì)最短路徑總和的制定有以下幾個(gè)特點(diǎn)：1）大學(xué)本身要考慮公園道路美觀問(wèn)題；2）大學(xué)本身要考慮經(jīng)濟(jì)問(wèn)題；3.問(wèn)題提出從一個(gè)大學(xué)建設(shè)公園的實(shí)際情況和上述特點(diǎn)出發(fā)，依據(jù)相關(guān)數(shù)據(jù)：1.假定公園內(nèi)確定要使用4個(gè)道路交叉點(diǎn)為：A(50,75),B(40,40),C(120,40),D(115,70)。問(wèn)如何設(shè)計(jì)道路可使公園內(nèi)道路總路程最短。2.現(xiàn)在公園內(nèi)可以任意修建道路，如何在滿(mǎn)足條件下使總路程最少。建立模型并給出算法。給

4、出交叉點(diǎn)的坐標(biāo)，畫(huà)出道理設(shè)計(jì)，計(jì)算出新修路的總路程。3.若公園內(nèi)有一條矩形的湖，新修的道路不能通過(guò)，但可以到達(dá)湖四周的邊。并且重復(fù)完成問(wèn)題二的任務(wù)。三、符號(hào)說(shuō)明Sk：狀態(tài)變量 Pi入口點(diǎn)fn():函數(shù)名 S=u:第u階段 Vi：某個(gè)頂點(diǎn) Vij:從i到j(luò)的路徑G表示某個(gè)區(qū)域 O(nlogn+k2)時(shí)間 O(n+k2)空間四 問(wèn)題分析本題是西安某大學(xué)計(jì)劃為建一個(gè)公園，而需要建立一個(gè)數(shù)學(xué)模型去設(shè)計(jì)道路，不僅讓任意兩個(gè)路口相連，而且使得公園內(nèi)道路路線總和最短。從題目中我們可以看出，這是一個(gè)應(yīng)用數(shù)學(xué)知識(shí)解決實(shí)際問(wèn)題的例子，是用數(shù)學(xué)模型求最優(yōu)化問(wèn)題。第一問(wèn)要求過(guò)給定的4個(gè)交叉點(diǎn)A(50,75)，B(40

5、,40)，C(120,40)，D(115,70），建立模型來(lái)使得道路總和最短。我們采用逆推法和動(dòng)態(tài)規(guī)劃相結(jié)合的方法來(lái)解決問(wèn)題，計(jì)算出最短路程。第二問(wèn)沒(méi)有給定的道路交叉點(diǎn)，自由度較高，我們首先采用Floyd算法求解出任意兩點(diǎn)間的最短距離，再根據(jù)歐拉回路的方法求出路徑總和最短的設(shè)計(jì)路線，確定出符合條件的道路交叉點(diǎn)，畫(huà)出最優(yōu)的道路設(shè)計(jì)方案。第三問(wèn)：有一塊比較重要的就是學(xué)校公園道路的設(shè)計(jì)，難點(diǎn)之一就是有障礙物地點(diǎn)之間的最短路徑問(wèn)題。這個(gè)問(wèn)題不是一個(gè)新問(wèn)題，很久以前就有人提出并解決了這個(gè)問(wèn)題。在歷史上這個(gè)問(wèn)題是計(jì)算幾何學(xué)中的一個(gè)經(jīng)典課題。被稱(chēng)為具有障礙物的歐幾里德最短路徑問(wèn)題(ESP0)。第三問(wèn)的解決辦

6、法是在第二問(wèn)的基礎(chǔ)上拓展得到的，只是要避免我們所設(shè)計(jì)的公園內(nèi)的道路通過(guò)湖，所以我們是在第二問(wèn)設(shè)計(jì)的路線上稍作改進(jìn)，去掉了其中通過(guò)湖的不符合條件的相關(guān)路線，根據(jù)最優(yōu)化和運(yùn)籌學(xué)中的動(dòng)態(tài)規(guī)劃原理，運(yùn)用歐幾里得最短路徑問(wèn)題(ESPO)的解法，可解第三問(wèn)。以上三問(wèn)中所提到的解決方案，都是符合條件的，公園內(nèi)道路路徑總和最短，任意兩點(diǎn)相連，且任意兩點(diǎn)間的連線不超過(guò)兩點(diǎn)間最短路徑的1.4倍（我們這里用橢圓的知識(shí)加以檢驗(yàn)）。五 模型假設(shè)1.假設(shè)公園內(nèi)道路零寬度，不影響交叉點(diǎn)坐標(biāo)，不受自然因素影響；2.假設(shè)交叉點(diǎn)寬度不影響道路長(zhǎng)度；3.假設(shè)公園內(nèi)道路平整；4. 假設(shè)公園草坪完整，不受人為因素影響；六 模型建立與求

7、解問(wèn)題一 該問(wèn)題給出了某公園的八個(gè)入口和要設(shè)定的四個(gè)交叉點(diǎn)，現(xiàn)在需要建立一個(gè)模型去設(shè)計(jì)道路讓任意兩個(gè)入口相連（可以利用公園四周的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)），使總的道路長(zhǎng)度和最小，前提要求是任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍。 通過(guò)分析題目要求，我們發(fā)現(xiàn)該問(wèn)題就是兩點(diǎn)間的最短距離問(wèn)題，這與動(dòng)態(tài)規(guī)劃原理的聯(lián)系最為密切，于是我們考慮選取八個(gè)入口點(diǎn)中的任意兩個(gè)點(diǎn)，將其抽象為兩點(diǎn)間的最短距離，完全動(dòng)態(tài)規(guī)劃最優(yōu)化原理，我們根據(jù)此原理以及圖論來(lái)建立此問(wèn)題的數(shù)學(xué)模型。我們先引入動(dòng)態(tài)規(guī)劃原理的應(yīng)用方法： 動(dòng)態(tài)規(guī)劃方法就是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€

8、的方法。解題步驟如下：1.把問(wèn)題劃分為幾個(gè)階段。2.按階段順序首先考慮最后階段如第四階段的最優(yōu)決策，也就是走哪條路線最短。 3.按階段順序依次考慮第三、第二，第一階段的最優(yōu)決策，為此只需確定每一階段上各初始點(diǎn)的最優(yōu)決策即可。用動(dòng)態(tài)規(guī)劃方法逐段求解時(shí)，每個(gè)階段上的求優(yōu)方法基本相同，而且比較簡(jiǎn)單，每一階段的計(jì)算都要利用上一階段的計(jì)算結(jié)果，因而減少了很多計(jì)算量。階段數(shù)愈多，這種效果愈明顯。 根據(jù)動(dòng)態(tài)規(guī)劃最短路徑這一原理，我們準(zhǔn)備用決策法的逆推法，就是從最后階段開(kāi)始，由后向前逐步遞推求出各點(diǎn)到終點(diǎn)的最短路徑，最后求得由始點(diǎn)到終點(diǎn)的最短路線，即動(dòng)態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)で笞疃搪肪€的一種方法。

9、按照東規(guī)劃的方法，將此過(guò)程劃分為3個(gè)階段，即變量k=1，2；取過(guò)程在各階段所處的位置狀態(tài)為狀態(tài)變量Sk，按逆序算法求解。 假設(shè)選取P1作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 當(dāng)k=2時(shí)： 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min47.2，29.2=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D到達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min44.7=44.7 （

10、選擇B點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min32,30=30 (選擇P2）假設(shè)選取P2作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min47.2，29.2=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7= 44.7 （選擇P1） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D到達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min44.7=44.7 （選擇B點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min110,30=30 (選擇P1）假

11、設(shè)選取P3作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min47.2，29.2=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min80.6=80.6 （選擇P3） 由結(jié)點(diǎn)D到達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min56.6=56.6 （選擇C點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min64,110=30 (選擇P4）假設(shè)選取P4作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有

12、f2(S2=A）=min47.2，29.2=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D到達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min56.6=56.6 （選擇C點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min64,94.3=64 (選擇P3）假設(shè)選取P5作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min47.2，29.2=29.2 （選擇P6）

13、 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D到達(dá)出口有 f2(S2=D）=min88.6，87.3=30.4 （選擇P6） 當(dāng)k=1時(shí)： f1（S1=B）=min30.4=31.4 （選擇D點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min85，94.3=85 (選擇P6）假設(shè)選取P6作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min29.2=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P

14、2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min29.2=29.2 （選擇A點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min25，85=25 (選擇P7）假設(shè)選取P7作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min29.2，67.3=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=5

15、6.6 （選擇P3） 由結(jié)點(diǎn)D達(dá)出口有 f2(S2=D）=min30.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min47.2=47.2 （選擇A點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min25，75.7=25 (選擇P6）假設(shè)選取P8作為入口點(diǎn)，其他作為出口點(diǎn)都經(jīng)過(guò)至少一個(gè)交叉點(diǎn) 由結(jié)點(diǎn)A到達(dá)出口有 f2(S2=A）=min29.2，67.3=29.2 （選擇P6） 由結(jié)點(diǎn)B到達(dá)出口有 f2(S2=B）=min44.7，41=41 （選擇P2） 由結(jié)點(diǎn)C到達(dá)出口有 f2(S2=C）=min56.6，80.6=56.6 （選擇P3） 由結(jié)點(diǎn)D達(dá)出口有 f2(S2=D）=min30

16、.4，87.3=30.4 （選擇P5） 當(dāng)k=1時(shí)： f1（S1=B）=min41.2=41.2 （選擇B點(diǎn)）不經(jīng)過(guò)交叉點(diǎn) f0=min32，75.7=32 (選擇P1）最后答案如圖所示即為最短的道路設(shè)計(jì)方法。最短路徑為804.6.問(wèn)題二 題目要求公園內(nèi)可以任意修建道路，使得在滿(mǎn)足條件下總路程最少。建立模型并給出算法。給出交叉點(diǎn)的坐標(biāo)，畫(huà)出道路設(shè)計(jì)，計(jì)算出新修路的總路程。 分析題目可知，問(wèn)題二沒(méi)有給出確定的交叉點(diǎn)，也就是說(shuō)公園內(nèi)道路的交叉點(diǎn)可以在任意位置。據(jù)此，我們?cè)谠撃Ｐ椭杏肍loyed算法求出兩點(diǎn)間最短距離的基礎(chǔ)上，利用圖論模型，找出歐拉回路作為整體最優(yōu)解，再通過(guò)加入臨近點(diǎn)和去邊的方式優(yōu)化

17、該模型，并將由此得到的歐拉回路作為最優(yōu)化路線。定義1.Floyd算法算法的數(shù)據(jù)結(jié)構(gòu)Floyd算法采用圖的帶權(quán)鄰接矩陣存儲(chǔ)結(jié)構(gòu)。算法基本思想假設(shè)求頂點(diǎn)Vi到Vj的最短路徑。弗洛伊德算法依次找從Vi到Vj，中間經(jīng)過(guò)結(jié)點(diǎn)序號(hào)不大于0的最短路徑，不大于1的最短路徑，直到中間頂點(diǎn)序號(hào)不大于n-1的最短路徑，從中選取最小值，即為Vi到Vj的最短路徑。算法具體描述若從Vi到Vj有弧，則從Vi到Vj存在一條長(zhǎng)度為弧上權(quán)（arcsij ）的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮從Vi到Vj經(jīng)過(guò)中間頂點(diǎn)V0的路徑（Vi，V0，Vj）是否存在，也就是判斷?。╒i，V0）和（V0，Vj）是否存在。若

18、存在，則比較（Vi，Vj）和（Vi，V0，Vj）的路徑長(zhǎng)度取較短的為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于0的最短路徑。 在此路徑上再增加一個(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的最短路徑。將它和已經(jīng)得到的從Vi到Vj中間頂點(diǎn)序號(hào)不大于0的最短路徑相比較，從中選出最短的作為從Vi到Vj中間頂點(diǎn)序號(hào)不大于1的最短路徑。 然后，再增加一個(gè)頂點(diǎn)V2繼續(xù)進(jìn)行這個(gè)試探過(guò)程。一般情況下，若（Vi，Vk）和（Vk，Vj）分別是從Vi到Vk和從Vk到Vj的中間頂點(diǎn)序號(hào)不大于k-1的

19、最短路徑，則將（Vi，Vk，Vj）和已經(jīng)得到的從Vi到Vj的中間頂點(diǎn)序號(hào)不大于k-1的最短路徑相比較，其長(zhǎng)度最短者即為從Vi到Vj的中間頂點(diǎn)序號(hào)不大于k的最短路徑。 經(jīng)過(guò)n次比較之后，最后求得的便是從Vi到Vj的最短路徑。按此方法可同時(shí)求得各對(duì)頂點(diǎn)之間的最短路徑。 現(xiàn)定義一個(gè)n階方陣序列D（-1），D（0），D（1），D（k），D（n-1）其中 D（-1）ij=arcsijD（k）ij=Min D（k-1）ij, D（k-1）ik+D（k-1）kj 0kn-1 上述公式中，D（1）ij是從 Vi到Vj的中間頂點(diǎn)序號(hào)不大于 k的最短路徑長(zhǎng)度；D（n-1）ij是從Vi到Vj的最短路徑長(zhǎng)度。2.歐拉

20、回路 圖 G 的一個(gè)回路,若它通過(guò) G 中每條邊一次且僅一次,則稱(chēng)為歐拉回路。而具有這種回路的圖稱(chēng)為歐拉圖(簡(jiǎn)稱(chēng) E 圖).或者：一副圖，尋找一條只通過(guò)每條邊一次的路徑叫做歐拉路徑如果這條路徑的起點(diǎn)和終點(diǎn)是同一點(diǎn)，那么這條路徑叫做歐拉回路 有關(guān)的問(wèn)題即是歐拉回路問(wèn)題，建議參考哥尼斯堡七橋問(wèn)題或一筆畫(huà)問(wèn)題。歐拉回路的判定規(guī)則：1. 如果通奇數(shù)橋的地方多于兩個(gè)，則不存在歐拉回路；2. 如果只有兩個(gè)地方通奇數(shù)橋，可以從這兩個(gè)地方之一出發(fā)，找到歐拉回路；3. 如果沒(méi)有一個(gè)地方是通奇數(shù)橋的，則無(wú)論從哪里出發(fā)，都能拉回路。4.模型求解1）根據(jù)給出的各點(diǎn)位置坐標(biāo)及互相到達(dá)信息，用MATLAB編程求解各 點(diǎn)之

21、間的距離，用Floyd算法得到任意兩點(diǎn)間的最短距離（Floyd算法源程序見(jiàn)附件1）上述解法中的Floyd算法用于求任意兩點(diǎn)間的最短距離，其程序流程如下：（注：D(i，j)i到j(luò)的距離；R(i，j)i到j(luò)的插入點(diǎn)。）i 輸入：帶權(quán)鄰接矩陣w（i，j）；ii 賦初值：對(duì)所有i，j，d（i，j）=w（i，j），r（i，j）=j，k=1；iii 更新d（i，j），r（i，j）：對(duì)i，j，若d（i，k）+ d（k，j） R+（即是權(quán)值為正） ，在點(diǎn)集V中的固定頂點(diǎn)s，尋找s到V中各頂點(diǎn)v的最短路徑.Dijkstra算法:Dijkstra算法是一種解決最短路徑問(wèn)題的非常有效的算法，時(shí)間復(fù)雜度為 O(|V|

22、2)：1.Set 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. 2.For each v in VSi, replace L(v) by minL(v), L(ui)+dvui. If L(v) is replaced, put a label (L(v), ui) on v. 3.Find a vertex v which minimizes L(v): v in VSi, say ui+1. 4.Let Si+1 = Si cup ui+1.

23、 5.Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 6.Set 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ì)于該問(wèn)題還有一些更好的算法，下面作一些簡(jiǎn)單的介紹：利用最短路徑映射 SPM(s,)在O(n(k+logn)時(shí)間內(nèi)求解任意多邊形障礙物的ESPO問(wèn)題的方法是由Reif和Storer提出的。如果給定SPM(s,)，則在O(logn)時(shí)間內(nèi)可以確定包含t的 域，而在0

24、(b+logn)時(shí)間內(nèi)能夠確定到t的路徑，其中b是路徑上線段的數(shù)目。Welzl等人利用可視圖給出了求解平面上n條線段的ESPO問(wèn)題的算法，該算法要求 0(n2)時(shí)間。不難修改這個(gè)算法使其能處理多邊形障礙物，并且具有相同的時(shí)間復(fù)雜性。注意，如果使用可視圖方法，那么對(duì)限界0(n2)將不可能改進(jìn)。多邊形物體中兩個(gè)物體(而非點(diǎn))之間的最短路徑的0(n2)算法是已知的。當(dāng)n是平行線段集合時(shí)，Lee和Preparata提出(nlogn)平面掃描算法。線段穿過(guò)掃描線并且把最短路徑映射到掃描線。平面上沒(méi)有最短路徑的0(n2)算法能處理避開(kāi)n條任意相交的線段。 Rohnert給出平面中避開(kāi)k個(gè)凸障礙物最短路徑的

25、O(nlogn+k2)時(shí)間的算法。這個(gè)時(shí)間限界在O(k2logn+n)時(shí)間和O(n+k2)空間預(yù)處理障礙物的條件下達(dá)到。預(yù)處理包括構(gòu)造可視圖的子圖。Rohnert還給出平面中避開(kāi)k個(gè)凸障礙物最短路徑的O(knlogn)時(shí)間和O(n)空間的算法。后者不需預(yù)先處理障礙物，而是利用Dijkstra最短路徑算法在線計(jì)算可視性。當(dāng)平面中有k個(gè)凸障礙物并且其邊界至多相交兩次時(shí)，Rohnert給出的算法能找到平面中任意兩點(diǎn)之間的最短路徑，其時(shí)間復(fù)雜性為O(nlogn+k2)。這個(gè)時(shí)間限界在O(nlogn+k3)時(shí)間和O(n+k2)空間預(yù)處理障礙物的條件下達(dá)到。(Dijkstra算法見(jiàn)附錄三）如圖所示即為最短

26、的道路設(shè)計(jì)方法。最短路徑為894.7.七 模型的評(píng)價(jià)與推廣7.1模型的評(píng)價(jià)本題主要運(yùn)用Floyd算法，窮舉法，歐拉回路和運(yùn)籌學(xué)中的最優(yōu)化的相關(guān)知識(shí)建立數(shù)學(xué)模型，進(jìn)而求出公園內(nèi)道路總和與交叉點(diǎn)的函數(shù)關(guān)系，并充分的結(jié)合題目所給的條件，應(yīng)用MATLAB軟件，提高了計(jì)算效率和結(jié)果的科學(xué)性。模型建立時(shí)忽略了題目所未給出的人為因素和自然因素對(duì)公園內(nèi)道路總和的影響，在實(shí)際中時(shí)建議考慮人為因素和自然因素對(duì)所設(shè)計(jì)的道路結(jié)果的影響。7.2 模型的推廣本題所建立的數(shù)學(xué)模型雖然解決的是某大學(xué)校園公園內(nèi)道路總和設(shè)計(jì)的問(wèn)題，但可以推廣到各種城市規(guī)劃和園林建設(shè)等實(shí)際問(wèn)題，這些問(wèn)題都可以用該模型來(lái)解決。解決該問(wèn)題時(shí)，我們查閱

27、了有關(guān)數(shù)學(xué)建模和運(yùn)籌學(xué)最優(yōu)化的相關(guān)書(shū)籍，該模型中所提到的Floyd算法，歐拉回路和動(dòng)態(tài)規(guī)劃的相關(guān)方法均可以直接使用，利用這些方法可以快速方便地解決諸如求最短路徑等一些城市規(guī)劃與園林建設(shè)中的實(shí)際問(wèn)題。解決該問(wèn)題時(shí)所用到的數(shù)學(xué)思想和數(shù)學(xué)方法，對(duì)于解決實(shí)際的社會(huì)問(wèn)題也同樣具有廣泛的教育意義和社會(huì)效益。八 參考文獻(xiàn)【1】MATLAB程序設(shè)計(jì)及應(yīng)用許麗佳 穆炯 清華大學(xué)出版社2011【2】最優(yōu)化理論與方法傅英定 成孝予 唐應(yīng)輝 國(guó)防工業(yè)出版社2005【3】?jī)?yōu)化技術(shù)與MATLAB工具箱趙繼俊 機(jī)械工業(yè)出版社 2011【4】最優(yōu)化方法MATLAB應(yīng)用黃雍檢 陶冶 錢(qián)祖平 人民郵電出版社 2010【5】運(yùn)籌學(xué)

28、（數(shù)學(xué)規(guī)劃篇）呂蓬 潘志 清華大學(xué)出版社北京交通大學(xué)出版社 附錄/*/* Dijkstra.java */* Copyright (C) 1997, 1998, 2000 K. Ikeda */*/import java.applet.*;import java.awt.*;import java.awt.event.*;import java.util.*;import java.io.*;import .URL;class Node intx;inty;intdelta_plus;/* edge starts from this node */intdelta_minus;/* edge

29、terminates at this node */intdist;/* distance from the start node */intprev;/* previous node of the shortest path */intsucc,pred;/* node in Sbar with finite dist. */intw;inth;intpw;intdx;intdy;Stringname;class Edge intrndd_plus;/* initial vertex of this edge */intrndd_minus;/* terminal vertex of thi

30、s edge */intdelta_plus;/* edge starts from rndd_plus */intdelta_minus;/* edge terminates at rndd_minus */intlen;/* length */Stringname;public class Dijkstra extends Applet implements MouseListener intn,m;intu,snode;/* start node */intpre_s_first, pre_s_last;booleanisdigraph;intiteration, step;Nodev

31、= new Node100;Edgee = new Edge200;int findNode(String name) for (int i=0; in; i+)if (.equals(name)return i;return -1;void input_graph(InputStream is) throws IOException int x,y,l;Strings;Reader r = new BufferedReader(new InputStreamReader(is);StreamTokenizer st = new StreamTokenizer(r);mentCh

32、ar(#);st.nextToken();n = (int)st.nval;st.nextToken();m = (int)st.nval;st.nextToken();s = st.sval;isdigraph = digraph.equals(s);for (int i = 0; in; i+) Node node = new Node();st.nextToken(); = st.sval;st.nextToken();node.x = (int)st.nval;st.nextToken();node.y = (int)st.nval;vi = node;switch

33、(st.nextToken() case StreamTokenizer.TT_NUMBER:edge.rndd_minus = (int)st.nval;break;case StreamTokenizer.TT_WORD:edge.rndd_minus = findNode(st.sval);break;default:break;st.nextToken();edge.len = (int)st.nval;ei = edge;for (int i=0; i= 0)k = ek.delta_minus;ek.delta_minus = i; void append_pre_s(int i)

34、 vi.succ = vi.pred = -1;if (pre_s_first=0) i = ej.rndd_minus;if (vi.succ=-2)&(vi.distvu.dist+ej.len) if (vi.dist=0) i = ej.rndd_plus;if (vi.succ=-2)&(vi.distvu.dist+ej.len) if (vi.dist=0; i = vi.succ) if (rho vi.dist) rho = vi.dist;u = i;remove_pre_s(u);vu.succ = -3;void step4() vu.succ = -4;double

35、weight(Node n, double x, double y) doublew,z,xx,yy;w = 0;for (int j = n.delta_plus; j=0; j=ej.delta_plus) xx = (double)(vej.rndd_minus.x - n.x);yy = (double)(vej.rndd_minus.y - n.y);z = (x*xx+y*yy)/Math.sqrt(x*x+y*y)*(xx*xx+yy*yy)+1.0;w += z*z*z*z;for (int j = n.delta_minus; j=0; j=ej.delta_minus) x

36、x = (double)(vej.rndd_plus.x - n.x);yy = (double)(vej.rndd_plus.y - n.y);z = (x*xx+y*yy)/Math.sqrt(x*x+y*y)*(xx*xx+yy*yy)+1.0;w += z*z*z*z;return w;void init_sub() int x = 1, 0, -1, 1, 0, -1;int y = 1, 1, 1, -1, -1, -1;int i,j,k;doublew,z;for (i=0; in; i+) k=0;w=weight(vi,(double)x0,(double)y0);for

37、(j=1; j6; j+) z=weight(vi,(double)xj,(double)yj);if (zw) w = z;k = j;vi.dx = xk;vi.dy = yk;public void init() String mdname = getParameter(inputfile);try InputStream is;is = new URL(getDocumentBase(),mdname).openStream();input_graph(is);try if (is != null)is.close(); catch(Exception e) catch (FileNo

38、tFoundException e) System.err.println(File not found.); catch (IOException e) System.err.println(Cannot access file.);String s = getParameter(start);if (s != null)snode = Integer.parseInt(s);elsesnode = 0;setBackground(Color.white);rdb();init_sub();addMouseListener(this);public void paintNode(Graphi

39、cs g, Node n, FontMetrics fm) String s;int x = n.x;int y = n.y;int w = fm.stringWidth() + 10;int h = fm.getHeight() + 4;n.w = w;n.h = h;if (n.succ-2)g.setColor(Color.yellow);elseg.setColor(getBackground();g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);g.setColor(Color.black);g.drawString(,x-(w-10)/

40、2,(y-(h-4)/2)+fm.getAscent();if (n.dist0)s = ;elses = +n.dist;w = fm.stringWidth(s) + 10;x += (h+1)*n.dx; y += (h+1)*n.dy;g.setColor(getBackground();g.fillRect(x-n.pw/2,y-h/2,n.pw,h);n.pw = w;if (n.succ=Math.abs(h*a) x0 = (b=0)?1:-1)*a*h/b/2;x1 = (b=0)?1:-1)*h/2; else x0 = (a=0)?1:-1)*w/2;x1 = (a=0)?1:-1)*b*w/a/2;return x;void drawArrow(Graphics g,int x1,int y1,int x2,int y2) inta = x1-x2;intb = y1-y2;if (isdigraph) doubleaa = Math.sqrt(a*a+b*b)/16.0;doublebb = b/aa;aa = a/aa;g.