《公园内道路最优化设计的讨论》由会员分享，可在线阅读，更多相关《公园内道路最优化设计的讨论（14页珍藏版）》请在金锄头文库上搜索。
1、公园内道路最优化设计的讨论摘要本题要解决的是公园内道路设计的最优化问题，就是需要建立一个模型去设计公园内部的道路，要求在满足约束条件的前提下找出总路程长度和最短的最优解，并给出相应的道路设计图。针对问题一，首先不考虑 ABCD 四个点，假设仅利用公园四周的道路，利用 matlab 通过floyd 算法解出 P1,P2,P3P8 任两点间的最短路程 S，再利用 matlab 算出 P1,P2,P3P8任两点之间的最短距离 L，通过比较 S 与 1.4*L，选出不符合题目要求的几组：(P1,P5),(P1,P6),(P1,P8),(P2,P5),(P2,P6),(P2,P7),(P3,P4),(P
2、3,P5),(P3,P6),(P3,P7)。结合图容易看出：(P1,P8)和(P3,P4)可以确定必须要相连，则 P8 与 P4 都已经符合要求，只需再考虑其它几个点 P1，P2，P3，P5，P6，P7，A，B，C，D，利用 kruskal 算法求最小生成树，在此基础上进行局部调整优化选择最优解。根据以上算法得到的最优解为 394.5 米，示意图请参见正文。针对问题二，由于没有限定道路结点，所以根据 1.4 倍的约束条件联想到利用椭圆的性质（边界上点到两焦点的距离和为定值）来进一步缩小取点范围，这样的简化过程使解决问题的效率大大加快。第一步是以任意两点为焦点，以 1.4 倍的焦距为长轴长作椭圆
3、，观察椭圆的交集，得到覆盖程度不同的区域；第二步将覆盖程度视为符合要求的中间交叉点的可能位置概率，计算出最大覆盖程度区域的坐标范围；第三步在区域中分阶段划分精度并做出程序计算区域中点到入口点的最短距离，比较后得出最佳点。根据以上算法得到最优解为 375.2 米，示意图请参见正文。针对问题三，湖的存在即使在问题二上增加一块不可利用的矩形区域，仍然可继续借助问题二的模型，但要重新确定交叉点的范围。此问题中，由于矩形湖在公园右边，通过问题二的分析过程可知，该湖只影响右边的交叉点。所以左边的交叉点位置不必改变，只需确定右边的交叉点即可。并在此基础上利用问题二的模型继续求解。由于时间关系与目前知识水平局
4、限还未能完成问题三的最优解。关键词：Floyd Kruskal 局部优化 Matlab 动态步长 穷举法一、 问题重述某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长） ，使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的 1.4 倍。主要设计对象可假设为如图所示的矩形公园，其相关数据为：长 200 米，宽 100 米，1 至 8 各入口的坐标分别为：P1(
5、20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25).示意图见图 1，其中图 2 即是一种满足要求的设计，但不是最优的。现完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70） 。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程
6、。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图 1 公园及入口示意图图 2 一种可能的道路设计图图 3 有湖的示意图二、 问题分析因为默认的矩形公园四周存在已经建好的道路，且利用此道路长度不计入设计道路总长，可以以此为问题的突破口来简化原问题。先抛开条件中的内部四个点，讨论后找出仅利用公园四周道路时，不满足题目条件的道路。然后以找
7、出的不满足条件的道路为主要研究对象，将原问题简化，再进行下一步的讨论求解。三、 模型假设假设一：公园为矩形状，且在同一个平面，不考虑台阶的影响假设二：假设距离与入口大小无关，将各入口可视为点，把路视为直线，每个入口与节点之间的路线均为直线路径假设三:任意两个入口相连，使总的道路长度和最小，前提要求是任意两个入口之间的最短路长不大于两点连线的 1.4 倍假设四: 公园内新修的道路与四周的连接只能与 8 个路口相通，而不能连到四周的其它点假设五：用穷举法在求解问题二时，用划分的每个小区域的中心对称点的坐标来代表该区域的坐标量，当划分的区域越来越小时，两者就近似相等四、 符号系统P1,P2,P3P8
8、 任两点间的最短路程矩阵 SP1,P2,P3P8 任两点之间的最短距离矩阵 L五、 模型建立问题一：初步简化问题：首先不考虑 ABCD 四个点，假设仅利用公园四周的道路，利用 matlab 通 1过 floyd 算法解出 P1,P2,P3P8 任两点间的最短路程 S：S= 0 30 140 230 240 155 130 4530 0 110 200 270 185 160 75140 110 0 90 220 295 270 185230 200 90 0 130 215 240 275240 270 220 130 0 85 110 195155 185 295 215 85 0 25 1
9、10130 160 270 240 110 25 0 8545 75 185 275 195 110 85 0再利用 matlab 编程技算出 P1,P2,P3P8 任两点之间的最短距离 L：L= 0 30.0000 140.0000 186.8154 141.4214 101.1187 100.4988 32.015630.0000 0 110.0000 158.1139 122.0656 101.1187 107.7033 55.9017140.0000 110.0000 0 64.0312 107.7033 160.0781 180.2776 161.9413186.8154 158.1
10、139 64.0312 0 94.3398 172.4094 196.4688 201.5564141.4214 122.0656 107.7033 94.3398 0 85.0000 110.0000 141.5097101.1187 101.1187 160.0781 172.4094 85.0000 0 25.0000 82.7647100.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*
11、L=0 -12.0000 -56.0000 -31.5416 42.0101 13.4338 -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.179042.0101 99.1082 69.2154 -2.0757 0 -34.0000 -44.0000 -3.11361
12、3.4338 43.4338 70.8907 -26.3732 -34.0000 0 -10.0000 -5.8706-10.6983 9.2154 17.6114 -35.0564 -44.0000 -10.0000 0 -20.92920.1781 -3.2624 -41.7179 -7.1790 -3.1136 -5.8706 -20.9292 0通过比较 S 与 1.4*L，也就是计算 S-1.4*L 的值：选出不符合题目要求的几组(图中已标记)：(P1,P5),(P1,P6),(P1,P8),(P2,P5),(P2,P6),(P2,P7),(P3,P4),(P3,P5),(P3,P6
13、),(P3,P7)。进一步简化问题：结合图容易看出：(P1,P8)和(P3,P4)可以确定必须要相连，则 P8 与 2P4 都已经符合要求，只需再考虑其它几个点 P1，P2，P3，P5，P6，P7，A，B，C，D 即可，如图利用 kruskal 算法求 P1、P2、P3、P5、P6、P7、A、B、C、D 总共十个点的最小生成树 3在此基础上，由于（P1,P5）不满足题目条件，所以进行局部调整优化选择最优解。 4此时得到问题一的最优解为：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 米问题二：为简化
14、问题，仍使用问题一中的初始模型，即（P1,P8） （P3,P4）默认相连。 1由于没有限定道路结点，所以根据 1.4 倍的约束条件联想到利用椭圆的性质（边界上点 2到两焦点的距离和为定值）来进一步缩小取点范围，这样的简化过程使解决问题的效率大大加快。第一步是以任意两点为焦点，以 1.4 倍的焦距为长轴长作椭圆，观察椭圆的交集，得到覆盖程度不同的区域；经过讨论可知：最少需要两个交叉点，可使修建的道路满足题目要求，为简化题目，我们这里只讨论公园内有且只有两个道路交叉点的情况。第二步将覆盖程度视为符合要求的中间交叉点的可能位置概率，计算出最大覆盖程度区域的坐标范围；由几个点的空间分布易知，两个交叉点
15、分别在矩形的左右两侧，且各自作用在各自的区域，不会产生相互影响。第三步在区域中分阶段划分精度并做出程序计算区域中点到入口点的最短距离，比较后得出最佳点。利用 c 程序分别取不同步长来试探最优解的位置，先用大步长的方法找到最优解的大致位置，再将此位置细分后去较小步长比较最优解，如此循环最终得到一个通过局部优化的近似最优解，如下图：两个交叉点坐标为：E（91,58.554）和 F（161,39.4）此时得到问题二的最优解为：L(P1,P8)+L(P2,E)+L(P5,E)+L(P6,E)+L(E,F)+L(F,4)+L(F,3)=375.2 米问题三：湖的存在即使在问题二上增加一块不可利用的矩形区域，仍然可继续借助问题二的模型，但要重新确定交叉点的范围。此问题中，由于矩形湖在公园右边，通过问题二的分析过程可知，该湖只影响右边的
