《B题 公园内道路优化.doc》由会员分享，可在线阅读，更多相关《B题 公园内道路优化.doc（25页珍藏版）》请在金锄头文库上搜索。
1、一、问题重述（一）问题背景校园是师生学习生活的重要场所。为了美化校园环境并为其学生提供更好的生活条件，西安某大学计划建一个形状为矩形或其他不规则图形的公园。（二）问题重述公园计划有若干个入口，我们需要建立一个模型去设计道路让任意两个入口相连，使总的道路长度和最小。条件与要求：1） 默认矩形公园的四条边上存在已经建好的道路，此道路不计入道路总长；2）任意的两个入口之间的最短道路长不大于两点连线的1.4倍。3）公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图 1 公园及入口示意图主要设计对象可假设为如图所示的长200米宽100米的矩形公园，1至8各入口的坐标分别为：P1(
2、20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25). 我们面临的问题是：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70)。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。图 2 一种可能的道路设计图问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖，新
3、修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二的任务。图3 有湖的示意图其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。二、问题分析1、问题一：我们初步认为确定使用的、也是仅使用的四个交叉点，为了实现使公园内总路程最短的设计目标，考虑到公园四周的边不计入道路总长的前提，我们把问题化简为满足限制条件（任意两个入口之间的最短道路长不大于两点连线的1.4倍）的十二个点间的最小生成树模型，运用克鲁斯卡尔（Kruskal）算法，后期通过人为修正，最终得出最短路径。2、问题二：在“现在公园内可以任意修建道路”的前提下，联系并比
4、较问题一，在问题二中我们首先要解决的问题是确定交叉点。在离散化和赋权基础上，我们通过建立概率场确定出点的数目和大致位置。然后构建两种模型解决最终问题：1.寻找概率最大的点，再运用最小生成树算法得出路径；2.按照局部优化思想，把区域分成两部分，找出费马点确定交叉点并连接路径。3、问题三：结合实际应用，在问题二基础上，问题三增设限制为“公园内有一条矩形湖，新修道路不能通过”。然而我们在问题二中求出最短路径经过矩形湖，所以我们需要对问题二所得优化路径进行调整。由于问题二运用局部最优思想，并且考虑到修改交叉点对全局的影响，我们只需集中针对湖附近的交叉点，运用穷举法，最终实现修正.三、模型假设与约定1）
5、考虑到对实际建设的影响和方便数据处理，我们将路径长度精确到0.1米；2）为了简化模型，我们约定可以忽略实际道路宽度，将实际问题抽象为点线（入口与道路交会处为点，道路为线）问题；3）假设问题一中仅使用给定的四个交叉点；4） 假设问题三中矩形湖四周的边没有路，即沿湖行走需要新修道路；5）计算两个入口间最短道路长时边界道路长度不可不计；6）假定满足最短总长度的道路设计同时也满足设计审美。四、符号说明及名词定义G赋权连通图V赋权连通图中的顶点E赋权连通图中的边d两点间的距离S具有永久标号的顶点集表示从顶点: 到的一条路的权的父亲点，用以确定最短路的路线D邻接矩阵b最小生成树输出矩阵最短道路的总路程h概
6、率场权值离散化：把无限空间中有限的个体映射到有限的空间中去。在本文中指规划区域抽象成点集。局部优化：把区域分割后分别优化，并且各区域间互不影响。费马点：在一个三角形中到三个顶点距离之和最小的点。长径比：一个点与两个焦点连线长度之和与焦点距离的比值。五、问题一（一）模型建立本题确定使用4个道路交叉点A( 50,75 )，B( 40,40 )，C( 120,40 )，D( 115,70 ) ，要求设计道路使公园内道路路程最短（重申：四周道路默认已建，不计入总路程）。我们将8个路口和4个交叉点简化为12个点，因此最短路径是由12个点形成的赋权连通图的最小生成树。基于上述分析，我们建立了最小生成树模型
7、，该模型运用克鲁斯卡尔（Kruskal）算法求解。再运用迪杰斯特拉（Dijkstra）算法对结果进行修正模型。1.克鲁斯卡尔（Kruskal）算法步骤如下：设G=(V,E)是一个顶点数为的赋权连通图。 （1）把赋权连通图的边按权递增的顺序排列（如果有两条以上的边权相等，则这些边之间的顺序可以任意）。 （2）选择边 E，使得()尽可能小。 （3）若已选好边，则从E/，中选取，使得： （i）G，为无圈图； （ii）()是满足（1）的尽可能小的权。 （4）若已选得条边，则停止，否则转（3）。在得到最小生成树之后，我们运用两点间距离公式： （1.1）2.迪杰斯特拉（Dijkstra）算法（并且结合任意
8、的两个入口之间的最短道路长不大于两点连线的1.4倍的限制条件）对每条路径进行修正。修正步骤如下：（1）运用迪杰斯特拉（Dijkstra）算法求处一点到其他任意一点间最短路径。（2）运用公式（1.1）求处两点间连线距离。（3）比较两者长度，若不满足1.4倍的限制条件，则从起点增加一条到其他任意点的连线，并转（1）。（4）将所有点间最短路径未利用的边删去。迪杰斯特拉（Dijkstra）算法步骤：（1）赋初值：令。，令，。（2）更新，：，若，则令，（3）设是使取最小值的中的顶点，则令，。（4）若，转（2）；否则停止。用上述算法求处的就是到的最短路的权，从的父亲点标记追溯到，就得到到的最短路的路线。（
9、二）模型求解考虑到默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长，第一步先针对可以利用已存在道路并且满足两个入口之间的最短道路长不大于两点连线的1.4倍的点进行筛选，再对剩余点在数学上抽象为“矩阵”，以矩阵的行和列表示入口和交叉点的地点，以矩阵中由行列所确定的位置表示两点间连线，以矩阵中点的权值表示两点连线的距离。用点对的方法表示两点间的连线，如P1和P2的连线表示为 (P1,P2) ，而可利用已存在道路的只有8个入口，利用两点间距离公式（1.1）筛选满足两个入口之间的最短道路长不大于两点连线的1.4倍的点，最终得到需要通过交叉点或两点连线的点对有：( 1,5 )，( 1,6 )，
10、( 1,8 ) ，( 2,5 )，( 2,6 ) ，( 2,7 )，( 3,4 )，( 3,5 )，( 3,6 )，( 3,7 )，( P1,A )，( P1,B )，( P1,C )，( P1,D )，( P2,A )，( P2,B )，( P2,C )，( P2,D )，( P3,A )，( P3,B )，( P3,C )，( P3,D )，( P4,A )，( P4,B )，( P4,C )，( P4,D )，( P5,A )，( P5,B )，( P5,C )，( P5,D )，( P6,A )，( P6,B )，( P6,C )，( P6,D )， ( P7,A )，( P7,B )
11、，( P7,C )，( P7,D )， ( P8,A )，( P8,B )，( P8,C )，( P8,D )。现在建立1212的邻接矩阵，由于矩形的四条边上存在已经建好的道路不计入道路总长，则可利用已存在道路的两点间权值为0，建立邻接矩阵如下（三）结果展示我们用Matlab 2012编写克鲁斯卡尔（Kruskal）算法程序，将邻接矩阵输入最小生成树模型中，得到结果为：矩阵中，权值为0的点表示两点不连通，有数值则说明两点连通。我们用几何画板 5.0.4根据所的矩阵绘制相应的路径图，如下：由于P2与P8，P6与P7在矩阵中的权值为0，即在计算最小生成树时两点重合，因此，在（P2，8）和（P8，8
12、），（P6，A）和（P7，A）中较短的一条。修正后的路径图为：我们利用修正模型，发现在该路径中（P5，D）这条路径不满足小于1.4倍连线长的限制，并加以修正，得到满足条件下的最短路径，路径图为：最短路径长度为：六、问题二 在此问题中我们通过两种不同思路，尝试找到满足条件最短路径。（一）思路一1.模型建立按照题设“两个入口之间的最短道路长不大于两点连线的1.4倍”来考虑P1至P8中的任意两点Pi、Pj，若有一点M使，则M必在以Pi和Pj为焦点、为长轴的椭圆内部（含边界）。显然这一点M最好落在线段PiPj上时,路径最短。由于越长路径就越大，而这样的M就越不可能成为交叉点。而由于针对面积计算量较大，
13、且结合实际情况，只需将面离散为点进行计算。基于上述分析，我们建立离散化模型，将平面离散为100200，间距为1米的点阵。我们还建立概率场模型，引入长径比的概念来衡量M的可能情况，称这个比值为M的权值，记做h。由题中区域图易得：把权值作为Z变量用Matlab 2012可以画出区域内的一个三维赋权图。我们考虑权的峰值也就是图中相对于旁边位置比较高的点。通过权值的意义可以得出结论这个或者这些点理论上最可能成为交叉点。我们先记录这个或者这些点的坐标，通过观察按照以下条件排除不可能作为交叉点的点：（1） 交叉点不可能出现在边框上。因为这样的点没有意义。（2） 交叉点不可能很接近边框的位置。因为这样的位置
14、靠近一边而远离另一边，按照顺序不等式的思想会产生最偏离极值的值。（3） 摒弃多个交叉点聚集在一起的情形，只留下其中最合理的点。因为考虑到模型建立在道路设计的实际问题中，这样的点既不美观也妨碍通行，没有考虑的必要。 接下来是一个已知点与边框求最短距离的问题。 与第一问相同，我们假设这些点形成一个赋权完全图，然后采取最小生成树算法。将数据以矩阵形式导入后用Matlab 2012进行处理，得出一个邻接矩阵。根据邻接矩阵我们可以利用几何画板 5.0.4初步作出路径图。再考虑“任意的两个入口之间的最短道路长不大于两点连线的1.4倍”这一题设条件，我们可以增加或者删除一些连线，对图做细微修改，得出最终结论
15、。2.模型求解求解过程及结果展示 使用VC+6.0程序输出这八个点之间的距离矩阵：使用Matlab 2012编写程序画出以P1到P8中任意两点为焦点形成椭圆的相交图： 因为椭圆数目过多而对各个点的影响差别较大，所以结合问题一的求解，我们最终选择了优化后的十个点对作为基础，以这些点对为焦点按照模型建立给出的步骤编写C语言程序，求出区域中所有点的权值，输出在矩阵里。由于含20000个点，数目太大，故在此不一一输出，只在附录中给出C语言程序。把权值做为区域中点的高，借助Matlab 2012作出图像： 取两个权的峰值点做区域中新加入的点，分别记为Q1、Q2，用几何画板 3.0.4作图如下： 那么可以求得此图中十个点的邻接矩阵： 把矩阵带入最小生成树算法再按照模型建立中的方法修改得到最终连线图：那么，在思路一中最短总路程：
