校园文化景观中心道路设计问题.doc

1、 校园文化景观中心道路设计问题摘 要：随着我国社会经济的不断发展，城市规划与建设已成为发展经济、文明进步的重要标志。而在此规划建设中，我们又经常会遇到形形色色的与最短路径有关的实际问题，比如像生产生活，交通运输，环境美化、道路设计等等，而研究诸如此类的问题不仅可以给我们的生活带来实际的方便，而且在很多情况下还可以提高经济效益。就从本题的实际情景出发来看，它研究的是我校逸夫教学楼和信息楼间拟建的校园文化景观中心内部的道路设计问题，而我们所要研究的就是在保证该文化景观中心边缘8个入口两两之间的最短路长不大于这两个入口之间连线的1.4倍的前提条件下，使内部道路总长度最短。首先我们应该明确一点，就所给

2、的两个问题总体而言，都是优化问题，要求修的路程尽量短。这就给了我们一个警示，即，在满足前提1.4倍这一特殊的约束条件之下，能使用的边尽量使用，并且在初定方案之后一定要根据题意仔细斟酌，确保所得道路修建方案在满足约束条件的情况下是最优路线，如果是，则保留，否则就剔除掉这一方案，寻求其他方案。针对问题一，由于该文化景观中心内部的4个交叉点已经给出，所以我们应该考虑的问题只有一个，即满足问题本身的约束条件，来求得使校园文化景观中心内部道路总长度最短。并且在该约束之下，我们还可以发现这是一个定点求最优路径的问题，所以我们考虑使用克鲁斯卡尔算法为主，以弗洛伊德算法相配合的方法来处理这一问题。前一个算法用

3、来生成最小生成树，后一个算法配合题设约束条件来对前边的最小生成树进行判断，以确定出最终的最优方案。最后根据两个算法不断的交替使用，得到最终结果。即在第一个约束条件之下我校园文化景观中心内新修路的最短总长为394.5米。针对问题二，由于题目要求任意的两个入口之间的最短道路长不大于两点连线的1.4倍，并且没有固定交叉点。因此根据此题设我们可以用椭圆的定义来解决此问题。所以第一步我们以任意两点为焦点，以1.4倍焦距为椭圆的长轴长做椭圆，这样画出椭圆后我们会发现大量的椭圆交叉区域,，由椭圆的性质可知满足条件的交叉点必在这些交叉区域内。第二步我们进行筛选，将不必要的椭圆筛选掉，且我们不知道交叉点的个数，

4、所以我们根据题目我们假设交叉点为0个或者两个。第三步，对于剩下的椭圆交叉区域进行优化，对于0个交叉点和两个交叉点分别优化出位置，且做出比较，找出最优的。关键词：克鲁斯卡尔算法 弗洛伊德算法 最小生成树 椭圆 一、问题重述1.1问题背景我校计划在逸夫教学楼与信息楼之间建一个形状为矩形或其他不规则图形的校园文化景观中心，不仅为了美化校园环境，也是想为其学生提供更的生活条件。该中心计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两

5、点连线的1.4倍。主要设计对象可假设为如图所示的矩形校园文化景观中心，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25).该8个入口的示意图如下所示：1.2 问题提出问题一：假定校园文化景观中心内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使校园文化景观中心内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问题二：现在校园

6、文化景观中心内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。注：以上问题中都要求校园文化景观中心内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。二、符号说明 符号意义校园文化景观中心的入口A,B,C,D校园文化景观中心内的四个交点构建模型中代表ABCD即四个交点E，F最后确定的校园文化景观中心内的交点P(x,y)表示各个入口以及道路交点处坐标X（01）矩阵8个入口最短路径矩阵控制矩阵M交叉点的个数i,j代表任意两点代表任一点的横坐标代表任一点的纵坐标i点和j之间的权值S道路总长（不含矩形边长）。三

7、、模型假设假设一：根据距离模型可知距离与入口大小无关，所以在校园文化景观中心内所修建的道路间的交叉点和各个入口不影响道路的总长，并且在实际建模过程中我们将道路假设成线段，道路间的交叉点和各个入口假设为点。假设二：在校园文化景观中心内所修建的道路与周围连接时只能与已给定的8个入口相连通，而不可以连接到四周其他的点。假设三：根据问题的需求是要满足最短距离，所以我们在建模过程中可以假设所有点之间的道路均修建为直线。假设四：假设该校园文化景观中心为矩形，且不考虑道路的宽度，只是一律视为线段即可，而且在满足题设的前提下在校园文化中心内可以任意修建路径。假设五：对于校园文化景观中心的任意两个入口点相连，使

