公園內(nèi)道路最優(yōu)化設(shè)計(jì)的討論

1、公園內(nèi)道路最優(yōu)化設(shè)計(jì)的討論摘要1本題要解決的是公園內(nèi)道路設(shè)計(jì)的最優(yōu)化問題，就是需要建立一個(gè)模型去設(shè)計(jì)公園內(nèi)部的道路，要求在滿足約束條件的前提下找出總路程長(zhǎng)度和最短的最優(yōu)解，并給出相應(yīng)的道路設(shè)計(jì)圖。針對(duì)問題一，首先不考慮abcd四個(gè)點(diǎn)，假設(shè)僅利用公園四周的道路，利用matlab通過floyd算法解出p1,p2,p3p8任兩點(diǎn)間的最短路程s，再利用matlab算出p1,p2,p3p8任兩點(diǎn)之間的最短距離l，通過比較s與1.4*l，選出不符合題目要求的幾組：(p1,p5),(p1,p6),(p1,p8),(p2,p5),(p2,p6),(p2,p7),(p3,p4),(p3,p5),(p3,p6),

2、(p3,p7)。結(jié)合圖容易看出：(p1,p8)和(p3,p4)可以確定必須要相連，則p8與p4都已經(jīng)符合要求，只需再考慮其它幾個(gè)點(diǎn)p1，p2，p3，p5，p6，p7，a，b，c，d，利用kruskal算法求最小生成樹，在此基礎(chǔ)上進(jìn)行局部調(diào)整優(yōu)化選擇最優(yōu)解。根據(jù)以上算法得到的最優(yōu)解為394.5米，示意圖請(qǐng)參見正文。針對(duì)問題二，由于沒有限定道路結(jié)點(diǎn)，所以根據(jù)1.4倍的約束條件聯(lián)想到利用橢圓的性質(zhì)（邊界上點(diǎn)到兩焦點(diǎn)的距離和為定值）來進(jìn)一步縮小取點(diǎn)范圍，這樣的簡(jiǎn)化過程使解決問題的效率大大加快。第一步是以任意兩點(diǎn)為焦點(diǎn)，以1.4倍的焦距為長(zhǎng)軸長(zhǎng)作橢圓，觀察橢圓的交集，得到覆蓋程度不同的區(qū)域；第二步將覆蓋

3、程度視為符合要求的中間交叉點(diǎn)的可能位置概率，計(jì)算出最大覆蓋程度區(qū)域的坐標(biāo)范圍；第三步在區(qū)域中分階段劃分精度并做出程序計(jì)算區(qū)域中點(diǎn)到入口點(diǎn)的最短距離，比較后得出最佳點(diǎn)。根據(jù)以上算法得到最優(yōu)解為375.2米，示意圖請(qǐng)參見正文。針對(duì)問題三，湖的存在即使在問題二上增加一塊不可利用的矩形區(qū)域，仍然可繼續(xù)借助問題二的模型，但要重新確定交叉點(diǎn)的范圍。此問題中，由于矩形湖在公園右邊，通過問題二的分析過程可知，該湖只影響右邊的交叉點(diǎn)。所以左邊的交叉點(diǎn)位置不必改變，只需確定右邊的交叉點(diǎn)即可。并在此基礎(chǔ)上利用問題二的模型繼續(xù)求解。由于時(shí)間關(guān)系與目前知識(shí)水平局限還未能完成問題三的最優(yōu)解。關(guān)鍵詞：floyd krusk

4、al 局部?jī)?yōu)化 matlab 動(dòng)態(tài)步長(zhǎng) 窮舉法一、 問題重述 某大學(xué)計(jì)劃建一個(gè)形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美化校園環(huán)境，也是想為其學(xué)生提供更的生活條件。公園計(jì)劃有若干個(gè)入口，現(xiàn)在你需要建立一個(gè)模型去設(shè)計(jì)道路讓任意兩個(gè)入口相連（可以利用公園四周的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)），使總的道路長(zhǎng)度和最小，前提要求是任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍。主要設(shè)計(jì)對(duì)象可假設(shè)為如圖所示的矩形公園，其相關(guān)數(shù)據(jù)為：長(zhǎng)200米，寬100米，1至8各入口的坐標(biāo)分別為：p1(20,0),p2(50,0),p3(160,0),p4(200,50),p5

