公園內(nèi)道路設(shè)計問題

1、目錄 TOC o 1-5 h z HYPERLINK l bookmark17 o Current Document 問題提出1 HYPERLINK l bookmark33 o Current Document 模型假設(shè)2 HYPERLINK l bookmark39 o Current Document 符號說明2 HYPERLINK l bookmark58 o Current Document 模型建立與求解34.1基于Prim算法和 Dijkstra 算法的模型34.1.1模型建立34.1.2模型的求解與優(yōu)化44.2基于改進K means 聚類算法的模型74.2.1模型建立74.2.

2、2模型求解94.3回歸優(yōu)化模型104.3.1模型建立104.3.2回歸模型的求解與檢驗11 HYPERLINK l bookmark150 o Current Document 模型優(yōu)化125.1距離代價函數(shù)和距離代價最小準(zhǔn)則125.2基于距離代價函數(shù)的空間聚類k值優(yōu)化算法135.3用K - means算法求解聚類中心135.4模型優(yōu)化處理13 HYPERLINK l bookmark181 o Current Document 模型分析與評價14 HYPERLINK l bookmark185 o Current Document 參考文獻14附錄1 15附錄2 16附錄3 18問題提出西安

3、某大學(xué)計劃建一個形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美 化校園環(huán)境，也是想為其學(xué)生提供更好的生活和學(xué)習(xí)條件。在綜合考慮了校園 各地方平均人流量后，公園計劃有若十個入口，為了保證公園里人員不過于擁 擠和出入快捷方便，現(xiàn)在需建立一個模型去設(shè)計園內(nèi)道路(可以利用公園四周 的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計入道路總長)， 使任意兩個入口相連，且總的道路長度和(這一總長度可能與成本成正比)最 小，同時還要滿足任意的兩個入口間的最短道路長不大于兩點連線的1.4倍?？紤]到不規(guī)則圖形的復(fù)雜性、矩形的特殊性和普適性以及實際中的公園面 積一般不會太小等因素，本題主要設(shè)計對象可假設(shè)為如圖

4、一所示的矩形公園， 其相關(guān)數(shù)據(jù)為：長200米，寬100米，1至8號各入口的坐標(biāo)分別為P1(20,0), P2(50,0), P3(160,0), P4(200,50), P5(120,100),P6(35,100),P7(10,100), P8(0,25)現(xiàn)完成以下問題：假定公園內(nèi)確定要使用的4個道路交叉點為4(50,75), B(40,40), C(120,40), D(115,70).圖二所示即是一種滿足要求的設(shè)計，但并不是最優(yōu)的，問如何設(shè)計道路可使公園內(nèi)道路的總路程最短。建立數(shù)學(xué)模 型并給出算法。畫出道路設(shè)計，計算新修路的總路程?，F(xiàn)在公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最短？

5、建 立模型并給出算法。給出道路交叉點的坐標(biāo)，畫出道路設(shè)計，計算新修路的總 路程。若公園內(nèi)有一條矩形的湖，如圖三所示，新修的道路不能通過，但可 以到達湖四周的邊，重復(fù)完成問題二的任務(wù)。其中矩形湖位置坐標(biāo)為夫1(140,70), R2(140,45), R3(165,45), R4(165,70).注：以上問題中都要求公園內(nèi)新修的道路與四周的連接只能與8個路口相 通，而不能連到四周的其他點。圖二一種可能的道路設(shè)計圖圖一公園及入口示意圖圖三有湖的示意圖模型假設(shè)設(shè)計道路只考慮路徑長短，道路寬度處處相同且不考慮美觀效果。經(jīng)驗值具有一定的科學(xué)規(guī)律，可實施。符號說明C1:記矩形邊框網(wǎng)格線最小距離不大于連線距

