公园内道路设计问题

1、目录 TOC o 1-5 h z HYPERLINK l bookmark17 o Current Document 问题提出1 HYPERLINK l bookmark33 o Current Document 模型假设2 HYPERLINK l bookmark39 o Current Document 符号说明2 HYPERLINK l bookmark58 o Current Document 模型建立与求解34.1基于Prim算法和 Dijkstra 算法的模型34.1.1模型建立34.1.2模型的求解与优化44.2基于改进K means 聚类算法的模型74.2.1模型建立74.2.

2、2模型求解94.3回归优化模型104.3.1模型建立104.3.2回归模型的求解与检验11 HYPERLINK l bookmark150 o Current Document 模型优化125.1距离代价函数和距离代价最小准则125.2基于距离代价函数的空间聚类k值优化算法135.3用K - means算法求解聚类中心135.4模型优化处理13 HYPERLINK l bookmark181 o Current Document 模型分析与评价14 HYPERLINK l bookmark185 o Current Document 参考文献14附录1 15附录2 16附录3 18问题提出西安

3、某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美 化校园环境，也是想为其学生提供更好的生活和学习条件。在综合考虑了校园 各地方平均人流量后，公园计划有若十个入口，为了保证公园里人员不过于拥 挤和出入快捷方便，现在需建立一个模型去设计园内道路(可以利用公园四周 的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长)， 使任意两个入口相连，且总的道路长度和(这一总长度可能与成本成正比)最 小，同时还要满足任意的两个入口间的最短道路长不大于两点连线的1.4倍。考虑到不规则图形的复杂性、矩形的特殊性和普适性以及实际中的公园面 积一般不会太小等因素，本题主要设计对象可假设为如图

4、一所示的矩形公园， 其相关数据为：长200米，宽100米，1至8号各入口的坐标分别为P1(20,0), P2(50,0), P3(160,0), P4(200,50), P5(120,100),P6(35,100),P7(10,100), P8(0,25)现完成以下问题：假定公园内确定要使用的4个道路交叉点为4(50,75), B(40,40), C(120,40), D(115,70).图二所示即是一种满足要求的设计，但并不是最优的，问如何设计道路可使公园内道路的总路程最短。建立数学模 型并给出算法。画出道路设计，计算新修路的总路程。现在公园内可以任意修建道路，如何在满足条件下使总路程最短？

5、建 立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总 路程。若公园内有一条矩形的湖，如图三所示，新修的道路不能通过，但可 以到达湖四周的边，重复完成问题二的任务。其中矩形湖位置坐标为夫1(140,70), R2(140,45), R3(165,45), R4(165,70).注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相 通，而不能连到四周的其他点。图二一种可能的道路设计图图一公园及入口示意图图三有湖的示意图模型假设设计道路只考虑路径长短，道路宽度处处相同且不考虑美观效果。经验值具有一定的科学规律，可实施。符号说明C1:记矩形边框网格线最小距离不大于连线距

6、离1.4倍的无序点对为C1类无 序点对C2 : P,P,.,P构成的所有无序点对中除C1类之外的无序点对记为C2类无 128序点对C :以公园8个入口 P,P,.,P为顶点的连通图的邻接矩阵 128B : P，P,.,4 8个点中任意两点沿矩形边框的最短距离构成的矩阵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 的所有聚类结果构成的集合p :空间中的任意一点，即X = x1, %., xn 中的样本点Ct : K-means算法求得的聚类数k下的类(簇)m :簇Ct,所含样本的均值 m :全部样本的均值模型建立与求解4. 1基于Pr im算法和 Dijkstra 算法的模型4. 1.1模型建立因为公园四周边上已经建好的道路不计入道路总长，要想园内道路总路程 最短，应尽可能利用矩形边框道路。由于C1类无序点对满足边框最短距离不大 于1