8、总的道路长度和最小，前提要求是任意的两个入口之间的最短路长不大于两点连线的1.4倍。四、问题分析4.1问题一在该问题中已经明确给出了校园文化景观中心内4个固定的道路交叉点的坐标值分别为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。并且还有两个前提约束条件分别为：（1）、在校园文化景观中心内修建道路时必须经过这四个固定的交叉点。（2）、校园文化景观中心的任意两个入口之间的最短道路长不大于两点连线的1.4倍。需要我们为校园文化景观中心设计最短的通行路线，即要求设计出的道路可使校园文化景观中心内道路的总路程最短。4.2问题二 在本问题中与前一问题相比较，虽然没有了校园

9、文化景观中心内道路交叉点数目和位置的限定，但它却是问题一在模型上的一个扩展，并且与问题一相比较分析而言，在此问题中依然存在以下几点约束条件需要注意：（1）、虽然校园文化景观中心内的拐点不确定也不限制，但它依然需要我们求出的总的道路长度和最小。（2）、校园文化景观中心的任意两个入口之间的最短道路长不大于两点连线的1.4倍，这一约束条件任然没有改变。并且由于校园文化景观中心内可以任意修建道路，所以这就要求我们所给出的设计方案一定要遵循最优原则。五、模型建立与求解5.1问题一的回答5.1.1问题一模型的建立综合与问题一所有相关的已知信息，我们可以看出这与最短路问题联系比较密切，所以我们考虑的是使用克

10、鲁斯卡尔算法和弗洛伊德算法来建立问题的模型。由于校园文化景观中心中已确定的四个道路交叉点在这一问题的求解中我们要予以使用，所以在模型的建立过程中，我们为了统一运算时的方便，现将八个入口及四个交叉点依次设为：、。这十二个点在校园文化景观中心中的分布位置如下图所示：本图所依据的坐标系道 路校 园 文 化 景 观 中 心信息楼逸夫教学楼XY0(20,0)(50,0)(160,0) (200,50) (120,100) (35,100) (10,100) (0,25) (50,75) (40,40) (120,40) (115,70)道 路道 路道 路图释：图中的黑点表示八个入口和四个交点的所在位置，

11、P(x,y)表示该点在如图所示坐标系下的具体坐标。根据克鲁斯卡尔算法的要求，我们首先需要建立一个连通网，而该连通网的顶点则是前面所设的到。而该连通网中的边即为其中两点之间的连线，并且这条连线（即相应的边）可以表示实际中道路的长度。由于实际问题的需求所在，所以在所建的连通网中会存在连通分量，即存在环路。所以不能采取直接构造最小生成树的方法来求得最小路径。所以对于直接求解最优解便显得相当复杂，由此我们便根据克鲁斯卡尔算法中所采用的贪婪准则，来引入贪婪算法进行方便求解。如果这样的话，我们在开始时便可以不考虑连通网中存在环路的问题，而是直接构造最小生成树。在构造好最小生成树之后，我们便可以利用弗洛伊德

12、算法来求出任意两点之间的最短路径，并建立起最短路径矩阵，然后进行验证，看是否满足约束条件，即任两入口之间的最短路径不大于其直线距离的1.4倍。如不满足继续寻找，直到找到满足这一约束条件的最短路径矩阵。这时候我们便允许环路的存在，并在此基础之上对前边所得到的结果进行边的删除与替换，使得最终满足任两入口之间的最短路径不大于其直线距离的1.4倍这个约束条件。当确定好这一最优方案之时，我们将所得校园文化景观中心内部需要新修的道路的起始坐标予以给出。然后利用我们编写好的Java代码进行求解，得出最短总路径的长度值。5.1.2问题一模型的求解由该校园文化景观中心的八个入口和其中的四个交叉点所表示的这十二个

13、点可以组成这样的一个点集： P=（、）并且根据题意我们已经获知它们的坐标分别为：(20,0)、(50,0)、(160,0)、(200,50)、(120,100)、(35,100)、(10,100)、(0,25)、(50,75)、(40,40)、(120,40)、(115,70)。在获得以上相关信息之后，我们对于前面所建模型的求解可以按下逐步展开，分层突破，最终获得所需结果。首先：利用MATLAB，算出任意两点之间的距离作为后面的参考数据，以供使用。（所有程序参见附录）。MATLAB中得出的数据如下图所示：其次：根据克鲁斯卡尔算法，再结合MATLAB工具可以求得最小生成树，在这里为了我们便于观察