6、離1.4倍的無序點對為C1類無 序點對C2 : P,P,.,P構(gòu)成的所有無序點對中除C1類之外的無序點對記為C2類無 128序點對C :以公園8個入口 P,P,.,P為頂點的連通圖的鄰接矩陣 128B : P，P,.,4 8個點中任意兩點沿矩形邊框的最短距離構(gòu)成的矩陣G :有n個頂點的連通圖T :連通圖的最小生成樹l(i, j):在確定路徑中P,P (i, j = 1,2, .,8)兩點間的道路長d(i, j):用Dijkstra算法求得的P,P (i, j = 1,2, .,8)兩點最短路徑的道路長 i jw(i, j): P,P (i, j = 1,2,.,8)兩點間的直線距離x :將8個

7、入口點兩兩相連得到的交點(端點不算)記作X = x , X., x k :將X = %,X2 .,x 中的n個空間對象聚類為k類(簇)Q : X = x1, %., xn 的所有聚類結(jié)果構(gòu)成的集合p :空間中的任意一點，即X = x1, %., xn 中的樣本點Ct : K-means算法求得的聚類數(shù)k下的類(簇)m :簇Ct,所含樣本的均值 m :全部樣本的均值模型建立與求解4. 1基于Pr im算法和 Dijkstra 算法的模型4. 1.1模型建立因為公園四周邊上已經(jīng)建好的道路不計入道路總長，要想園內(nèi)道路總路程 最短，應(yīng)盡可能利用矩形邊框道路。由于C1類無序點對滿足邊框最短距離不大 于1

8、.4倍連線距離，所以C1無序點對對應(yīng)的入口可以通過公園邊上道路連通， 在進行道路設(shè)計時不予考慮；對C 2類無序點對，可以將相關(guān)點連成連通圖，通 過Prim算法得出相應(yīng)的最小生成樹，再通過Dijkstra算法得到這些無序點對的 最短路徑，最后檢驗驗證方案設(shè)計是否符合要求，若方案不合理，則需修改優(yōu) 化模型，直到得到符合條件的最佳道路設(shè)計方案為止。（I）確定C1,C2類無序點對根據(jù)圖一坐標(biāo)得到以公園8個入口 P,P, ,P為頂點的連通圖的鄰接矩陣 TOC o 1-5 h z 128C以及這8個點中任意兩點沿矩形邊框的最短距離構(gòu)成的矩陣B。進行矩陣運M = 1.4C - B對矩陣元素進行分析，當(dāng)m 0

9、時，1.4c b，即P,P兩點的矩形邊框距 、 .j 一 j i j .離不大于兩點連線的距離的1.4倍，P,P構(gòu)成的無序點對屬于C1類無序點對， 在設(shè)計道路時，不需考慮這兩點對應(yīng)入口的道路連接問題；當(dāng)m 1.4b礦 i, j = 1,2,3,5,6,7成立，說明圖四中相應(yīng)的連線不符合要求，需要將結(jié)果進行修改優(yōu)化。綜合考 慮所有無序點對間的最短道路長和最短道路總長，在已經(jīng)連接好的路線不做太 大改變的前提下，將不合理的路線進行適當(dāng)?shù)男薷膬?yōu)化，直到所有路線都滿足 要求且道路總長最小為止。4.1.2模型的求解與優(yōu)化（I）根據(jù)圖一坐標(biāo)得到以公園8個入口 P,P,.,P為頂點的連通圖的鄰接 128矩陣-

10、042.0000 196.0000 261.5416 197.9899 141.5662 140.6983 44.8219142.00000154.0000 221.3594 170.8918 141.5662 150.7846 78.2624196.0000 154.0000089.6437 150.7846 224.1093 252.3886 226.7179261.5416 221.3594 89.64370132.0757 241.3732 275.0564 282.179（C=197.9899 170.8918 150.7846 132.07570119.0000 154.0000

11、198.1136141.5662 141.5662 224.1093241.3732119.0000035.0000115.8706140.6983 150.7846 252.3886275.0564154.000035.00000105.929244.8219 78.2624 226.7179282.1790198.1136115.8706105.92920 p, P,., P8這8個點中任意兩點沿矩形邊框的最短距離構(gòu)成的矩陣一 03014023024015513045 一30011020027018516075140110090220295270185B =2302009001302152

