《数模论文公园内道路有条件限制的设计最短路径》由会员分享，可在线阅读，更多相关《数模论文公园内道路有条件限制的设计最短路径（36页珍藏版）》请在金锄头文库上搜索。
1、装 订 线公园内道路设计最优问题摘 要对于题中所给的道路设计问题，即研究在约束条件下最小生成树问题。题中所给三个问题，研究在不同现实背景下的最优道路设计问题，根据所给限制条件的增加，层层深入。本文针对题中所述的矩形公园，利用图论中各种成熟的相关算法，对道路和最短的设计方案进行建模求解：对问题一，分为两个步骤进行建模求解。步骤一利用算法生成总道路和的最小树，步骤二用算法对步骤一生成的道路用是否满足“任意两入口间最短道路长小于二者连线的1.4倍”这一条件进行验算，对于个别不满足的道路进行微调和修改。最终方案中得到的道路总长度为394.5米。对问题二，在问题一的基础上，我们采用求解欧式距离的斯坦纳点
2、最小树的逐步调优法，根据相应理论通过离散概率随机抽取相应的斯坦纳点进行扰动，直到得到最优解。经验算确定，最终方案得到的道路总长度为362.1米。对问题三，我们利用题中的限制条件，分析了所给的人工湖位置与入口的坐标的数据特点，先确定了在不加道路交叉点情况下，仅利用湖四周的道路，即可满足任意入口间最短路径1.4倍条件的可利用的最短道路，再利用问题二中的方法添加了一个斯坦纳点，并在其邻域内进行扰动后得到最优解。经验算确定，最终方案得到的道路总长度为324.6米。最后本文还结合实际情况，对模型的优缺点进行了分析与评价，并提出了改进和推广方向。关键词：最小生成树；约束条件；算法；算法；求解欧式距离的斯坦
3、纳点最小树的逐步调优法；二叉堆目 录1.问题重述11.1.问题背景11.2.问题要求11.3.问题提出12.问题分析22.1.问题一的分析22.2.问题二的分析22.3.问题三的分析33.模型假设34.符号说明及名词解释34.1.基本符号35.模型建立与求解、检验45.1.问题一45.1.1.问题解析45.1.2. 模型建立与求解、检验75.2. 问题二95.2.1. 问题解析95.2.2. 模型建立与求解、检验95.3. 问题三95.3.1. 问题解析95.3.2. 模型建立与求解、检验96.结果表示96.1.问题一96.2.问题二96.3.问题三97.模型的评价、优化及推广97.1.模型的
4、评价97.2.模型的优化97.3.模型的推广98.参考文献99.附件清单91. 问题重述1.1. 问题背景西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。假设主要设计对象为一个矩形公园，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：.根据题目所给数据，运用数学建模方法，将实际复杂的问题理想模型简化，设计出满足题目要求的公园内道路，有很重要的现实意义。1.2. 问题要求从实际情况出发，对道路的设计有以下几个要求：1) 让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长
5、）；2) 任意的两个入口之间的最短道路长不大于两点连线的1.4倍；3) 公园内新修的道路只能通过8个路口与四周相连；4) 公园内总的道路长度和最小。1.3. 问题提出从实际情况及上述要求出发，依据相关条件和数据解决：问题一 ：假定公园内确定要使用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、故道路长度和为主要考察的对象。2.1. 问题一的分析问题一规定了一些必须经过的点。这来源于实际中所修道路要通向那些在公园建设之前就已存在的观赏景点的情况。用数学模型分析解决这一问题对此类情况有重要意义。问题一属于有限制条件的最小树生成问题。解决最小树问题，一般采用算法和算法。根据所学知识、题中数据特点和结果要求，我们选择使用算法解决最小树问题。为验算是否满足题中所给两点间1.4倍直线距离的要求，我们采用算法解决最短路径问题。2.2. 问题二的分析同问题一相比，问题二没有规定公园内必须通过的点。这来源于实际中公园内的景点及设施都是在设计公园道路后才建的情况。用数学模型分析解决这一问题对此类情况有
8、重要意义。问题二属于斯坦纳最小生成树问题。考虑到任意两点之间可以直接相连，我们采用求解欧式距离的斯坦纳点最小树的逐步调优法。2.3. 问题三的分析问题三在问题二的基础上增加了限制条件，考虑到实际中公园等休闲场所在道路规划前即有人工湖等情况，问题三即是从这一情形中抽象出来的。因此对于问题三的研究很有现实意义。问题三属于约束条件下的斯坦纳最小树问题。显然，在问题二的基础上，道路是不能通过人工湖的，因此，问题二可看作问题三的简化。考虑到重建模型的复杂性和时间的紧迫性，我们利用了问题二所建模型，针对问题二得到的结果，在此基础上进行了相关优化，直到获得最优解。3. 模型假设1) 假设所有道路均为直线；2
9、) 假设任意两点间均可修建道路，即公园内土质及其它条件对修路不产生影响（第三问的湖泊除外）；3) 假设所有道路均为无向的，不存在单行道，即道路为同一条路；4) 对于问题一，假设除了题中所给道路交叉点外，不再另外添加点。5) 对于问题三，假设矩形湖的四周也可以利用，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长。4. 符号说明及名词解释4.1. 基本符号符号意义第个入口从第个入口到第个入口的行走路线5. 模型建立与求解、检验5.1. 问题一5.1.1. 问题解析该问题给出了四个道路交叉点：A、B、C、D，在所设计道路要让任意两个入口相连（可以利用公园的矩形边），道路只能与公园的8个
10、入口相连而不能与四周其他点相连，任意的两个入口之间的最短道路长不大于两点连线的1.4倍，两点间所建道路为直线的前提下，我们所关心的问题是，如何设计出公园内道路设计的最优方案，使得道路长度和最短。我们将问题一的求解分为两个步骤：一、使用算法解决最小树问题；二、采用算法验算步骤一生成的树是否满足题中所给的两点间1.4倍直线的距离要求并进行人工微调修正。5.1.1.1. 步骤一：通过分析道路长度和最短的要求，我们发现这个问题和最小生成树问题联系最为紧密，于是考虑用贪心法求解最小生成树的算法的一些研究成果以及相关的图论知识来建立该问题的数学模型。我们先引入最小生成树的简单定义：给定一个无向连通带权图中
11、的每一条边权值为。如果的子图是一个包含中所有定点的子图，那么称为的生成树，如果的边的权值最小，那么称为的最小生成树。对于算法，其中心思想是每次添加权尽可能小的边，使新的图无圈，直到生成最优树为止，其步骤如下：1) 把内的所有边按照权的非减次序排列；2) 按1)排列的次序检查中的每一条边，如果这条边与已得到的边不产生圈，则取这一条边为解的一部分；3) 若已取得n-1条边，算法终止。此时以为顶点集，以取到的n-1条边为边集的图即为最优树。 对于问题一，题中仅给定几个固定点的坐标，并不知道相应的边。为简单起见，我们先假设任意两点之间都是可以相连的，通过相关程序，即可算出任意两点间的距离，并作为距离矩
12、阵输出。其中，将任意两点间的距离即作为该边的权。 此时，可将距离矩阵作为算法的加权矩阵，进行输入，即可得到由算法处理的最小树。附注：利用该算法时，不考虑由外矩形边框所引入的圈。 5.1.1.2. 步骤二：通过分析题中要求，任意的两个入口之间的最短路径不大于两点间连线的1.4倍，我们采用算法对于步骤一生成的树进行验算。我们先引入算法的简单定义：算法是解决关于带权图(权为非负数)的单源最短路径问题的一种贪心算法，它要一个一个地按路径长度递增序找出从某个源点出发到所有其他顶点的最短路径。算法是按长度递增的次序生成从源点到其他定点的最短路径，则当前正在生成的最短路径上除终点以外，其余的顶点的最短路径均
13、已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。可利用算法对步骤一所生成的道路中任意两入口间的最短距离进行求解得到一个矩阵，再与这两入口间距离的矩阵的1.4倍进行作差，找出负数（即不符合要求）对应的道路，进行人工合理化调整修改后即可得到最优结果。对问题一的求解过程用流程图表示如下：形成距离矩阵利用程序求任意两点间的距离由kruskal算法程序最小树最短路径矩阵Dijkstra算法1.4倍距离矩阵差距作为输入输出作差倍最优解调整 5.1.2. 模型建立与求解、检验5.1.1.1. 步骤一：将数据输入由算法对应的程序（见附录），仅仅考虑生成最小树，得到如下结果：算出来的结果：
14、边端点 距离 是否在最小支撑树 (1,2) 30 (1,3) 140 (1,4) 1.868154e+002 (1,5) 1.414214e+002 (1,6) 1.011187e+002 (1,7) 1.004988e+002 (1,8) 3.201562e+001 (1,9) 8.077747e+001 (1,10) 4.472136e+001 (1,11) 1.077033e+002 (1,12) 1.180042e+002 (2,3) 110 (2,4) 1.581139e+002 (2,5) 1.220656e+002 (2,6) 1.011187e+002 (2,7) 1.077033e+002 (2,8) 5.590170e+001 (2,9) 75 (2,10) 4.123106e+001 (2,11) 8.062258e+001 (2,12) 9.552487e+001 (3,4) 6.403124e+001 (3,5) 1.077033e+002 (3,6) 1.600781e+002 (3,7) 1.802776e+002