14、各个点之间的关系，我们根据离散数学中的相关知识将其所得结果转换成为了01矩阵如下： ；注释：在该矩阵之中，0表示对应两点之间没有连线，即：表示实际中这两点之间没有道路相连通；1则表示两点之间有连线，即：表示实际中这两点之间有道路相同。此时，便可以由所得到的相关数据绘制出如下所示的可能方案，参考道路设计图如下所示：校 园 文 化 景 观 中 心信息楼逸夫教学楼XY0(20,0)(50,0)(160,0) (200,50) (120,100) (35,100) (10,100) (0,25) (50,75) (40,40) (120,40) (115,70)道 路道 路道 路再次：使用弗洛伊德算法

15、针对上面无环路存在的参考道路设计图进行检验，以使其达到题设中的约束条件。在使用弗洛伊德算法的时候，先计算出已有条件下8个入口最短路径矩阵如下：并与事先已求得的控制矩阵 作比较， 发现部分入口间最短路径不满足任意两入口之间的最短路径不大于其直线距离的1.4倍这一约束条件。如下表中所列数据，并且由于这是一个无向图，所以下三角数据不予列出，并且为了明显期间，其他不相关数据也没有列出，则这些不满足条件的数据如下所示：24015513055270185160220295270再次：根据题意可知，入口间路径长度已经满足任意两入口之间的最短路径不大于其直线距离的1.4倍这一约束条件。而且涉及到的路径中可替换

16、的边是有限的，因此利用穷举法，我们进一步求出了满足任意两入口之间的最短路径不大于其直线距离的1.4倍这一约束条件的近似最优解，对应道路设计图如下所示：校 园 文 化 景 观 中 心信息楼逸夫教学楼XY0(20,0)(50,0)(160,0) (200,50) (120,100) (35,100) (10,100) (0,25) (50,75) (40,40) (120,40) (115,70)道 路道 路道 路最后将图示校园文化景观中心内的每条路径的起始点坐标带入到所编写Java代码中进行求解，得出最终在满足第一个问题的约束条件之下，我校园文化景观中心内新修道路的最短总长为394.5米。5.2

17、问题二的回答5.2.1问题二模型的建立由于就整体问题而言，都是优化问题，具有其相似点，所以对于问题二的求解，在某些情况下任然需要参照问题一中的相关信息，就其模型的建立应该从以下几个方面考虑。 首先：我们知道椭圆的定义为：平面上到两定点的距离之和为常值的点的轨迹，再根据此题设要求 我们可用椭圆的定义来解决此问题。所以我们先以任意两点（即任意入口点）为焦点，以1.4倍焦距为椭圆的长轴长做椭圆。做出椭圆之后我们会发现交叉点只会在椭圆与椭圆的交叉区域中，即在椭圆中。其次：通过对几何图形的分析 我们筛选出一些椭圆，缩小椭圆交叉区域，为后面的计算进行进一步的优化。再次：分别对交叉点为0个和两个的情况进行讨

18、论，最后优化出交叉点位置。5.2.2问题二模型的求解对于问题二的求解，应从以下几点出发去解决：第一：任意两个入口距离为焦距2C,以1.4倍2C为长轴长做椭圆，得出=28个椭圆。交叉点就在椭圆的额交叉区域内。第二：（1）M=0（即交叉点为0个时）因为为没有交叉点，所以我们只能依靠四周的矩形路。根据我们计算出的两点之间最短路径，与控制矩阵比较后，不符合条件的数据如下表显示这里仍然要参考问题一中的那个数据表，不过此处对于上次省略的问题予以给出：0.030.0259.8323.8203.2136.8161.832.00.0229.8293.8173.2106.8131.862.00.064.0117.

19、4181.3206.3291.80.0181.4245.4270.4355.90.0124.8149.8235.30.025.0168.80.0193.80.0注释：不添加交叉点时校园文化景观中心各入口的最短距离与1.4倍距离的比较结果因此必须通过添加交叉点才能使得新修道路满足条件任两入口之间的最短路径不大于其直线距离的1.4倍。（2） M=2（即交叉点为2个时）对八个入口进行分析，因为处于同一边的入口不存在大于两点连线的1.4倍，故处于同一边上的两个入口所画的椭圆可以去掉，经过筛选后的椭圆交点坐标为：1-6,1-8,2-5,2-6,2-7,3-4,3-5,3-6,3-7,4-5.所以图像简化