12、402752402702201300851101951551852952158502511013016027024011025085_ 4575185275195110850 _進行矩陣運算M =1.4C -B后,得到的矩陣一 012.000056.000031.5416 -42.0101 -13.433810.6983-0.178112.0000044.000021.3594 -99.1082 -43.4338-9.21543.262456.000044.00000-0.3563-69.2154 -70.8907 -17.6114 41.717931.541621.3594-0.356302

13、.075726.373235.05647.1790M =-42.0101 -99.1082 -69.21542.0757034.000044.00005.8706-13.4338 -43.4338 -70.8907 26.373234.0000010.00005.870610.6983-9.2154-17.6114 35.056444.000010.0000020.9292-0.17813.262441.71797.17903.11365.870620.92920 _當(dāng)m 0時，點(i, j)屬于C1類無序點對；當(dāng)m 0時，點(i, j)屬于C2類無序 點對。由矩陣M的輸出結(jié)果知，C2類無序點

14、對有(1,5),(1,6),(1,8),(2,5),(2,6),(2,7),(3,4),(3,5),(3,6),(3,7)，其他無序點對均為 C1 類無序點對。用Prim算法和Dijkstra算法對C2類無序點對進行處理 TOC o 1-5 h z 經(jīng)觀察分析，在所有C2類無序點對中，p,P均只在一對無序點對中出現(xiàn)， 所以優(yōu)先單獨分析(1，8)和(3, 4)。4 8在圖二所示的道路設(shè)計坐標(biāo)圖中可以看出，P, P經(jīng)過其他任意點間接連接起來的路程l (1,8)滿足不等關(guān)系1 8l(1,8) 、 1.4%同理有，l(3,4) 、 1.4c34所以，P,P和P,P對應(yīng)的兩對入口必須分別直接連通。 18

15、34余下未處理的 C2 類無序點對有(1,5), (1,6), (2, 5), (2, 6), (2, 7), (3, 5),印6 7)，將與上述無序點對的連接有關(guān)的點(P,P,P,P,P,P,P,&B,C,D)兩兩連接，1235678對得到的連通圖G用Prim算法得到相應(yīng)的最小生成樹T。算法運行后輸出的最小生成樹T如下圖四所示：圖四最小生成樹由于最小生成樹只保證了 C2類無序點對連接總路程最短，并不一定滿足無 序點對對應(yīng)的入口之間的道路長不大于兩點連線距離的1.4倍，所以需要檢驗。用Dijkstra算法對模型進行修改優(yōu)化并檢驗?zāi)Ｐ偷目尚行詢?yōu)化一：經(jīng)Dijkstra算法計算得到，p,P5兩點間

16、的最短路徑為P IP IBIAIDIP，但最短道路長d(1,5)1.4。，所以該路徑不可取。 TOC o 1-5 h z 18515在道路總長最小的前提下，為減少入口2和入口5間的道路長，可以將上述路徑優(yōu)化為P IP IBIAIP。125優(yōu)化二：通過觀察，在連通入口 7的道路中，AIP段可以優(yōu)化，可以先7假設(shè)優(yōu)化模型再驗證檢驗假設(shè)的合理性。假設(shè)該段道路可以用AIP IP優(yōu) 化代替，即在優(yōu)化模型中去掉A I P段，用Dijkstra算法可以求出：點到其他 各點的最短路徑和最短距離，計算結(jié)7果均滿足不等關(guān)系7d (7, j) 8 d ,（8go.5,1），則x.（i = s或t）為第三個聚類中心，

17、類別數(shù)K = K +1 ;否則算法結(jié)束（6）重復(fù)（3）（5）根據(jù)已經(jīng)設(shè)定的聚類數(shù)k = 2，運用K - means算法求出聚類數(shù)2下的聚類 中心。（III）以聚類中心為道路交叉點設(shè)計最佳道路空間聚類一般使用距離作為劃分準(zhǔn)則，即任一空間對象與該對象所屬簇的 幾何中心之間的距離比該對象到任何其他簇的幾何中心的距離都小，所以，上步中得到的聚類中心可以作為公園道路規(guī)劃時園內(nèi)交叉路口。在確定了道路交 叉點的個數(shù)和位置后，我們可以套用問題一的模型來設(shè)計最優(yōu)道路方案。4.2.2模型求解輸入P,P,.,P各點的坐標(biāo)，運用算法1得到兩兩連線交點，輸出結(jié)果128如下圖六所示：10090807060 50 40 3