8、.4倍连线距离，所以C1无序点对对应的入口可以通过公园边上道路连通， 在进行道路设计时不予考虑；对C 2类无序点对，可以将相关点连成连通图，通 过Prim算法得出相应的最小生成树，再通过Dijkstra算法得到这些无序点对的 最短路径，最后检验验证方案设计是否符合要求，若方案不合理，则需修改优 化模型，直到得到符合条件的最佳道路设计方案为止。（I）确定C1,C2类无序点对根据图一坐标得到以公园8个入口 P,P, ,P为顶点的连通图的邻接矩阵 TOC o 1-5 h z 128C以及这8个点中任意两点沿矩形边框的最短距离构成的矩阵B。进行矩阵运M = 1.4C - B对矩阵元素进行分析，当m 0

9、时，1.4c b，即P,P两点的矩形边框距 、 .j 一 j i j .离不大于两点连线的距离的1.4倍，P,P构成的无序点对属于C1类无序点对， 在设计道路时，不需考虑这两点对应入口的道路连接问题；当m 1.4b矿 i, j = 1,2,3,5,6,7成立，说明图四中相应的连线不符合要求，需要将结果进行修改优化。综合考 虑所有无序点对间的最短道路长和最短道路总长，在已经连接好的路线不做太 大改变的前提下，将不合理的路线进行适当的修改优化，直到所有路线都满足 要求且道路总长最小为止。4.1.2模型的求解与优化（I）根据图一坐标得到以公园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个点中任意两点沿矩形边框的最短距离构成的矩阵一 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 _当m 0时，点(i, j)属于C1类无序点对；当m 0时，点(i, j)属于C2类无序 点对。由矩阵M的输出结果知，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 经观察分析，在所有C2类无序点对中，p,P均只在一对无序点对中出现， 所以优先单独分析(1，8)和(3, 4)。4 8在图二所示的道路设计坐标图中可以看出，P, P经过其他任意点间接连接起来的路程l (1,8)满足不等关系1 8l(1,8) 、 1.4%同理有，l(3,4) 、 1.4c34所以，P,P和P,P对应的两对入口必须分别直接连通。 18

15、34余下未处理的 C2 类无序点对有(1,5), (1,6), (2, 5), (2, 6), (2, 7), (3, 5),印6 7)，将与上述无序点对的连接有关的点(P,P,P,P,P,P,P,&B,C,D)两两连接，1235678对得到的连通图G用Prim算法得到相应的最小生成树T。算法运行后输出的最小生成树T如下图四所示：图四最小生成树由于最小生成树只保证了 C2类无序点对连接总路程最短，并不一定满足无 序点对对应的入口之间的道路长不大于两点连线距离的1.4倍，所以需要检验。用Dijkstra算法对模型进行修改优化并检验模型的可行性优化一：经Dijkstra算法计算得到，p,P5两点间

16、的最短路径为P IP IBIAIDIP，但最短道路长d(1,5)1.4。，所以该路径不可取。 TOC o 1-5 h z 18515在道路总长最小的前提下，为减少入口2和入口5间的道路长，可以将上述路径优化为P IP IBIAIP。125优化二：通过观察，在连通入口 7的道路中，AIP段可以优化，可以先7假设优化模型再验证检验假设的合理性。假设该段道路可以用AIP IP优 化代替，即在优化模型中去掉A I P段，用Dijkstra算法可以求出：点到其他 各点的最短路径和最短距离，计算结7果均满足不等关系7d (7, j) 8 d ,（8go.5,1），则x.（i = s或t）为第三个聚类中心，

17、类别数K = K +1 ;否则算法结束（6）重复（3）（5）根据已经设定的聚类数k = 2，运用K - means算法求出聚类数2下的聚类 中心。（III）以聚类中心为道路交叉点设计最佳道路空间聚类一般使用距离作为划分准则，即任一空间对象与该对象所属簇的 几何中心之间的距离比该对象到任何其他簇的几何中心的距离都小，所以，上步中得到的聚类中心可以作为公园道路规划时园内交叉路口。在确定了道路交 叉点的个数和位置后，我们可以套用问题一的模型来设计最优道路方案。4.2.2模型求解输入P,P,.,P各点的坐标，运用算法1得到两两连线交点，输出结果128如下图六所示：10090807060 50 40 3

