建模论文__公园内道路设计.doc

参赛队编号：Xjd2012181B题 公园内道路设计一 摘要随着社会经济的发展，人们生活水平的提高，人们对最优化的要求越来越高，对于公园道路的设计问题也要考虑到很多。本文就针对所给的路线，要求设计最佳路线的问题展开研究，运用Floyd算法，运筹学最优化原理，动态规划，图论对各问题进行求解。对于问题一，先在公园任意门作为入口，分别以其他7个门作为出口，运用穷举法求得出入口两地点间且要经过公园内的道路交叉点的最短距离。模型一建立TSP问题图论模型，找到增广完全图作为精确最优解，并由此求得最短路程为。对于问题二，采用Floyd算法计算出任意两个点之间的最短距离，再根据欧拉回路原理，以及动态规划原理，运用matlab软件运行处相应的图，求得符合条件的最短路径，提高了运算的效率和科学性。对于问题三，要求在问题二的基础上进行改进，方法与问题二的解决方法类似，最后再依据运筹学中的动态规划原理，运用欧几里得方法，在公园内道路不通过湖的条件下，设计出最短路径。最后本文还结合实际情况，对模型的优缺点进行了分析与评价，并提出了改进方向。 关键字： 动态规划 Floyd算法 图论 最优化原理 逆推法 欧几里得算法二 问题重述1.问题背景随着经济的发展和人民生活水平的提高，公园的道路设计以及美化越来越重要。对设计师而言，设计出最经济美观的道路已经成为必不可少的本领。而对大学而言，设计出最合理的道路已经成为彰显大学文化气息和人文精神的一点。基于上述情况，根据题目所给数据，运用数学建模方法，对公园道路进行设计。制定出合理的路线，使得公园内道路路径总和最小，获得最优化的解决办法，具有重大的实际意义。2.实际现状对最短路径总和的制定有以下几个特点：1）大学本身要考虑公园道路美观问题；2）大学本身要考虑经济问题；3.问题提出从一个大学建设公园的实际情况和上述特点出发，依据相关数据：1.假定公园内确定要使用4个道路交叉点为：A(50,75),B(40,40),C(120,40),D(115,70)。问如何设计道路可使公园内道路总路程最短。2.现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出交叉点的坐标，画出道理设计，计算出新修路的总路程。3.若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边。并且重复完成问题二的任务。三、符号说明Sk：状态变量 Pi入口点fn():函数名 S=u:第u阶段 Vi：某个顶点 Vij:从i到j的路径G表示某个区域 O(nlogn+k2)时间 O(n+k2)空间四 问题分析本题是西安某大学计划为建一个公园，而需要建立一个数学模型去设计道路，不仅让任意两个路口相连，而且使得公园内道路路线总和最短。从题目中我们可以看出，这是一个应用数学知识解决实际问题的例子，是用数学模型求最优化问题。第一问要求过给定的4个交叉点A(50,75)，B(40,40)，C(120,40)，D(115,70），建立模型来使得道路总和最短。我们采用逆推法和动态规划相结合的方法来解决问题，计算出最短路程。第二问没有给定的道路交叉点，自由度较高，我们首先采用Floyd算法求解出任意两点间的最短距离，再根据欧拉回路的方法求出路径总和最短的设计路线，确定出符合条件的道路交叉点，画出最优的道路设计方案。第三问：有一块比较重要的就是学校公园道路的设计，难点之一就是有障碍物地点之间的最短路径问题。这个问题不是一个新问题，很久以前就有人提出并解决了这个问题。在历史上这个问题是计算几何学中的一个经典课题。被称为具有障碍物的欧几里德最短路径问题(ESP0)。第三问的解决办法是在第二问的基础上拓展得到的，只是要避免我们所设计的公园内的道路通过湖，所以我们是在第二问设计的路线上稍作改进，去掉了其中通过湖的不符合条件的相关路线，根据最优化和运筹学中的动态规划原理，运用欧几里得最短路径问题(ESPO)的解法，可解第三问。以上三问中所提到的解决方案，都是符合条件的，公园内道路路径总和最短，任意两点相连，且任意两点间的连线不超过两点间最短路径的1.4倍（我们这里用椭圆的知识加以检验）。五 模型假设1.假设公园内道路零宽度，不影响交叉点坐标，不受自然因素影响；2.假设交叉点宽度不影响道路长度；3.假设公园内道路平整；4. 假设公园草坪完整，不受人为因素影响；六 模型建立与求解问题一 该问题给出了某公园的八个入口和要设定的四个交叉点，现在需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。 通过分析题目要求，我们发现该问题就是两点间的最短距离问题，这与动态规划原理的联系最为密切，于是我们考虑选取八个入口点中的任意两个点，将其抽象为两点间的最短距离，完全动态规划最优化原理，我们根据此原理以及图论来建立此问题的数学模型。我们先引入动态规划原理的应用方法： 动态规划方法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下：1.把问题划分为几个阶段。2.按阶段顺序首先考虑最后阶段如第四阶段的最优决策，也就是走哪条路线最短。 3.按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段上各初始点的最优决策即可。用动态规划方法逐段求解时，每个阶段上的求优方法基本相同，而且比较简单，每一阶段的计算都要利用上一阶段的计算结果，因而减少了很多计算量。阶段数愈多，这种效果愈明显。 根据动态规划最短路径这一原理，我们准备用决策法的逆推法，就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路径，最后求得由始点到终点的最短路线，即动态规划的方法是从终点逐段向始点方向寻求最短路线的一种方法。按照东规划的方法，将此过程划分为3个阶段，即变量k=1，2；取过程在各阶段所处的位置状态为状态变量Sk，按逆序算法求解。 假设选取P1作为入口点，其他作为出口点都经过至少一个交叉点 当k=2时： 由结点A到达出口有 f2(S2=A）=min47.2，29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D到达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min44.7=44.7 （选择B点）不经过交叉点 f0=min32,30=30 (选择P2）假设选取P2作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min47.2，29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7= 44.7 （选择P1） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D到达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min44.7=44.7 （选择B点）不经过交叉点 f0=min110,30=30 (选择P1）假设选取P3作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min47.2，29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min80.6=80.6 （选择P3） 由结点D到达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min56.6=56.6 （选择C点）不经过交叉点 f0=min64,110=30 (选择P4）假设选取P4作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min47.2，29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D到达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min56.6=56.6 （选择C点）不经过交叉点 f0=min64,94.3=64 (选择P3）假设选取P5作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min47.2，29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D到达出口有 f2(S2=D）=min88.6，87.3=30.4 （选择P6） 当k=1时： f1（S1=B）=min30.4=31.4 （选择D点）不经过交叉点 f0=min85，94.3=85 (选择P6）假设选取P6作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min29.2=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min29.2=29.2 （选择A点）不经过交叉点 f0=min25，85=25 (选择P7）假设选取P7作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min29.2，67.3=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min47.2=47.2 （选择A点）不经过交叉点 f0=min25，75.7=25 (选择P6）假设选取P8作为入口点，其他作为出口点都经过至少一个交叉点 由结点A到达出口有 f2(S2=A）=min29.2，67.3=29.2 （选择P6） 由结点B到达出口有 f2(S2=B）=min44.7，41=41 （选择P2） 由结点C到达出口有 f2(S2=C）=min56.6，80.6=56.6 （选择P3） 由结点D达出口有 f2(S2=D）=min30.4，87.3=30.4 （选择P5） 当k=1时： f1（S1=B）=min41.2=41.2 （选择B点）不经过交叉点 f0=min32，75.7=32 (选择P1）最后答案如图所示即为最短的道路设计方法。最短路径为804.6.问题二 题目要求公园内可以任意修建道路，使得在满足条件下总路程最少。建立模型并给出算法。给出交叉点的坐标，画出道路设计，计算出新修路的总路程。 分析题目可知，问题二没有给出确定的交叉点，也就是说公园内道路的交叉点可以在任意位置。据此，我们在该模型中用Floyed算法求出两点间最短距离的基础上，利用图论模型，找出欧拉回路作为整体最优解，再通过加入临近点和去边的方式优化该模型，并将由此得到的欧拉回路作为最优化路线。定义1.Floyd算法算法的数据结构Floyd算法采用图的带权邻接矩阵存储结构。算法基本思想假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。算法具体描述若从Vi到Vj有弧，则从Vi到Vj存在一条长度为弧上权（arcsij ）的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑从Vi到Vj经过中间顶点V0的路径（Vi，V0，Vj）是否存在，也就是判断弧（Vi，V0）和（V0，Vj）是否存在。若存在，则比较（Vi，Vj）和（Vi，V0，Vj）的路径长度取较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。 在此路径上再增加一个顶点V1，也就是说，如果（Vi，V1）和（V1，Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么，（Vi，V1，Vj）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短路径相比较，从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短路径。 然后，再增加一个顶点V2继续进行这个试探过程。一般情况下，若（Vi，Vk）和（Vk，Vj）分别是从Vi到Vk和从Vk到Vj的中间顶点序号不大于k-1的最短路径，则将（Vi，Vk，Vj）和已经得到的从Vi到Vj的中间顶点序号不大于k-1的最短路径相比较，其长度最短者即为从Vi到Vj的中间顶点序号不大于k的最短路径。 经过n次比较之后，最后求得的便是从Vi到Vj的最短路径。按此方法可同时求得各对顶点之间的最短路径。 现定义一个n阶方阵序列D（-1），D（0），D（1），D（k），D（n-1）其中 D（-1）ij=arcsijD（k）ij=Min D（k-1）ij, D（k-1）ik+D（k-1）kj 0kn-1 上述公式中，D（1）ij是从 Vi到Vj的中间顶点序号不大于 k的最短路径长度；D（n-1）ij是从Vi到Vj的最短路径长度。2.欧拉回路 图 G 的一个回路,若它通过 G 中每条边一次且仅一次,则称为欧拉回路。而具有这种回路的图称为欧拉图(简称 E 图).或者：一副图，寻找一条只通过每条边一次的路径叫做欧拉路径如果这条路径的起点和终点是同一点，那么这条路径叫做欧拉回路 有关的问题即是欧拉回路问题，建议参考哥尼斯堡七桥问题或一笔画问题。欧拉回路的判定规则：1. 如果通奇数桥的地方多于两个，则不存在欧拉回路；2. 如果只有两个地方通奇数桥，可以从这两个地方之一出发，找到欧拉回路；3. 如果没有一个地方是通奇数桥的，则无论从哪里出发，都能拉回路。4.模型求解1）根据给出的各点位置坐标及互相到达信息，用MATLAB编程求解各 点之间的距离，用Floyd算法得到任意两点间的最短距离（Floyd算法源程序见附件1）上述解法中的Floyd算法用于求任意两点间的最短距离，其程序流程如下：（注：D(i，j)i到j的距离；R(i，j)i到j的插入点。）i 输入：带权邻接矩阵w（i，j）；ii 赋初值：对所有i，j，d（i，j）=w（i，j），r（i，j）=j，k=1；iii 更新d（i，j），r（i，j）：对i，j，若d（i，k）+ d（k，j） R+（即是权值为正） ，在点集V中的固定顶点s，寻找s到V中各顶点v的最短路径.Dijkstra算法:Dijkstra算法是一种解决最短路径问题的非常有效的算法，时间复杂度为 O(|V|2)：1.Set i=0, S0= u0=s, L(u0)=0, and L(v)=infinity for v u0. If |V| = 1 then stop, otherwise go to step 2. 2.For each v in VSi, replace L(v) by minL(v), L(ui)+dvui. If L(v) is replaced, put a label (L(v), ui) on v. 3.Find a vertex v which minimizes L(v): v in VSi, say ui+1. 4.Let Si+1 = Si cup ui+1. 5.Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 6.Set i=0, S0= u0=s, L(u0)=0, and L(v)=infinity for v u0. If |V| = 1 then stop, otherwise go to step 2. 对于该问题还有一些更好的算法，下面作一些简单的介绍：利用最短路径映射 SPM(s,)在O(n(k+logn)时间内求解任意多边形障碍物的ESPO问题的方法是由Reif和Storer提出的。如果给定SPM(s,)，则在O(logn)时间内可以确定包含t的 域，而在0(b+logn)时间内能够确定到t的路径，其中b是路径上线段的数目。Welzl等人利用可视图给出了求解平面上n条线段的ESPO问题的算法，该算法要求 0(n2)时间。不难修改这个算法使其能处理多边形障碍物，并且具有相同的时间复杂性。注意，如果使用可视图方法，那么对限界0(n2)将不可能改进。多边形物体中两个物体(而非点)之间的最短路径的0(n2)算法是已知的。当n是平行线段集合时，Lee和Preparata提出(nlogn)平面扫描算法。线段穿过扫描线并且把最短路径映射到扫描线。平面上没有最短路径的0(n2)算法能处理避开n条任意相交的线段。 Rohnert给出平面中避开k个凸障碍物最短路径的O(nlogn+k2)时间的算法。这个时间限界在O(k2logn+n)时间和O(n+k2)空间预处理障碍物的条件下达到。预处理包括构造可视图的子图。Rohnert还给出平面中避开k个凸障碍物最短路径的O(knlogn)时间和O(n)空间的算法。后者不需预先处理障碍物，而是利用Dijkstra最短路径算法在线计算可视性。当平面中有k个凸障碍物并且其边界至多相交两次时，Rohnert给出的算法能找到平面中任意两点之间的最短路径，其时间复杂性为O(nlogn+k2)。这个时间限界在O(nlogn+k3)时间和O(n+k2)空间预处理障碍物的条件下达到。(Dijkstra算法见附录三）如图所示即为最短的道路设计方法。最短路径为894.7.七 模型的评价与推广7.1模型的评价本题主要运用Floyd算法，穷举法，欧拉回路和运筹学中的最优化的相关知识建立数学模型，进而求出公园内道路总和与交叉点的函数关系，并充分的结合题目所给的条件，应用MATLAB软件，提高了计算效率和结果的科学性。模型建立时忽略了题目所未给出的人为因素和自然因素对公园内道路总和的影响，在实际中时建议考虑人为因素和自然因素对所设计的道路结果的影响。7.2 模型的推广本题所建立的数学模型虽然解决的是某大学校园公园内道路总和设计的问题，但可以推广到各种城市规划和园林建设等实际问题，这些问题都可以用该模型来解决。解决该问题时，我们查阅了有关数学建模和运筹学最优化的相关书籍，该模型中所提到的Floyd算法，欧拉回路和动态规划的相关方法均可以直接使用，利用这些方法可以快速方便地解决诸如求最短路径等一些城市规划与园林建设中的实际问题。解决该问题时所用到的数学思想和数学方法，对于解决实际的社会问题也同样具有广泛的教育意义和社会效益。八 参考文献【1】MATLAB程序设计及应用许丽佳 穆炯 清华大学出版社2011【2】最优化理论与方法傅英定 成孝予 唐应辉 国防工业出版社2005【3】优化技术与MATLAB工具箱赵继俊 机械工业出版社 2011【4】最优化方法MATLAB应用黄雍检 陶冶 钱祖平 人民邮电出版社 2010【5】运筹学（数学规划篇）吕蓬 潘志 清华大学出版社北京交通大学出版社 附录/*/* Dijkstra.java */* Copyright (C) 1997, 1998, 2000 K. Ikeda */*/import java.applet.*;import java.awt.*;import java.awt.event.*;import java.util.*;import java.io.*;import .URL;class Node intx;inty;intdelta_plus;/* edge starts from this node */intdelta_minus;/* edge terminates at this node */intdist;/* distance from the start node */intprev;/* previous node of the shortest path */intsucc,pred;/* node in Sbar with finite dist. */intw;inth;intpw;intdx;intdy;Stringname;class Edge intrndd_plus;/* initial vertex of this edge */intrndd_minus;/* terminal vertex of this edge */intdelta_plus;/* edge starts from rndd_plus */intdelta_minus;/* edge terminates at rndd_minus */intlen;/* length */Stringname;public class Dijkstra extends Applet implements MouseListener intn,m;intu,snode;/* start node */intpre_s_first, pre_s_last;booleanisdigraph;intiteration, step;Nodev = new Node100;Edgee = new Edge200;int findNode(String name) for (int i=0; in; i+)if (.equals(name)return i;return -1;void input_graph(InputStream is) throws IOException int x,y,l;Strings;Reader r = new BufferedReader(new InputStreamReader(is);StreamTokenizer st = new StreamTokenizer(r);mentChar(#);st.nextToken();n = (int)st.nval;st.nextToken();m = (int)st.nval;st.nextToken();s = st.sval;isdigraph = digraph.equals(s);for (int i = 0; in; i+) Node node = new Node();st.nextToken(); = st.sval;st.nextToken();node.x = (int)st.nval;st.nextToken();node.y = (int)st.nval;vi = node;switch (st.nextToken() case StreamTokenizer.TT_NUMBER:edge.rndd_minus = (int)st.nval;break;case StreamTokenizer.TT_WORD:edge.rndd_minus = findNode(st.sval);break;default:break;st.nextToken();edge.len = (int)st.nval;ei = edge;for (int i=0; i= 0)k = ek.delta_minus;ek.delta_minus = i; void append_pre_s(int i) vi.succ = vi.pred = -1;if (pre_s_first=0) i = ej.rndd_minus;if (vi.succ=-2)&(vi.distvu.dist+ej.len) if (vi.dist=0) i = ej.rndd_plus;if (vi.succ=-2)&(vi.distvu.dist+ej.len) if (vi.dist=0; i = vi.succ) if (rho vi.dist) rho = vi.dist;u = i;remove_pre_s(u);vu.succ = -3;void step4() vu.succ = -4;double weight(Node n, double x, double y) doublew,z,xx,yy;w = 0;for (int j = n.delta_plus; j=0; j=ej.delta_plus) xx = (double)(vej.rndd_minus.x - n.x);yy = (double)(vej.rndd_minus.y - n.y);z = (x*xx+y*yy)/Math.sqrt(x*x+y*y)*(xx*xx+yy*yy)+1.0;w += z*z*z*z;for (int j = n.delta_minus; j=0; j=ej.delta_minus) xx = (double)(vej.rndd_plus.x - n.x);yy = (double)(vej.rndd_plus.y - n.y);z = (x*xx+y*yy)/Math.sqrt(x*x+y*y)*(xx*xx+yy*yy)+1.0;w += z*z*z*z;return w;void init_sub() int x = 1, 0, -1, 1, 0, -1;int y = 1, 1, 1, -1, -1, -1;int i,j,k;doublew,z;for (i=0; in; i+) k=0;w=weight(vi,(double)x0,(double)y0);for (j=1; j6; j+) z=weight(vi,(double)xj,(double)yj);if (zw) w = z;k = j;vi.dx = xk;vi.dy = yk;public void init() String mdname = getParameter(inputfile);try InputStream is;is = new URL(getDocumentBase(),mdname).openStream();input_graph(is);try if (is != null)is.close(); catch(Exception e) catch (FileNotFoundException e) System.err.println(File not found.); catch (IOException e) System.err.println(Cannot access file.);String s = getParameter(start);if (s != null)snode = Integer.parseInt(s);elsesnode = 0;setBackground(Color.white);rdb();init_sub();addMouseListener(this);public void paintNode(Graphics g, Node n, FontMetrics fm) String s;int x = n.x;int y = n.y;int w = fm.stringWidth() + 10;int h = fm.getHeight() + 4;n.w = w;n.h = h;if (n.succ-2)g.setColor(Color.yellow);elseg.setColor(getBackground();g.fillRect(x-w/2+1,y-h/2+1,w-1,h-1);g.setColor(Color.black);g.drawString(,x-(w-10)/2,(y-(h-4)/2)+fm.getAscent();if (n.dist0)s = ;elses = +n.dist;w = fm.stringWidth(s) + 10;x += (h+1)*n.dx; y += (h+1)*n.dy;g.setColor(getBackground();g.fillRect(x-n.pw/2,y-h/2,n.pw,h);n.pw = w;if (n.succ=Math.abs(h*a) x0 = (b=0)?1:-1)*a*h/b/2;x1 = (b=0)?1:-1)*h/2; else x0 = (a=0)?1:-1)*w/2;x1 = (a=0)?1:-1)*b*w/a/2;return x;void drawArrow(Graphics g,int x1,int y1,int x2,int y2) inta = x1-x2;intb = y1-y2;if (isdigraph) doubleaa = Math.sqrt(a*a+b*b)/16.0;doublebb = b/aa;aa = a/aa;g.