18、0 20 10020406080100120140160180200圖六入口兩兩連線示意圖重合的交點不計算在內(nèi)，一共得到68個交點，用x (i = 1,2, .,68)表示各交 點，交點坐標(biāo)的輸出結(jié)果見附錄2ik -means算法求解聚類中心記A = x ,x，,x,.,x (i = 1,2,.,68)為樣本空間，由經(jīng)驗準(zhǔn)則給定聚類12 i 68數(shù)k = 2,用K -means算法求出聚類數(shù)k = 2下的聚類空間。運行結(jié)束時輸出k = 2時的聚類空間，將求得的兩個中心分別記為S，計算結(jié)果為S1 = (172,42), S2 = (60,77)以聚類中心為道路交叉點設(shè)計最佳道路以S = (172

19、,42),S = (60,77)為道路交叉點設(shè)計道路使道路總長最短，可以 套用問題一中的模型，2最后輸出結(jié)果如下圖六所示：圖六以聚類中心為交叉點的道路設(shè)計經(jīng)計算，新修道路總長為358.6米。4.3回歸優(yōu)化模型4.3.1模型建立問題三相對于問題二只是多了矩形湖的限制，可以在做盡量少的改變的前 提下優(yōu)先優(yōu)化經(jīng)過湖面區(qū)域的路徑，再對優(yōu)化后的模型進行檢驗驗證。(I)回歸模型建立由問題二的設(shè)計方案知，只有路徑S1P5經(jīng)過了湖面區(qū)域，所以首先對 該路徑進行優(yōu)化，另外找一合適的點 ,使得路徑S 一P不經(jīng)過湖面區(qū)域且改 變的路徑P 一 S 一P最短，為尋找這一S點建立如下回歸模型：3353設(shè)S;= (a,b)

20、， S1= (S3 ,S3 ) = (172,42),目標(biāo)函數(shù)為y =、；(a -120)2 + (b -100)2 ;(a - S3)2 + (b - S3)2代入數(shù)據(jù)，于是，目標(biāo)函數(shù)可簡化為y =、J(a -120)2 + (b -100)2 + (a -172)2 + (b - 42)2 其中a,b滿足以下約束條件：kS3 R3 -七 R kS3 S1S3 S1a 200, b 4a 200, b 100于是，求解路徑P3s S3 -弓的最短路徑問題轉(zhuǎn)化為求目標(biāo)函數(shù) y =、：(a 120)2 +(b 100)2 +、a -172)2 +(b - 42)2在上述約束條件確定的可行域里何處

21、取最小值的問題，該回歸模型通過Lingo 求解，結(jié)果輸出就是我們要找的點S3。(II)模型檢驗在確定S3點后，我們還需要進行檢驗，驗證優(yōu)化模型中任意兩點間的最短 道路距離是否都不大于兩點連線距離的1.4倍，用Dijkstra算法(算法說明問題 一中已經(jīng)給出)可完成檢驗過程。若經(jīng)驗證模型符合1.4倍的要求，則模型可取; 若經(jīng)驗證模型不符合1.4倍的要求，則需進一步優(yōu)化，此時，需綜合考慮路徑最 短距離和道路總路程最短，在盡量少地改動符合條件的路線的前提下，將不符 合條件的路線修改優(yōu)化，直到模型檢驗結(jié)果符合要求為止。4.3.2回歸模型求解與檢驗將上述建立的回歸模型在Lingo中運行，運行結(jié)果為a =

