第一组公园内道路设计论文.pdf

1 武汉理工大学华夏学院武汉理工大学华夏学院 20122012 年暑期数学建模训练论文年暑期数学建模训练论文 题目题目 公园内道路设计问题公园内道路设计问题 参赛队员参赛队员 1 姜媛姜媛 制药制药 11011101 2 2 王芳王芳 营销营销 1101 1101 3 3 吴双吴双 营销营销 11011101 4 4 郑宇郑宇 自动化自动化 1102 1102 5 5 蒋天齐蒋天齐 自动化自动化 1101 1101 2012 年年 7 月月 21 日日 2 公园内道路设计问题公园内道路设计问题 摘要 本文研究的是最短路线设计问题 通过道路设计来探求如何使得新修路总路程最 小 通过检验与分析得出适合的方案解决该问题 之后结合实际情况对上述模型进行科 学误差分析 并分析所用算法的复杂性与实用性 对于问题一 题目中给出了公园内确定 4 个固定道路交叉点为 A 50 75 B 40 40 C 120 40 D 115 70 要求我们为公园设计最短的通行路线 即从任意一点出发 经过每个拐点之 和的路径最短 可以将问题转化成最小生成树问题 运用 kruskal 算法或波莱姆 Prim 算法求解此问题 对按照符合的条件 可以考虑以任意两点之间的最短距离为最短路 径模式 利用 Matlab 软件编程得出所有点之间的相互距离所组成的矩阵 在满足任意 两个入口之间的最短路长不大于两点连线的 1 4 倍的条件下 运用 Dijkstra 算法的思想 通过从一点开始依次选取距离最短的点 将会得到一条路径 同时应用题目中的要求 进行模型修改与确定 从而得到最优解 即最短的路径路线 这样就会为这个公园设计 出最短的路径线路 对于问题二 本问题的目标是在公园内拐点不限制不确定的条件下 设计最短路径的方案 由第 一问思想启示 要引入虚拟点 即交叉点 为了满足任意的两个入口之间的最短道路长 不大于两点连线的 1 4 倍这一约束条件 联想到椭圆性质 椭圆上任意一点到两焦点 的距离为定值 用椭圆来确定交叉点所在区域 然后根据费马点定理来确定交叉点 的位置 从而得到最短的路径 D 对于问题三 由题意知此题仍为最短路问题 现在在公园内加一条矩形的湖 新修的道路不能通 过 但可到达湖四周的边 根据模型二所求出的模型进行为基础 我们可以考虑设定原 则 仍然以最短路径为原则 重复问题二的建模过程 运用费马点定理 从而得出最 优点 设计出最优方案 之后结合实际情况对上述模型进行科学误差分析 并分析所用算法的复杂性与实用 性 同时对上述解决最短路问题所采用的算法进行评价 使公园建设者的问题有更深一 步的理解 关键词 关键词 公园内道路设计 最小树 DijkstraDijkstra 算法算法 kruskal 算法算法 费马点费马点 matlab 软件软件 3 问题重述 现在西安某大学计划要建一个矩形或其他不规则图形公园 为美化校园环境 同时 为学生提供更加舒适温馨的生活条件 公园计划有若干个入口 现在需建立一个模型去 设计道路路径 需要按下面要求制定可行方案 1 使任意两个入口相连 使总的道路长度和最小 前提要求是任意两个入 口之间的最短路长不大于两点连线的 1 4 倍 2 要求公园内新修的道路与四周的连接只能与 8 个路口相通 而不能连到 四周的其他地方 3 可以利用公园四周的边 即默认矩形的四条边上存在已经建好的道路 此道路不计入道路总长 4 画出道路设计 计算新修路的总路程 5 对算法作复杂性 可行性分析 6 关于最短路径问题提出对所采用的算法的理解及评价 7 主要设计对象可假设为如图所示的矩形公园 其相关数据为 长 200 米 宽 100 米 1 至 8 各入口的坐标分别为 1 v 20 0 2 v 50 0 3 v 160 0 4 v 200 50 5 v 120 100 6 v 35 100 7 v 10 100 8 v 0 25 示意图见图 1 问题一 假定公园内确定要使用4个道路交叉点为 A 50 75 B 40 40 C 120 40 D 115 70 如何设计道路可使公园内道路的总路程最短 建立模型并给出算法 画出道 路设计 计算新修路的总路程 问题二 现在公园内道路可任意修建 如何在满足条件下使总路程最少 建立模型 并给出算法 给出道路交叉点的坐标 画出道路设计 计算新修路的总路程 问题三 若公园内有一条矩形的湖 新修的道路不能通过 但可到达湖四周的边 示意图见图3 重复完成问题二 的任务 其中矩形的湖为R1 140 70 R2 140 45 R3 165 45 R4 165 70 4 图图 1 1 公园及入口示意公园及入口示意 图图 2 一种可能的道路设计图一种可能的道路设计图 5 图图 3 有湖的示意图有湖的示意图 问题分析 问题一 题目中给出了公园内确定 4 个固定道路交叉点为 A 50 75 B 40 40 C 120 40 D 115 70 要求为公园设计最短的通行路线 即从任意一点出发 经过每个拐点之和最 短 可以考虑运用 kruskal 算法求解此问题 按照符合的条件 可以考虑以任意两点之 间的最短距离为最短路径模式 利用 Matlab 软件编程得出所有点之间的相互距离所组 成的距阵 在满足任意两个入口之间的最短路长不大于两点连线的 1 4 倍的条件下 运 用 Dijkstra 算法的思想 通过从一点开始依次选取距离最短的点 将会得到一条路径 同时应用题目中的要求 进行模型修改与确定 从而得到最优解 即最短的路径路线 这样就会为这个公园设计出最短的路径线路 问题二 本问题的目标是在公园内拐点不限制不确定的条件下 设计最短路径的方案 首先 根据 1 4 倍的约束条件联想到利用椭圆来进一步缩小取点范围 第一步以任意两点为焦 点 以 1 4 倍的焦距长轴长做椭圆 筛选有效覆盖面积的椭圆 得到覆盖程度不同的区 域 第二步将覆盖程度视为符合要求的点落入的概率 得出最大覆盖区域的范围 然后 再利用费马点定理确定最优点 从而得到最优解 即最短的路径路线 问题三 由题意知此题仍为最短路问题 现在在公园内加一条矩形的湖 新修的道路不能通 过 但可到达湖四周的边 根据模型二所求出的模型进行为基础 我们可以考虑设定原 则 仍然以最短路径为原则 重复问题二的建模过程 运用费马点定理 从而得出最 优点 设计出最优方案 6 模型假设 假设一 根据距离模型可知距离与入口大小无关 所以可将各入口可视为点 把路 视为直线 假设二 除题目外 道路规划可以任意进行 而不需要考虑其他客观因素 假设三 公园内新修的道路与四周的连接只能与 8 个路口相通 而不能连到四周的 其它点 假设四 矩形湖的周边没有建好的道路 符号说明 首先将 A B C D 四个点分别定义为第 9 点 第 10 点 第 11 点 第 12 点 如下图 i v 第 i 个点的坐标 i j L i j 两点间直线的距离 i j S i j 两点间最短路程 i D 总路程的长度 7 模型建立 5 15 1最小生成树最小生成树引入引入 为了美化校园环境 为其学生提供更方便的生活条件 公园计划有若干个入口 现 在我们需要建立一个模型去设计道路让任意两个入口相连 可以利用公园四周的边 即 默认矩形的四条边上存在已经建好的道路 此道路不计入道路总长 使总的道路长度 和最小 由此问题可以转化成最小生成树问题 定义 任意两点均有通路的图称为连通图 定义 连通而无圈的图称为树 常用T表示树 由树的定义不难知道 任意一个连 通的p q图 p个顶点q条边 G适当去掉q p 1 条边后 都可以变成树 这棵树称 为图G的生成树 设T是图G的一棵生成树 用F T 表示树T中所有边的权数之和 F T 称为树T的权 定义 一个连通图G的生成树一般不止一棵 图G的所有生成树中权数最小的生成 树称为图G的最小生成树 5 25 2 最小生成树算法及最小生成树算法及 Dijkstra 算法算法介绍介绍 首先来看在欧几里德空间最小生成树的算法 两个最常用的算法为克罗斯克尔 Kruskal 算法和波莱姆 Prim 算法 在克罗斯克尔算法中 最初将 个节点看作 个不同的只含有单节点的部分树 算法每进行一步 通过图的一条边把两个不同的部分 树连接成一个部分树 在经过这样 步后 只有一个部分树 它就是最小生成树 究竟连接那两个部分树 是由两个不同部分树的距离来决定的 最小生成树的波莱姆算 法是从任意一个节点开始连接与该节点最近的节点 后续要加上的节点是距前已形成树 最近的节点 直至所有的节点都加入为止 其实不管是罗斯克尔 Kruskal 算法还是波 莱姆 Prim 算法 其实质都是 Dijkstra 算法的运用 即某一点到任意其它点间的最短 路 对最短路问题的研究早在上个世纪 60 年代以前就卓有成效了 其中对赋权图 0 ij w 的有效算法是由荷兰著名计算机专家 E W Dijkstra 在 1959 年首次提出的 该算法 能够解决两指定点间的最短路 也可以求解图 G 中一特定点到其它各顶点的最短路 后 来海斯在 Dijkstra 算法的基础之上提出了海斯算法 但这两种算法都不能解决含有负权 的图的最短路问题 因此由 Ford 提出了 Ford 算法 它能有效地解决含有负权的最短路问 题 但在现实生活中 我们所遇到的问题大都不含负权 所以我们在 0 ij w 的情况下选择 Dijkstra 算法 定义 1 若图 G G V E 中各边 e 都赋有一个实数 W e 称为边 e 的权 则称这种图为赋 权图 记为 G G V E W 定义 2 若图 G G V E 是赋权图且 0W e eE G 若 u 是 i v到 j v的路 W u的权 则称 W u为u的长 长最小的 i v到 j v的路 W u称为最短路 若要找出从 i v到 n v的通路u 使全长最短 即 min ij eu W uW e 8 5 35 3 费马点定理的介绍费马点定理的介绍 定义 在一个三角形中 到 3 个顶点距离之和最小的点叫做这个三角形的费马点 性质 1 若三角形 ABC 的 3 个内角均小于 120 那么 3 条距离连线正好三等分费马点所 在的周角 所以三角形的费马点也称为三角形的等角中心 2 若三角形有一内角不小于 120 度 则此钝角的顶点就是距离和最小的点 5 45 4 最短路问题的算法基本步骤最短路问题的算法基本步骤 将 个入口点和 个交叉点都当做节点 利用 Matlab 软件编程得出这 个点 之间的相互距离所组成的距阵 利用 Kruskal 算法从一点开始依次选取距离最短的点 将会得到一条路径 同时应用题中要求进行模型修改与确定 从而确定最佳路线并求出 最佳路线的总距离 D 引入虚拟点 即交叉点 为了满足任意的两个入口之间的最短道路长不大于两 点连线的 1 4 倍这一约束条件 联想到椭圆性质 椭圆上任意一点到两焦点的距离为 定值 用椭圆来确定交叉点所在区域 然后根据费马点定理来确定交叉点的位置 以使道路总长 最短 利用 Matlab 软件编程得出这 个点之间的相互距离所组成的 距阵 模型求解 第一问 第一问 步骤一 步骤一 利用利用 MatlabMatlab 软件编程得出这 个软件编程得出这 个点之间的相互距离点之间的相互距离 i j L所组成的距阵所组成的距阵图 图 为了使总的道路长度和最小 公园四周道路不计入道路总长 并且任意的两入口 点之间的最短道路长不大于 1 4 倍 先对各入口点进行分析 同一水平线上入口点之间 可以不予考虑 然后开始验证其他任意两个入口之间的最短道路长 发现有 1 v 到 5 v 6 v 8 v 2 v 到 5 v 6 v 7 v 3 v 到 4 v 5 v 6 v 7 v不满足要求 并且 1 v与 8 v直接连接 3 v与 4 v直接连接 4 v 8 v可 以不予考虑 9 然后 利用 Dijkstra 算法思维来确定最小生成树 根据上表数据确定 1 v到 7 v的部分 树为 1 v 2 v 10 v 9 v 6 v 7 v 3 v到 5 v的部分树为 3 v 11 v 12 v 5 v 可得如下图 接下来考虑的问题是 如何将这两部分的树连接成一棵树 即最小生成树 这由 两部分树间距离决定 并依据题意任意的两个入口之间的最短道路长不大于两点连线的 1 4 倍这一条件 找出相对应点来连接这这两部分树 若选 6 v 5 v 2 v 3 v 显然入口点 2 v到 5 v的最短路 2 5 s大于 1 4 倍 2 5 L 故只能在 9 v 10 v中取得 10 由于 9 12 L 9 5 L 9 11 L 10 11 L 10 12 L1 4 2 5 L 选 9 v 5 v 验证得其他任意两入口点间最短道路都满 足不大于两点连线的 1 4 倍这一条件 故最终选 9 v 5 v 综上所述 可以确定最优路径如下图 则需要修建最短道路的总路径为 11 D 1 83 42 1010 99 69 55 1212 1111 3 LLLLLLLLL 394 5596 米 注 可以直接通过 Matlab 软件 运用 Kruskal 算法求最小生成树 6 26 2 第二问第二问 从 1 点开始 将 1 点看作椭圆一个焦点 分别以 2 3 4 5 6 7 8 为椭圆另一个焦点 以 1 4 倍的焦距长为长轴画椭圆 同理再依次以其他点为定点焦点 画出椭圆 则总共 可画 28 个 再通过对 8 个入口坐标的分析 剔除掉那些可以通过走公园外边的点 以 及在同一边上的两点 这些点构成的椭圆可以略去 不计必入考虑范围 即从众多椭圆 中筛选出有效覆盖面积的椭圆 得到覆盖程度不同的区域 以此来确定交叉点所在范围 及位置 从图中通过对比分析重叠区域最密集的部分 则确定可能有两个或三个交叉点 如 图所示 12 然后根据费马点定理来确定交叉点位置 根据总道路长最短来确定最优交叉点的个 数 由 1 v 5 v 6 v三个顶点来确定一个交叉点 9 v 48 2063 85 1646 由 2 v 5 v 6 v三个顶点来确定一个交叉点 10 v 62 3370 77 8649 由 3 v 4 v 5 v三个顶点来确定一个交叉点 11 v 173 0980 43 6433 由 9 v 5 v 11 v三个顶点来确定一个交叉点 12 v 120 100 13 由 10 v 5 v 11 v三个顶点来确定一个交叉点 13 v 118 774 94 8113 经过计算分析可得两种优化方案 模型一和模型二 14 模型一 加入 9 v 11 v两个交叉点 构成的最优路径的最短路径如下所示 交叉点坐标为 9 v 48 2063 85 1646 11 v 173 0980 43 6433 最短道路总长 11 81 99 69 55 1111 411 3 DLLLLLLL 365 5417 米 模型二 加入 10 v 11 v 13 v三个交叉点 构成的最优路径的最短路径如下所示 1 82 106 1010 135 1313 1414 1111 411 3 LLLLLLLLL 交叉点坐标为 10 v 62 3370 77 8649 11 v 173 0980 43 6433 13 v 118 774 94 8113 最短道路总长 21 82 1010 610 1313 1111 411 35 13 DLLLLLLLL 358 1163 米 15 6 36 3 第三问第三问 在第二问得到的最优解的情况下 考虑湖所在的位置 得到下图 此时 要将点 11 和点 13 之间的路径进行微调 考虑是选择经过 R4 定义 R4 为点 14 还是R2 定义R2为点15 首先利用费马点定理可知14 15都分别为三角形13 14 11 三角形 13 15 11 的费马点 然后算出 13 1414 11 LL 80 0364 13 1515 11 LL 87 2711 故确 定最终路径如下图所示 D 1 82 106 1010 135 1313 1414 1111 411 3 LLLLLLLLL 363 5252 米 16 模型评价与改进 7 1 模型一的优点 根据题目要求 优先考虑矩形边框路线 先对 8 个入口点进行分析 剔除可以不予考虑的点 然后灵活运用 Dijkstra 算法的思想 求最 小生成树 缺点 计算过程中 不能很好的通过软件实现最小生成树的计算 7 2 模型二的优点 巧妙运用椭圆性质来满足题目任意两个入口之间的最短路长不大于 两点连线的 1 4 倍这一要求 根据椭圆覆盖区域来界定交叉点的范 围区域 然后根据费马点定理来确定交叉点的个数及位置 相对于 整体问题而言 进行局部之间的交替优化可简化问题 缺点 1 由于椭圆是满足一个点到两焦点的距离为常数的点的集合 对于 椭圆内的两个点 有时不能满足 任意两个入口之间的最短路长不 大于两点连线的 1 4 倍 这个条件 存在不严谨性 可能会导致结 果出现较大误差 2 部分优先处理只能无穷逼近全局的最优解 但无法证明我们所得 结果是最优解 7 3 模型三的优点 在模型二的基础上 模型三的建立相对比较简单 思路清晰 缺点 模型三考虑的不够全面 没有考虑到不绕湖边走的情况 参考文献 1 姜启源 谢金星 叶俊 数学模型 第三版 高等教育出版 2009 年重印 2 百度文库 费马点 3 王树禾 图论 第二版 科学出版社 4 百度文库 matlab 绘图 ppt 5 董霖 MATLAB 使用详解 电子工业出版社 2009 版 附录 第一问 n 9 A 0 30 0000 140 0000 141 4214 101 1187 80 7775 44 7214 107 7033 118 0042 30 0000 0 110 0000 122 0656 101 1187 75 0000 41 2311 80 6226 95 5249 140 0000 110 0000 0 107 7033 160 0781 133 1353 126 4911 56 5685 83 2166 141 4214 122 0656 107 7033 0 85 0000 74 3303 100 0000 60 0000 30 4138 101 1187 101 1187 160 0781 85 0000 0 29 1548 60 2080 104 0433 85 4400 80 7775 75 0000 133 1353 74 3303 29 1548 0 36 4005 78 2624 65 1920 44 7214 41 2311 126 4911 100 0000 60 2080 36 4005 0 80 0000 80 7775 107 7033 80 6226 56 5685 60 0000 104 0433