资源描述：
《公园道路优化模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、公园内道路优化模型摘要本文主要讨论公园内的道路修建问题。在数据的处理方面，我们较多的使用了MATLAB，LINGO，VC++6.0，VS2010软件，使得在解决具体问题时操作简便，效率更高，能节省大量时间。针对第一问，在忽略前提要求的情况下任意的两个入口之间的最短道路长不大于两点连线的1.4倍，采用Prim算法利用最小生成树求得一个满意解，为满足前提要求，优化算法，利用Dijkstra算法循环计算，发现路径P1-P5和P2-P5均不满足前提要求。因此，我们在此基础上进行局部优化，调整原则是使总路径尽可能的小，且其他入口的最短路径不变。最终得到相对最优解为394.
2、56.针对第二问，将约束条件用椭圆直观的表示出来，将可行点锁定在椭圆交叉的公共区和密集区域，在椭圆交集最密集的地方添加道路交叉点或选取搜索初始点。接下来充分利用公园四周的道路，由LINGO程序算出可行解，再由C++程序搜索更好的点，利用上述思路分别考察道路价差点为0,1,2,3的情况。经过计算发现，0个交叉点时，不满足约束条件；1个交叉点时，道路总长度的最小值为379.62；再增加一个交叉点，采用局部搜索方法，得出2交叉点时的道路总长度的最小值为358.53；3个交叉点时类似讨论，道路总长度的最小值为357.96。通过比较发现道路总长度的最小值为357.96，即
3、三个交叉点时道路总长度的最小。对于第三问，实质是在第二问有约束条件的最小生成树问题的基础上再添加了一个约束条件，对于这类问题的求解，我们的想法是（1）将路径的一个交叉点固定在湖的一个顶点上，（2）对经过湖的路径进行旋转，从而有效的化解了不能穿过湖这一约束条件，降低了求解难度，具体方案如下：方案一，选取湖的一个路径，参照第二问的搜索思路，用椭圆图为选取初始点作参考，由LINGO软件求出可行解，最后由C++程序循环搜素该可行点附近的点，期望找到更好的点。最终得到的四个交叉点坐标为(64,63)、(112,74)、(162,30.5)、（140,45），道路总长度的为
4、359.94.方案二：对经过湖的路径进行旋转，使之不经过湖。得到的道路总长度均比359.94要长。故最终能够得到的最好的四个交叉点坐标为(64,63)、(112,74)、(162,30.5)、（140,45），道路总长度的为359.94.关键词：Prim算法、Floyd算法、Dijkstra算法、局部搜索、贪婪算法11问题重述西安某大学为美化校园环境，要建设一个有八个入口的矩形公园，要求建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间
5、的最短道路长不大于两点连线的1.4倍。矩形公园的长为200米，宽为100米。各个入口的坐标分别为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个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问题二：在公园内可以任意修路的情况下，如何在满足条件下使总路程最少，建
6、立模型并给出算法。给出道路交叉点的坐标，画出道路设计，并计算新修路的总路程。问题三：若公园内有一个矩形的湖，新修的道路不能通过，但是能够到达湖的四周，矩形湖的四个角的坐标分别为R1（140，70），R2（140，45），R3（165，45），R4（165，70）。重复完成问题二的任务。注：以上问题要求公园内新修的道路与四周的连接只能与八个入口连通，而不能连到四周其它点。2问题分析题中给出了八个入口的坐标，并要求这八个入口间任意两个能够通过道路连通，且要求出最短的道路设计方案。分析题目可以看到，这属于图论中的最小生成树问题，先把满足题目要求的最短的修路方案找到，然
7、后根据条件任意的两个入口之间的最短道路长不大于两点连线的1.4倍进行道路的微调，下面基于这一基本问题根据不同的情况设计不同的修路方案。2.1问题一分析对于问题一，题中给出了四个固定的道路交叉点的坐标，而且公园八个入口的坐标也已知，也就是这12个点必须通过所修的道路能够连通。因此可以把问题考虑成求通过12个顶点的最小生成树问题，根据Floyd和Prim算法，用Matlab软件进行求解。求出最小的修路方案之后，根据任意的两个入口之间的最短道路长不大于两点连线的1.4倍进行道路的检验，如果不满足，则在保证所修道路最短的前提下进行道路的微调，直至满足题目所要求的为止。2
8、.2问题二分析对于问题二