22、 165,b = 70，即R4 點，此時道路設(shè)計如下圖七所示：對圖七所示連通圖用Dijkstra算法求得任意兩點間的最短路徑和最短距離， 經(jīng)計算，任意兩點間的最短路徑距離均不大于連線距離的L4倍，這說明該設(shè)計 方案是合理的。又由于在回歸模型中，求解的是最小值且其他路線的連接情況 并未改變，所以該設(shè)計方案也是最佳的。經(jīng)計算，新修道路總長為361.7米。模型優(yōu)化由于典型的K - means算法是在k準(zhǔn)確給定的條件下實現(xiàn)的，所以要先算出 最優(yōu)的聚類k值，本題借用距離代價函數(shù)和距離代價最小準(zhǔn)則求解最佳聚類數(shù)k， 該方法對實際問題具有一定的合理性。5.1距離代價函數(shù)和距離代價最小準(zhǔn)則一個好的聚類應(yīng)該使聚

23、類中心的間距盡可能大，而樣本中心間距盡可能地，小。令K = X,耕為空間聚類的聚類空間，其中X = %,x2,x ，假設(shè)n個 空間對象被聚類為k個簇，現(xiàn)做如下定義：1 2，n（1）類際距離為所有聚類中心（簇內(nèi)樣本的均值）到全域中心（全體樣本 的均值）的距離之和L =丈 m - mi=1式中，L為類際距離，m為全部樣本的均值，m,為簇。，所含樣本的均值， k值為所要聚類的個數(shù)。（2）類內(nèi)距離為所有聚類簇內(nèi)部距離的總和，其中，每個簇的內(nèi)部距離為 該簇內(nèi)所有樣本到其中心的距離之和D = |p m|ii=1 pcCt.式中，D為類內(nèi)距離，p為任意空間對象及樣本點，1,m,Ct,k含義與上 式含義相同。

24、（3）距離代價函數(shù)為類際距離與類內(nèi)距離之和F (S, k) = L + D = |i = 1|m.-m| + i=1 peCt i式中，F(xiàn)（S,k）為距離代價函數(shù)，其他符號含義與上二式相同。在運用距離代價函數(shù)作為空間聚類有效性檢驗函數(shù)時，我們運用距離代價 最小準(zhǔn)則，即當(dāng)距離代價函數(shù)取得最小值時，空間聚類結(jié)果為最優(yōu)，k的最優(yōu) 選擇由下式給出：min（F （S, k）, k = 1,2,., n5.2基于距離代價函數(shù)的空間聚類k值優(yōu)化算法距離代價最小準(zhǔn)則雖然能夠求出最優(yōu)聚類數(shù)，但在樣本點偏多時k的取值 范圍偏大，計算量過大。我們可以通過經(jīng)驗規(guī)則k Jn （n為所有樣本點個數(shù)）縮小最優(yōu)解范圍，這樣便

25、能大大降低計算量。于是，空間聚類k值優(yōu)化算法過 程如下：k值優(yōu)化算法:在K -means算法基礎(chǔ)上，通過距離代價函數(shù)優(yōu)化k值輸入：包含n個對象的數(shù)據(jù)庫輸出：距離代價函數(shù)最小條件下的k*個簇步驟：（1）根據(jù)經(jīng)驗規(guī)則計算和確定最優(yōu)解的上界k 品。（2）用K-means算法實現(xiàn)k 卻所有數(shù)目下的空間聚類。（3）根據(jù)距離代價函數(shù)分別計算不同聚類數(shù)目k下的F（S,k）值。（4）搜尋距離代價函數(shù)最小的F（S,k），并記下相應(yīng)的k*值。（5）結(jié)束。5.3用K-means算法求解聚類中心上一步中已經(jīng)得出最優(yōu)聚類數(shù)k*，從全體樣本點中隨機選擇k*個對象（樣本），每個對象成為一個種子，代表一個簇（類）的均值或中心

26、，對剩余的每 個對象，根據(jù)其與各簇中心的距離將它賦給最近的簇，然后重新計算每個簇內(nèi) 對象的平均值形成的新的聚類中心，將這個過程重復(fù)進行，直到準(zhǔn)則函數(shù)E = |p - m |2i=1 pCtj收斂為止。式中，E是所有研究對象的平方誤差和，p為空間任意一點，即數(shù)據(jù)對象，m,為簇Ct,所含樣本的均值，按照這個準(zhǔn)則生成的結(jié)果簇趨向于獨立和緊湊。5.4模型優(yōu)化處理記A = x ,x，,心,x （i = 1,2, .,68）為樣本空間，由經(jīng)驗準(zhǔn)則知，聚類12 i 68數(shù)k滿足不等關(guān)系k n（n = 68），因為k為整數(shù)，所以其可能取值為1,2,.,8，記k = i（i = 1,2,.,8），用K-mean