5、(120,100),p6(35,100),p7(10,100),p8(0,25).示意圖見圖1，其中圖2即是一種滿足要求的設(shè)計(jì)，但不是最優(yōu)的。現(xiàn)完成以下問題：?jiǎn)栴}一：假定公園內(nèi)確定要使用4個(gè)道路交叉點(diǎn)為：a(50,75)，b(40,40)，c(120,40)，d(115,70）。問如何設(shè)計(jì)道路可使公園內(nèi)道路的總路程最短。建立模型并給出算法。畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。問題二：現(xiàn)在公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點(diǎn)的坐標(biāo)，畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。問題三：若公園內(nèi)有一條矩形的湖，新修的道路不能通過，但可以到達(dá)湖四周的邊，示意圖見

6、圖3。重復(fù)完成問題二 的任務(wù)。其中矩形的湖為r1(140,70),r2(140,45),r3=(165,45),r4=(165,70)。注：以上問題中都要求公園內(nèi)新修的道路與四周的連接只能與8個(gè)路口相通，而不能連到四周的其它點(diǎn)。圖 1 公園及入口示意圖圖 2 一種可能的道路設(shè)計(jì)圖圖3 有湖的示意圖二、 問題分析因?yàn)槟J(rèn)的矩形公園四周存在已經(jīng)建好的道路，且利用此道路長(zhǎng)度不計(jì)入設(shè)計(jì)道路總長(zhǎng)，可以以此為問題的突破口來簡(jiǎn)化原問題。先拋開條件中的內(nèi)部四個(gè)點(diǎn)，討論后找出僅利用公園四周道路時(shí)，不滿足題目條件的道路。然后以找出的不滿足條件的道路為主要研究對(duì)象，將原問題簡(jiǎn)化，再進(jìn)行下一步的討論求解。三

7、、 模型假設(shè)假設(shè)一：公園為矩形狀，且在同一個(gè)平面，不考慮臺(tái)階的影響假設(shè)二：假設(shè)距離與入口大小無關(guān)，將各入口可視為點(diǎn)，把路視為直線，每個(gè)入口與節(jié)點(diǎn)之間的路線均為直線路徑假設(shè)三:任意兩個(gè)入口相連，使總的道路長(zhǎng)度和最小，前提要求是任意兩個(gè)入口之間的最短路長(zhǎng)不大于兩點(diǎn)連線的1.4倍假設(shè)四: 公園內(nèi)新修的道路與四周的連接只能與8個(gè)路口相通，而不能連到四周的其它點(diǎn)假設(shè)五：用窮舉法在求解問題二時(shí)，用劃分的每個(gè)小區(qū)域的中心對(duì)稱點(diǎn)的坐標(biāo)來代表該區(qū)域的坐標(biāo)量，當(dāng)劃分的區(qū)域越來越小時(shí)，兩者就近似相等四、 符號(hào)系統(tǒng)p1,p2,p3p8任兩點(diǎn)間的最短路程矩陣sp1,p2,p3p8任兩點(diǎn)之間的最短距離矩陣l五、 模型建立

8、 問題一：初步簡(jiǎn)化問題：首先不考慮abcd四個(gè)點(diǎn)，假設(shè)僅利用公園四周的道路，利用matlab通過floyd算法解出p1,p2,p3p8任兩點(diǎn)間的最短路程s：s= 0 30 140 230 240 155 130 45 30 0 110 200 270 185 160 75 140 110 0 90 220 295 270 185 230 200 90 0 130 215 240 275 240 270 220 130 0 85 110 195 155 185 295 215 85 0 25 110 130 160 270 240 110 25 0 8545 75 185 275 195 110

9、 85 0再利用matlab編程技算出p1,p2,p3p8任兩點(diǎn)之間的最短距離l：l= 0 30.0000 140.0000 186.8154 141.4214 101.1187 100.4988 32.0156 30.0000 0 110.0000 158.1139 122.0656 101.1187 107.7033 55.9017 140.0000 110.0000 0 64.0312 107.7033 160.0781 180.2776 161.9413 186.8154 158.1139 64.0312 0 94.3398 172.4094 196.4688 201.5564 141

