校园文化景观中心道路设计问题.doc
《校园文化景观中心道路设计问题.doc》由会员分享,可在线阅读,更多相关《校园文化景观中心道路设计问题.doc(20页珍藏版)》请在沃文网上搜索。
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.
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 校园文化 景观 中心 道路 设计 问题