27、s算法求出聚類數(shù)k下的聚類空間，再求出相應(yīng)的距離代價函數(shù)F（S,k ），計算結(jié)果如下：,iK12345F3305.332351.171914.751767.381402.67cluster 1 cluster cluster 3 rlusterd cluster h圖八聚類優(yōu)化分析圖模型分析和評價問題一中求連通圖的最小生成樹時既可用Pr im算法也可用Kruskal算法， 但前者具有更高的效率，且算法易拓展，所以本題中用的是Prim算法。問題二用到了傳統(tǒng)的K-means算法，它是一種比較簡潔和快速的聚類算法， 但它是在給定類別數(shù)k的情況下對樣本實現(xiàn)類別劃分的一種方法。事實上，在 很多時候并不知

28、道事先將數(shù)據(jù)集分成多少個類別才最合適，所以剛開始的k的 值具有一定的主觀性，模型不是最好的模型，又由于它的優(yōu)化空間不大，可以 大大減少計算量，所以這個算法有可取點也有不可取點，應(yīng)視具體問題具體分 析使用。參考文獻1楊善林，李永森，胡笑旋，潘若愚，K-means算法中的k值優(yōu)化問題， 系統(tǒng)工程理論與研究，2006年2月第2期，1-5楊會鋒，曹潔，帥立國，基于改進K-均值聚類算法的背景建模方法，電 子測量與儀器學(xué)報，2010年12月 第24卷第12期，1115-1116function T c=Primf(a) l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;lis

29、tV(1)=1;e=1;while (ea(i,j) min = a(i,j);b=a(i,j); s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=source;destination;for g=1:e-1c(g)=a(T(1,g),T(2,g);endc;sample=0 2510 10014.4117647116.4705882417.2839506217.7777777818.4210526320 021.5384615455.8823529435.29411765

30、27.1604938322.2222222215.78947368 71.1538461522.09302326 13.95348837 23.20610687 21.3740458 24.20382166 28.0254777126.20689655 41.3793103428.18181818 54.54545455 29.06779661 87.28813559 30 1032 4532.265625 94.14062532.72727273 84.8484848534.05063291 93.67088608 35 10036.02739726 93.1506849337.777777

31、78 81.48148148 38.0952381 29.76190476 38.91891892 18.918918925.35714285721.4285714351.4285714342.66666667 18.3333333345.39877301 30.67484663 46.08695652 26.08695652 47 7.547.25490196 90.1960784347.36 17.648.8 850 031.4285714357.24137931 10.3448275960.84507042 15.49295775 63.22580645 64.51612903 70.4

32、 1472.28070175 70.175438673.97260274 34.24657534 76 5682.22222222 62.22222222 85 5085.10638298 11.7021276687.40740741 79.6296296389.48717949 56.4102564192.24489796 82.65306122 97.08333333 77.08333333 100.2325581 80.23255814 102.8888889 75.55555556 103.1578947 37.89473684 105.125 78.75111.3513514 38.

33、91891892118.8235294 27.45098039 120 100123.3333333 24.44444444123.9175258 28.86597938127.6470588 25.88235294131.7241379 70.68965517 132.9411765 67.64705882 142.8571429 42.85714286146 35147.0588235 32.35294118 160 0200 50;%Kmeans聚類函數(shù)function D,L,cluster_center=kmeans(k) load dotdist=;sample=result;dingdian=;% 頂點確定%畫出所有點figure;hold onfor i=1:size(sample,1)plot(sample(i,1),sample(i,2),k*)end%中心點x_mean=mean(result(:,1),mean(result(:,2)d=abs2(sample,x_mean);din