20、为由十个椭圆构成的图，然后对比分析其中重叠区域最密集的部分，则可确定出有两个交叉点及其范围区间。第三：求解最优路径的方法是先在交叉点的可行区域任意给定两点，用prim算法求出最优路线，固定路线后再以坐标为设计变量，以总路径为设计目标，以总路径最小进行优化，这样可以找到两个优化点，再以此确定改点，与八个入口一起按照prim算法寻找最尤路径，再优化点。按此方法不断的循环迭代，知道前后两处的优化点不再改变，此时得到的两个点即为交叉点,此时该问题与问题一类似，得到两个交叉点坐标为： F（91,58.554），E（161,39.4）。最后所得到的校园文化景观中心的规划图如下所示：校 园 文 化 景 观

21、中 心信息楼逸夫教学楼XY0(20,0)(50,0)(160,0) (200,50) (120,100) (35,100) (10,100) (0,25) F(91,58) E(161,39)道 路道 路道 路则最后所得校园文化景观中心道路总长为S = = 375.20.六、误差分析在进行本问题的求解过程中所存在的误差可能有以下几个方面，第一：在问题一中可能会由于对比数据进行删选时删选不当，第二个问题中可能会由于对椭圆构析方法使用不够完善，而导致最终所得的数据并非最优数据。还有就是可能由于各种算法使用的位置不当所造成的误差。七、模型推广最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路

22、、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等(如110报警、119火警以及120医疗救护系统)这些系统一般要求计算出到出事地点的最佳路线的时间应该在15一35内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。在很多目标信息引导系统的设计中需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者

23、实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息则可以达到迅速制止犯罪的目的。八、模型的应用对于最优路径的求解问题，不仅仅是在校园的规划与美化中存在，而且还可以将其应用到现实生活中的方方面面，比如像现在城市用地紧张，所以在城市住宅小区的优化建设以及高耸林立的现代大楼之间都可以将其进行推广应用。此外在农田道路的规划问题中也可以使用此模型，增加使用土地面积，减少不必要的浪费。还有就是在城市道路的规划中也可以将其推广应用。增加城市运输的流通量，减少道路阻塞问题。九、模型评价本文是在任意的两个入口之间的最短道路长

24、不大于两点连线的1.4倍的前提下，考虑总的道路长度和最小。建立了一个逐步逼近最优解的模型，通过计算机编程穷举其所有可能的点来实现的。模型优点1. 相对于整体考虑问题所带来的难度来说，进行局部之间的交替优化可简化问题。2. 充分利用了公园四周的边，使得总的道路长度最小。3. 对于第一题，我们在已经得到结果的基础上，进一步通过对局部的计算，得到更优解。模型不足1. 对局部的点进行交替来求最优解，虽然简化了问题的难度，但是计算量庞大，使用C语言编程过于繁杂，增加了劳动量。2. 局部最优化处理只能无限逼近全局的最优解，但无法证明我们所得结果是最优解。十、参考文献1 （美）吉奥丹诺（Giordano,

25、F.R.）等著；叶其孝、姜启源等译. 数学建模（原书第3版）. 北京：机械工业出版社，2005.12 王文波编译. 数学建模及其基础知识详解. 武汉：武汉大学出版社，2006.53 谭永基等编著. 数学模型. 上海：复旦大学出版社，2005.24 徐洁磐编. 离散数学基础教程. 北京：机械工业出版社，2009.75 卓金武、魏永生、泰键、李必文. MATLAB在数学建模中应用 北京航空航天大学出版社 2011.4十一、附 录附录一：MATLAB中求解任意两点之间的距离的MATLAB代码x = 20 50 160 200 120 35 10 0 50 40 120 115 ; y = 0 0 0