18、0 20 10020406080100120140160180200图六入口两两连线示意图重合的交点不计算在内，一共得到68个交点，用x (i = 1,2, .,68)表示各交 点，交点坐标的输出结果见附录2ik -means算法求解聚类中心记A = x ,x，,x,.,x (i = 1,2,.,68)为样本空间，由经验准则给定聚类12 i 68数k = 2,用K -means算法求出聚类数k = 2下的聚类空间。运行结束时输出k = 2时的聚类空间，将求得的两个中心分别记为S，计算结果为S1 = (172,42), S2 = (60,77)以聚类中心为道路交叉点设计最佳道路以S = (172

19、,42),S = (60,77)为道路交叉点设计道路使道路总长最短，可以 套用问题一中的模型，2最后输出结果如下图六所示：图六以聚类中心为交叉点的道路设计经计算，新修道路总长为358.6米。4.3回归优化模型4.3.1模型建立问题三相对于问题二只是多了矩形湖的限制，可以在做尽量少的改变的前 提下优先优化经过湖面区域的路径，再对优化后的模型进行检验验证。(I)回归模型建立由问题二的设计方案知，只有路径S1P5经过了湖面区域，所以首先对 该路径进行优化，另外找一合适的点 ,使得路径S 一P不经过湖面区域且改 变的路径P 一 S 一P最短，为寻找这一S点建立如下回归模型：3353设S;= (a,b)

20、， S1= (S3 ,S3 ) = (172,42),目标函数为y =、；(a -120)2 + (b -100)2 ;(a - S3)2 + (b - S3)2代入数据，于是，目标函数可简化为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 -弓的最短路径问题转化为求目标函数 y =、：(a 120)2 +(b 100)2 +、a -172)2 +(b - 42)2在上述约束条件确定的可行域里何处

21、取最小值的问题，该回归模型通过Lingo 求解，结果输出就是我们要找的点S3。(II)模型检验在确定S3点后，我们还需要进行检验，验证优化模型中任意两点间的最短 道路距离是否都不大于两点连线距离的1.4倍，用Dijkstra算法(算法说明问题 一中已经给出)可完成检验过程。若经验证模型符合1.4倍的要求，则模型可取; 若经验证模型不符合1.4倍的要求，则需进一步优化，此时，需综合考虑路径最 短距离和道路总路程最短，在尽量少地改动符合条件的路线的前提下，将不符 合条件的路线修改优化，直到模型检验结果符合要求为止。4.3.2回归模型求解与检验将上述建立的回归模型在Lingo中运行，运行结果为a =

22、 165,b = 70，即R4 点，此时道路设计如下图七所示：对图七所示连通图用Dijkstra算法求得任意两点间的最短路径和最短距离， 经计算，任意两点间的最短路径距离均不大于连线距离的L4倍，这说明该设计 方案是合理的。又由于在回归模型中，求解的是最小值且其他路线的连接情况 并未改变，所以该设计方案也是最佳的。经计算，新修道路总长为361.7米。模型优化由于典型的K - means算法是在k准确给定的条件下实现的，所以要先算出 最优的聚类k值，本题借用距离代价函数和距离代价最小准则求解最佳聚类数k， 该方法对实际问题具有一定的合理性。5.1距离代价函数和距离代价最小准则一个好的聚类应该使聚