10、.4214 122.0656 107.7033 94.3398 0 85.0000 110.0000 141.5097 101.1187 101.1187 160.0781 172.4094 85.0000 0 25.0000 82.7647 100.4988 107.7033 180.2776 196.4688 110.0000 25.0000 0 75.6637 32.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0s-1.4*l= 0 -12.0000 -56.0000 -31.5416 42.0101 13.4338 -

11、10.6983 0.1781 -12.0000 0 -44.0000 -21.3594 99.1082 43.4338 9.2154 -3.2624 -56.0000 -44.0000 0 0.3563 69.2154 70.8907 17.6114 -41.7179 -31.5416 -21.3594 0.3563 0 -2.0757 -26.3732 -35.0564 -7.1790 42.0101 99.1082 69.2154 -2.0757 0 -34.0000 -44.0000 -3.1136 13.4338 43.4338 70.8907 -26.3732 -34.0000 0

12、-10.0000 -5.8706 -10.6983 9.2154 17.6114 -35.0564 -44.0000 -10.0000 0 -20.9292 0.1781 -3.2624 -41.7179 -7.1790 -3.1136 -5.8706 -20.9292 0通過比較s與1.4*l，也就是計(jì)算s-1.4*l的值：選出不符合題目要求的幾組(圖中已標(biāo)記)：(p1,p5),(p1,p6),(p1,p8),(p2,p5),(p2,p6),(p2,p7),(p3,p4),(p3,p5),(p3,p6),(p3,p7)。進(jìn)一步簡(jiǎn)化問題：結(jié)合圖容易看出：(p1,p8)和(p3,p4)可以確定必

13、須要相連，則p8與p4都已經(jīng)符合要求，只需再考慮其它幾個(gè)點(diǎn)p1，p2，p3，p5，p6，p7，a，b，c，d即可，如圖利用kruskal算法求p1、p2、p3、p5、p6、p7、a、b、c、d總共十個(gè)點(diǎn)的最小生成樹在此基礎(chǔ)上，由于（p1,p5）不滿足題目條件，所以進(jìn)行局部調(diào)整優(yōu)化選擇最優(yōu)解。此時(shí)得到問題一的最優(yōu)解為：l(p1,p8)+l(p2,b)+l(a,b)+l(a,6)+l(a,5)+l(5,d)+l(c,d)+l(c,3)+l(3,4)=394.5米問題二：為簡(jiǎn)化問題，仍使用問題一中的初始模型，即（p1,p8）（p3,p4）默認(rèn)相連。由于沒有限定道路結(jié)點(diǎn)，所以根據(jù)1.4倍的約束條件聯(lián)想

14、到利用橢圓的性質(zhì)（邊界上點(diǎn)到兩焦點(diǎn)的距離和為定值）來進(jìn)一步縮小取點(diǎn)范圍，這樣的簡(jiǎn)化過程使解決問題的效率大大加快。第一步是以任意兩點(diǎn)為焦點(diǎn)，以1.4倍的焦距為長(zhǎng)軸長(zhǎng)作橢圓，觀察橢圓的交集，得到覆蓋程度不同的區(qū)域；經(jīng)過討論可知：最少需要兩個(gè)交叉點(diǎn)，可使修建的道路滿足題目要求，為簡(jiǎn)化題目，我們這里只討論公園內(nèi)有且只有兩個(gè)道路交叉點(diǎn)的情況。第二步將覆蓋程度視為符合要求的中間交叉點(diǎn)的可能位置概率，計(jì)算出最大覆蓋程度區(qū)域的坐標(biāo)范圍；由幾個(gè)點(diǎn)的空間分布易知，兩個(gè)交叉點(diǎn)分別在矩形的左右兩側(cè)，且各自作用在各自的區(qū)域，不會(huì)產(chǎn)生相互影響。第三步在區(qū)域中分階段劃分精度并做出程序計(jì)算區(qū)域中點(diǎn)到入口點(diǎn)的最短距離，比較后得