26、 50 100 100 100 25 75 40 40 70; for i=1:12 for j = 1:12 if i=j w(i,j) = sqrt(x(i)-x(j)2+(y(i)-y(j)2); end end end disp(邻接矩阵为) disp(w);附录二：编写的Java源代码。Point.javapublic class Point /保存每个点的坐标private int x;private int y;public Point(int x, int y) super();this.x = x;this.y = y;public int getX() return x;p

27、ublic void setX(int x) this.x = x;public int getY() return y;public void setY(int y) this.y = y;public double distanceTo (Point p) /计算从该点到 p 间线段的长度return Math.sqrt(this.y - p.y) * (this.y - p.y) + (this.x - p.x) * (this.x - p.x);Distance.javapublic class Distance public static double getEachDistance

28、() /取得各点相互之间的距离Point p = new Point(20, 0), new Point(50, 0), new Point(160, 0), new Point(200, 50), new Point(120, 100), new Point(35, 100), new Point(10, 100), new Point(0, 25), new Point(50, 75), new Point(40, 40), new Point(120, 40), new Point(115, 70);double distance = new double1212;for (int i

29、= 0; i p.length; i+) for (int j = 0; j b) int temp = b;b = a;a = temp;double eachLength = new double88;double circ = 600.0; /矩形周长eachLength01 = 30;eachLength12 = 110;eachLength23 = 90;eachLength34 = 130;eachLength45 = 85;eachLength56 = 25;eachLength67 = 85;/eachLength70 = ;double length = eachLength

30、aa+1;for (int i = a+1; i circ - length) length = circ - length;return length;Floyd.javapublic class Floyd double length = null;/ 任意两点之间路径长度int path = null;/ 任意两点之间的路径int edgeCount = 0;/ 记录边的数量double data = null;public double getLength() return length;public int getPath() return path;public int getEd

31、geCount() return edgeCount;public Floyd() public Floyd(double G) data = G;int MAX = 100;int row = G.length;/ 图G的行数int spot = new introwrow;/ 定义任意两点之间经过的点int onePath = new introw;/ 记录一条路径length = new doublerowrow;path = new introwrow;for (int i = 0; i row; i+) / 处理图两点之间的路径for (int j = 0; j row; j+) i

32、f (Gij = 0) Gij = MAX;/ 没有路径的两个点之间的路径为默认最大if (i = j) Gij = 0;/ 本身的路径长度为0for (int i = 0; i row; i+) / 初始化为任意两点之间没有路径for (int j = 0; j row; j+) spotij = -1;for (int i = 0; i row; i+) / 假设任意两点之间的没有路径onePathi = -1;for (int v = 0; v row; +v) for (int w = 0; w row; +w) lengthvw = Gvw;for (int u = 0; u row

33、; +u) for (int v = 0; v row; +v) for (int w = 0; w lengthvu + lengthuw) lengthvw = lengthvu + lengthuw;/ 如果存在更短路径则取更短路径spotvw = u;/ 把经过的点加入for (int i = 0; i row; i+) / 求出所有的路径int point = new int1;for (int j = 0; j row; j+) point0 = 0;onePathpoint0+ = i;outputPath(spot, i, j, onePath, point);pathij =

34、 new intpoint0;for (int s = 0; s point0; s+) pathijs = onePaths;void outputPath(int spot, int i, int j, int onePath, int point) / 输出i/ 到j的路径的实际代码，point记录一条路径的长度if (i = j)return;if (spotij = -1)onePathpoint0+ = j;/ System.out.print( +j+ );else outputPath(spot, i, spotij, onePath, point);outputPath(sp

35、ot, spotij, j, onePath, point);public Floyd getFloydResult() for (int i = 0; i data.length; i+)for (int j = i; j data.length; j+)if (dataij != dataji) break;Floyd test = new Floyd(data);for (int i = 0; i data.length; i+) for (int j = i; j datai.length; j+) for (int k = 0; k test.pathij.length; k+) e

36、dgeCount+;return test;public void showFloydResult() for (int i = 0; i data.length; i+)for (int j = i; j data.length; j+)if (dataij != dataji) break;Floyd test = new Floyd(data);for (int i = 0; i data.length; i+) for (int j = i; j datai.length; j+) System.out.println();System.out.print(From + (i + 1)

37、 + to + (j + 1)+ path is: );for (int k = 0; k test.pathij.length; k+) System.out.print(test.pathijk + 1) + );edgeCount+;System.out.println();System.out.println(From + (i + 1) + to + (j + 1)+ length : + test.lengthij); public static void main(String args) double data = Distance.getEachDistance();System.out.println(data03);Floyd f = new Floyd(data);f.getFloydResult();System.out.println(f.edgeCount);MinDistance.javapublic class MinDistance public static void main(String args) double data = Distance.getEachDistance();Floyd f = new Floyd(data);f.getFloydResult();20