23、类中心的间距尽可能大，而样本中心间距尽可能地，小。令K = X,耕为空间聚类的聚类空间，其中X = %,x2,x ，假设n个 空间对象被聚类为k个簇，现做如下定义：1 2，n（1）类际距离为所有聚类中心（簇内样本的均值）到全域中心（全体样本 的均值）的距离之和L =丈 m - mi=1式中，L为类际距离，m为全部样本的均值，m,为簇。，所含样本的均值， k值为所要聚类的个数。（2）类内距离为所有聚类簇内部距离的总和，其中，每个簇的内部距离为 该簇内所有样本到其中心的距离之和D = |p m|ii=1 pcCt.式中，D为类内距离，p为任意空间对象及样本点，1,m,Ct,k含义与上 式含义相同。

24、（3）距离代价函数为类际距离与类内距离之和F (S, k) = L + D = |i = 1|m.-m| + i=1 peCt i式中，F（S,k）为距离代价函数，其他符号含义与上二式相同。在运用距离代价函数作为空间聚类有效性检验函数时，我们运用距离代价 最小准则，即当距离代价函数取得最小值时，空间聚类结果为最优，k的最优 选择由下式给出：min（F （S, k）, k = 1,2,., n5.2基于距离代价函数的空间聚类k值优化算法距离代价最小准则虽然能够求出最优聚类数，但在样本点偏多时k的取值 范围偏大，计算量过大。我们可以通过经验规则k Jn （n为所有样本点个数）缩小最优解范围，这样便

25、能大大降低计算量。于是，空间聚类k值优化算法过 程如下：k值优化算法:在K -means算法基础上，通过距离代价函数优化k值输入：包含n个对象的数据库输出：距离代价函数最小条件下的k*个簇步骤：（1）根据经验规则计算和确定最优解的上界k 品。（2）用K-means算法实现k 却所有数目下的空间聚类。（3）根据距离代价函数分别计算不同聚类数目k下的F（S,k）值。（4）搜寻距离代价函数最小的F（S,k），并记下相应的k*值。（5）结束。5.3用K-means算法求解聚类中心上一步中已经得出最优聚类数k*，从全体样本点中随机选择k*个对象（样本），每个对象成为一个种子，代表一个簇（类）的均值或中心

26、，对剩余的每 个对象，根据其与各簇中心的距离将它赋给最近的簇，然后重新计算每个簇内 对象的平均值形成的新的聚类中心，将这个过程重复进行，直到准则函数E = |p - m |2i=1 pCtj收敛为止。式中，E是所有研究对象的平方误差和，p为空间任意一点，即数据对象，m,为簇Ct,所含样本的均值，按照这个准则生成的结果簇趋向于独立和紧凑。5.4模型优化处理记A = x ,x，,心,x （i = 1,2, .,68）为样本空间，由经验准则知，聚类12 i 68数k满足不等关系k n（n = 68），因为k为整数，所以其可能取值为1,2,.,8，记k = i（i = 1,2,.,8），用K-mean

27、s算法求出聚类数k下的聚类空间，再求出相应的距离代价函数F（S,k ），计算结果如下：,iK12345F3305.332351.171914.751767.381402.67cluster 1 cluster cluster 3 rlusterd cluster h图八聚类优化分析图模型分析和评价问题一中求连通图的最小生成树时既可用Pr im算法也可用Kruskal算法， 但前者具有更高的效率，且算法易拓展，所以本题中用的是Prim算法。问题二用到了传统的K-means算法，它是一种比较简洁和快速的聚类算法， 但它是在给定类别数k的情况下对样本实现类别划分的一种方法。事实上，在 很多时候并不知

28、道事先将数据集分成多少个类别才最合适，所以刚开始的k的 值具有一定的主观性，模型不是最好的模型，又由于它的优化空间不大，可以 大大减少计算量，所以这个算法有可取点也有不可取点，应视具体问题具体分 析使用。参考文献1杨善林，李永森，胡笑旋，潘若愚，K-means算法中的k值优化问题， 系统工程理论与研究，2006年2月第2期，1-5杨会锋，曹洁，帅立国，基于改进K-均值聚类算法的背景建模方法，电 子测量与仪器学报，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聚类函数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