公园内道路设计建模论文

《公园内道路设计建模论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、B题公园内道路设计一摘要随着社会经济的发展，人们生活水平的提高，人们对最优化的要求越来越高，对于公园道路的设计问题也要考虑到很多。本文就针对所给的路线，要求设计最佳路线的问题展开研究，运用Floyd算法，运筹学最优化原理，动态规划，图论对各问题进行求解。对于问题一，先在公园任意门作为入口，分别以其他7个门作为出口，运用穷举法求得出入口两地点间且要经过公园内的道路交叉点的最短距离。模型一建立TSP问题图论模型，找到增广完全图作为精确最优解，并由此求得最短路程为。对于问题二，采用Floyd算法计算出任意两个点之间的最短距离，再根据欧拉回路原理，以及动态规

2、划原理，运用matlab软件运行处相应的图，求得符合条件的最短路径，提高了运算的效率和科学性。对于问题三，要求在问题二的基础上进行改进，方法与问题二的解决方法类似，最后再依据运筹学中的动态规划原理，运用欧几里得方法，在公园内道路不通过湖的条件下，设计出最短路径。最后本文还结合实际情况，对模型的优缺点进行了分析与评价，并提出了改进方向。关键字：动态规划Floyd算法图论最优化原理逆推法欧几里得算法30二问题重述1.问题背景随着经济的发展和人民生活水平的提高，公园的道路设计以及美化越来越重要。对设计师而言，设计出最经济美观的道路已经成为必不可少的本领。而

3、对大学而言，设计出最合理的道路已经成为彰显大学文化气息和人文精神的一点。基于上述情况，根据题目所给数据，运用数学建模方法，对公园道路进行设计。制定出合理的路线，使得公园内道路路径总和最小，获得最优化的解决办法，具有重大的实际意义。2.实际现状对最短路径总和的制定有以下几个特点：1）大学本身要考虑公园道路美观问题；2）大学本身要考虑经济问题；……3.问题提出从一个大学建设公园的实际情况和上述特点出发，依据相关数据：1.假定公园内确定要使用4个道路交叉点为：A(50,75),B(40,40),C(120,40),D(115,70)。问如何设计道路可使公园

4、内道路总路程最短。2.现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出交叉点的坐标，画出道理设计，计算出新修路的总路程。303.若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边。并且重复完成问题二的任务。三、符号说明Sk：状态变量Pi入口点fn():函数名S=u:第u阶段Vi：某个顶点Vij:从i到j的路径G表示某个区域O(nlogn+k^2)时间O(n+k^2)空间四问题分析本题是西安某大学计划为建一个公园，而需要建立一个数学模型去设计道路，不仅让任意两个路口相连，而且使得公园内道路路线总和最短。从

5、题目中我们可以看出，这是一个应用数学知识解决实际问题的例子，是用数学模型求最优化问题。第一问要求过给定的4个交叉点A(50,75)，B(40,40)，C(120,40)，D(115,70），建立模型来使得道路总和最短。我们采用逆推法和动态规划相结合的方法来解决问题，计算出最短路程。第二问没有给定的道路交叉点，自由度较高，我们首先采用Floyd算法求解出任意两点间的最短距离，再根据欧拉回路的方法求出路径总和最短的设计路线，确定出符合条件的道路交叉点，画出最优的道路设计方案。第三问：30有一块比较重要的就是学校公园道路的设计，难点之一就是有障碍物地点之间

6、的最短路径问题。这个问题不是一个新问题，很久以前就有人提出并解决了这个问题。在历史上这个问题是计算几何学中的一个经典课题。被称为具有障碍物的欧几里德最短路径问题(ESP0)。第三问的解决办法是在第二问的基础上拓展得到的，只是要避免我们所设计的公园内的道路通过湖，所以我们是在第二问设计的路线上稍作改进，去掉了其中通过湖的不符合条件的相关路线，根据最优化和运筹学中的动态规划原理，运用欧几里得最短路径问题(ESPO)的解法，可解第三问。以上三问中所提到的解决方案，都是符合条件的，公园内道路路径总和最短，任意两点相连，且任意两点间的连线不超过两点间最短路径的

7、1.4倍（我们这里用椭圆的知识加以检验）。五模型假设1.假设公园内道路零宽度，不影响交叉点坐标，不受自然因素影响；2.假设交叉点宽度不影响道路长度；3.假设公园内道路平整；4.假设公园草坪完整，不受人为因素影响；……六模型建立与求解问题一该问题给出了某公园的八个入口和要设定的四个交叉点，现在需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。30通过分析题目要求，我们发现该问题就是两点

8、间的最短距离问题，这与动态规划原理的联系最为密切，于是我们考虑选取八个入口点中的任意两个点，将其抽象为两点间