15、出最佳點(diǎn)。利用c程序分別取不同步長(zhǎng)來試探最優(yōu)解的位置，先用大步長(zhǎng)的方法找到最優(yōu)解的大致位置，再將此位置細(xì)分后去較小步長(zhǎng)比較最優(yōu)解，如此循環(huán)最終得到一個(gè)通過局部?jī)?yōu)化的近似最優(yōu)解，如下圖：兩個(gè)交叉點(diǎn)坐標(biāo)為：e（91,58.554）和f（161,39.4）此時(shí)得到問題二的最優(yōu)解為：l(p1,p8)+l(p2,e)+l(p5,e)+l(p6,e)+l(e,f)+l(f,4)+l(f,3)=375.2米問題三：湖的存在即使在問題二上增加一塊不可利用的矩形區(qū)域，仍然可繼續(xù)借助問題二的模型，但要重新確定交叉點(diǎn)的范圍。此問題中，由于矩形湖在公園右邊，通過問題二的分析過程可知，該湖只影響右邊的交叉點(diǎn)。所以左邊的

16、交叉點(diǎn)位置不必改變，只需確定右邊的交叉點(diǎn)即可。并在此基礎(chǔ)上利用問題二的模型繼續(xù)求解。時(shí)間問題就不再展開。六、 模型分析 在問題2的求解過程中，由于時(shí)間所限，我們只討論了包含兩個(gè)交叉點(diǎn)的最有線路選取和交叉點(diǎn)優(yōu)化問題，如果添加更多的交叉點(diǎn)，優(yōu)化目標(biāo)會(huì)得到進(jìn)一步提高。七、 模型推廣我們?cè)诒疚慕鉀Q了一個(gè)在任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍的前提下，考慮總的道路長(zhǎng)度和最小的最優(yōu)化問題。是建立了一個(gè)逐步逼近最優(yōu)解的模型，通過計(jì)算機(jī)編程窮舉其簡(jiǎn)化后的所有可能的值來實(shí)現(xiàn)的。模型優(yōu)點(diǎn)1. 相對(duì)于整體考慮問題所帶來的難度來說，進(jìn)行局部之間的交替優(yōu)化可簡(jiǎn)化問題。2. 充分利用了公園四周的邊，使得

17、總的道路長(zhǎng)度最小。3. 對(duì)于第一題，我們?cè)谝呀?jīng)得到結(jié)果的基礎(chǔ)上，進(jìn)一步通過對(duì)局部的計(jì)算，得到更優(yōu)解。模型不足1. 在研究問題二時(shí)，最好再討論一下交叉點(diǎn)數(shù)為3、4、5或者更多時(shí)的情況，從而得出最優(yōu)解2. 問題三的湖邊道路的假設(shè)與運(yùn)用可以更加靈活。八、 結(jié)論對(duì)于問題一,我們得出的最優(yōu)解為394.5米對(duì)于問題二,我們得出的最優(yōu)解為375.2米九、 參考文獻(xiàn)1 趙靜 但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（第3版），北京：高等教育出版社，2008.2 張志涌 楊祖櫻，matlab教程r2011a，北京：北京航空航天大學(xué)出版社，2011.3 艾冬梅等，matlab與數(shù)學(xué)實(shí)驗(yàn)，北京：機(jī)械工程出版社，2011.附錄1、p

18、1p8各點(diǎn)之間最短距離矩陣l的matlab程序x=20 50 160 200 120 35 10 0;y=0 0 0 50 100 100 100 25;i=1;j=i:8l1=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=2l2=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=3l3=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=4l4=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=5l5=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=6l6=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i

19、=7l7=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=8l8=sqrt(x(i)-x(j).2+(y(i)-y(j).2)l=l;l2;l3;l4;l5;l6;l7;l82、求任意兩點(diǎn)間最短路徑的floyd算法的matlab程序function d=floyd(do)n,n-size(do);d=zeros(n);max1=floor(log(2*n-3)/log(2)for k=1:max1 for r=1:n;d1=do(r,:);d(r,:)=min(repmat(d1'',1,n)+do);endendfor k=1:max1 dt=d;dt(fin

20、d(dt=inf)=1;do(find(do=inf)=1;do=do-dt;if sum(do(:)=0 return;endfor r=1:n;d1=do(r,:);d(r,:)=min(repmat(d1'',1,n)+do);enddo=d;end3、已知十個(gè)點(diǎn)坐標(biāo)求其賦權(quán)鄰接矩陣的matlab程序x=20 50 160 120 35 10 50 40 129 115y=0 0 0 100 100 100 75 40 40 70i=1,j=1:10l1=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=2,j=1:10l2=sqrt(x(i)-x(j).2

21、+(y(i)-y(j).2)i=3,j=1:10l3=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=4,j=1:10l4=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=5,j=1:10l5=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=6,j=1:10l6=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=7,j=1:10l7=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=8,j=1:10l8=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=9,j=1:10l9=sqrt(x(i)-x(j).

22、2+(y(i)-y(j).2)i=10,j=1:10l10=sqrt(x(i)-x(j).2+(y(i)-y(j).2)l=l1;l2;l3;l4;l5;l6;l7;l8;l9;l104、計(jì)算最小生成數(shù)的kruskal算法實(shí)現(xiàn)程序function kruskal(w,max)%此程序?yàn)樽钚∩蓸涞膋ruskal算法實(shí)現(xiàn)%w為無向圖的距離矩陣%max為距離矩陣中無窮大的實(shí)際輸入值len=length(w); edge=zeros(len*(len-1),3);¡count=1; for i=1:len-1 for j=i+1:len if w(i,j)=max edge(count,1

23、)=w(i,j); edge(count,2)=i; edge(count,3)=j; count=count+1; end endendedge=edge(1:count-1,:); tmp,index=sort(edge(:,1); i=3; while 1 x=findcycle(edge(index(1:i),:),len); if x index(i)=0; else i=i+1; end index=index(index>0); if i=len break; endendindex=index(1:len-1); s=sprintf('nt%st%st %st&#

24、39;,'邊端點(diǎn)','距離','是否在最小生成樹'); for i=1:count-1 edge_tmp=edge(i,:); if isempty(find(index=i,1) s_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp(2),edge_tmp(3),edge_tmp(1),'¡Ì'); else s_tmp=sprintf('n t (%d,%d)t %dt %st',edge_tmp(2),edge_tmp(3),edge_

25、tmp(1),'¡Á'); end s=strcat(s,s_tmp); enddisp(s);endfunction isfind=findcycle(w,n) %此程序用于判斷所給的邊能否構(gòu)成圈：有圈，返回1；否則返回0%w：輸入的邊距陣%n：原圖的點(diǎn)數(shù)%原理：不斷除去出現(xiàn)次數(shù)小于2的端點(diǎn)所在的邊，最后觀察是否有邊留下len=length(w(:,1); index=1:len; while 1 num=length(index); p=zeros(1,n); for i=1:num p(w(index(i),2)=p(w(index(i),2)+1;

26、p(w(index(i),3)=p(w(index(i),3)+1; end index_tmp=zeros(1,num); discard=find(p<2); count=0; for i=1:num if (isempty(find(discard=w(index(i),2),1) | isempty(find(discard=w(index(i),3),1) count=count+1; index_tmp(count)=index(i); end end if num=count index=index_tmp(1:count); break; else index=index

27、_tmp(1:count); endend if isempty(index) isfind=0; else isfind=1; endend5、求解問題二中兩個(gè)交叉點(diǎn)最優(yōu)位置的c語言源程序：#include<stdio.h>#include<math.h>int main()double a,d;a=20,0;50,0;160,0;120,100;35,100;10,100;double b,b022;double d15,d015,d16,d016,d25,d025,d26,d026,d27,d027,d35,d035,d36,d036,d37,d037;d015=

28、141.421;d016=101.119;d025=122.066;d026=101.119;d027=107.703;d035=107.703;d036=160.078;d037=180.278;b22=65,55;105,60double k1,k2,k3,k4;double s0=500,s=0;double m; for(k1=-10;k1<=10;k1=k1+1)for(k2=-10;k2<=10;k2=k2+1)for(k3=-10;k3<=10;k3=k3+1)for(k4=-10;k4<=10;k4=k4+1) d01=sqrt(b00+k1-a10)*(b00+k1-a10)+(b01+k2-a11)*(b01+k2-a11); d00=d01+30; d02=sqrt(b00+k1-a20)*(b00+k1-a2