《动物园路径规划要点.pdf》由会员分享,可在线阅读,更多相关《动物园路径规划要点.pdf(21页珍藏版)》请在三一文库上搜索。
1、2014 高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了 全国大学生数学建模竞赛章程和全国大学生数学建模竞 赛参赛规则(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模 竞赛网站下载)。 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、 网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成 果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述 方式在正文引用处和参考文献中明确列出。 我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。
2、如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公 开展示(包括进行网上公示, 在书籍、期刊和其他媒体进行正式或非正式发表等)。 我们参赛选择的题号是(从A/B/C/D 中选择一项填写): A 我们的参赛报名号为(如果赛区设置报名号的话): 27090009 所属学校(请填写完整的全名):西北工业大学明德学院 参赛队员 ( 打印并签名 ): 1. 杨琳 2. 张阳 3. 田列敏 指导教师或指导教师组负责人 ( 打印并签名 ) : (论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。 以上 内容请仔细核对,提交
3、后将不再允许做任何修改。如填写错误,论文可能被取消 评奖资格。) 日期: 2014 年 9 月 10 日 赛区评阅编号(由赛区组委会评阅前进行编号): 2014 高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号(由赛区组委会评阅前进行编号): 赛区评阅记录(可供赛区评阅时使用): 评 阅 人 评 分 备 注 全国统一编号(由赛区组委会送交全国前编号): 全国评阅编号(由全国组委会评阅前进行编号): - 1 - 动物园最短路径规划模型 摘要 最短路径问题在实际生活中应用广泛,在商业利润估算、生产生活、道路建 设与规划等方面都有重要意义。对于动物园道路最优设计问题,本文基于Prim
4、 算 法,得出最小生成树,建立相应的最短路径模型,找出最优解。 针对问题一 :通过动物园的坐标参数构造出赋权图,考虑矩形动物园已有的 周边道路,且仅利用边界道路, 用 C+编程算出所有入口点两两直线距离, 利用“ 两 个入口最短道路长不超过两点连线1.5 倍” 的限制找出所有满足条件的情况,再把 不满足条件的入口点利用交叉点的情况逐一验证和讨论,然后用 MATLAB 编程找 出所有满足条件限制的路径建设方式,再通过对比与验证,得出园区内最短路径 为 1446.93米。 针对问题二 :由于问题一给出了四个道路的交叉点,又有固定的海洋馆作为 约束条件,则需要考虑问题一得到的最优解所建立的路径是否穿
5、过该海洋馆。如 有穿过,则需做进一步的局部优化;否则,最优解不变。由于是在问题一的基础 上增加了一个矩形海洋馆,则可以继续借助第一个问题的模型,再利用MATLAB 软件做出加入海洋馆之后的最短路径规划图,得出海洋馆没有穿过已经规划好的 最短道路,第一个问题的最优解没有受到海洋馆位置的限制,所以,最短路径仍 是 1446.93米。 关键字:Prim 算法最小生成树C+ 赋权图MATLAB - 2 - 一、问题重述 1.1 问题背景 武汉是我国中部最大的城市,在改革开放以来迅速发展,尤其在经济上取得 了重大的突破,而且为了响应国家中部大的崛起,营造出美好家园,促进我国经 济更近一步的大发展,武汉市
6、政府近期决定建造一个矩形动物园,并对其园内进 行规划,以方便游客们游玩。动物园设计规划决策者想在已经建好道路的矩形动 物园的四边上设置8 个入口点: M1 、M2 、M3 、M4 、M5 、M6 、M7 、M8 ;四个内部交 叉点: A、B、C、D。 1.2 问题要求 要求建立一个模型,即在两个入口最短道路长不超过两点连线1.5倍的情况下, 使其道路的总体长度最短(总长中不计入矩形四边的长度,新修的路与矩形四边 的连接只能在入口处,不能在矩形的其他位置)矩形动物园的基本参数及各个路 口坐标为:长: 1000米,宽:500米。 1 M (100,0), 2 M (250,0), 3 M (800
7、,0), 4 M (1000,250), 5 M (600,500), 6 M (175,500), 7 M (50,500), 8 M (0,125)。 A(250,375),B(200,200),C(600,200),D(575,350)。 (一)考虑边界道路已修建, 最短路径可以尽量依靠边界设置。根据以上矩形 动物园参数计算园区内最短路径规划。 (二)在中间设一个矩形海洋馆,海洋馆的四个点坐标为: 1 N (700,350), 2 N (700,225), 3 N (825,225), 4 N (825,350),要求道路不能穿过海洋馆,但可 以到达四边,以此绕过海洋馆,则计算其最短路径
8、。 二、问题分析 本题是一个道路设计的最优化的问题,即是如何设计路径使公园内部新修道 - 3 - 路总长最小,但要满足两个控制条件:1.任意两入口连通; 2.任意两个入口最短 路径不超过其直线距离的1.5 倍。注意到题设中说明动物园周围存在修好的道路, 优先考虑四周通道。再根据图论中,求最小生成树的方法,将整个动物园抽象为 这十二个点组成的一个图G,而图 G 是一个完全图。这样,再用prim 算法进行计 算得出最小生成树。最后根据各个题目的具体限制要求,进行局部优化。 在问题一中, 题目要求两个入口最短道路长不超过两点连线1.5 倍。考虑动物 园设计规划决策者想在已经建好道路 四条边线。现根据
9、边线计算入口处两两 之间距离。如果满足,则以边线作为此两处入口的最短路径。 在问题二中,由于引入了海洋馆,并且海洋馆位于动物园内固定位置,并且 要求新建道路不能穿过海洋馆,但可以到达四边,以此绕过海洋馆。所以首先考 虑问题二的路径是否穿过海洋馆。不穿过,则问题得解;否则,再进行局部优化 分析。所以,对问题一中已经讨论过的是否能利用边界道路的情况不产生影响, 仍然只需要考虑 “M1 M5、M1M6、M2M5、M2M6、M3M5、M3M6 ” 这 6 种情况,并且在问题一的设计方式下有些线路与海洋馆没有交点,固也不会 对那一段道路产生影响,所要考虑的只是与海洋馆有交点的几条路径,进行局部 优化。
10、三、模型假设 1、假设所有点或线都在同一平面内,不考虑台阶或其他因素的影响。 2、假设在修建道路时,交叉点的修建部影响总体长度。 3、假设道路的建设不受任何的阻碍。 4、除题目要求外,暂不考虑其他客观因素的影响。 四、符号说明 G: 赋权图。 - 4 - V: 表示顶点集合。 E: 表示距离集合。 W:邻接矩阵。 五、模型的建立与求解 5.1 问题一 题中给出动物园入口坐标以及四个交叉点坐标,总共12 个点。根据图论中赋 权图的定义,我们可以做出动物园赋权图。其中顶点为入口处和交叉点,权为距 离大小。这样,问题就转化为求这个无向图最路问题。 由题意可知出入点坐标和交叉点坐标: 表 5-1 出入
11、点坐标和交叉点坐标 点坐标点坐标点坐标点坐标 M1 (100,0) M2 (250,0) M3 (800,0) M4 (1000,250) M5 (600,500) M6 (175,500) M7 (50,500) M8 (0,125) A (250,375) B (200,200) C (600,200) D (575,350) 根据上述数据画出公园的出入点以及交叉点图: - 5 - 01002003004005006007008009001000 0 50 100 150 200 250 300 350 400 450 500 M1M2 M3 M4 M5 M6 M7 M8 A BC D 图
12、 5-1 公园的出入点以及交叉点图 5.1.1 模型建立(最小生成树) 首先构造赋权图。将每一出口或交叉点看做为顶点,将定顶点与顶点之间的 距离看做权重。 Prim 算法构造最小生成树: 构造连通的赋权图G=(V,E,W)的最小生成树,其中V 是顶点集合, E 是距 离集合, W 邻接矩阵。设置两个集合P和 Q 用于存放 G 的最小生成树中的顶点, 集合 Q 存放 G 的最小生成树边。 集合 P 的初值为 P= 1 v , 集合 Q 的初值为 Q=。 从所有 pP,vV-P 的边中,选取具有最小权值得边pv,将顶点 v 加入集合 P中, 将边 pv加入集合 Q 中,不断重复,知道P=V,完毕。
13、 算法: P= 1 v,Q=; While P=V 找出最小边 pv,其中 p P,vV-P; - 6 - P=P+v ; Q=Q+pv 。 5.1.2 模型求解 求解问题一时,将第一步分为两节,第一节算出口点之间点与点之间的直接 距离。第二节根据题意算出点与点的局限边界的路径距离,最后做出路径距离与 直接距离的比值,根据比值判断满足条件否,满足条件则就地利用边界路径作为 最短路径。第二步根据第一步的不满足条件的出口点结合园区内交叉点用prim 算 法计算最小生成树。最后得出道路总体规划出的最小生成树,再进行计算最小路 径。 第一步: 令 M1= 1 v ; V=M1 ,M2,M3,M4,M5
14、,M6,M7,M8 ; E 为顶点之间的距离。 (1)入口点两两之间的直线距离。 将顶点坐标经过 Microsoft Visual C+ 6.0 软件进行编程计算得到: 表 5-2 入口点两两之间的直线距离 入口点M1 M2 M3 M4 M5 M6 M7 M8 M1 0 150 700 934.08 707.11 505.6 502.5 160.8 M2 0 550 790.57 610.33 505.59 538.52 279.51 M3 0 320.16 538.52 800.39 901.39 809.71 M4 0 471.7 862.05 982.32 1007.78 M5 0 42
15、5 550 707.55 M6 0 125 413.82 M7 0 378.32 M8 0 (2)局限路径为四边的入口点两两之间的路径距离: - 7 - 表 5-3 局限路径为四边的入口点两两之间的路径距离 入口点M1 M2 M3 M4 M5 M6 M7 M8 M1 0 150 700 1150 1800 775 650 225 M2 0 550 1000 1650 925 800 375 M3 0 450 1100 1475 1350 925 M4 0 650 1075 1200 1375 M5 0 425 550 975 M6 0 125 525 M7 0 425 M8 0 根据条件,需要
16、算出两点间路径距离与两点间直线距离的比值。利用EXCEL 软件对( 1)/(2)数据进行运算得到下列结果: 表 5-4 两点间路径距离与两点间直线距离的比值 入口点 M1 M2 M3 M4 M5 M6 M7 M8 M1 1 1 1.231158 2.545573 1.532832 1.293532 1.399254 M2 1 1.26491 2.703456 1.829546 1.485553 1.341634 M3 1.405547 2.042635 1.842852 1.497687 1.142384 M4 1.377994 1.247027 1.221598 1.364385 M5 1
17、1 1.377994 M6 1 1.268668 M7 1.123388 表格中加入下划线的数值为大于1.5 的数值。 根据题意中不符合条件则上表数 值大于 1.5 的组合有 M1-M5 ,M1-M6 ,M2-M5 ,M2-M6 ,M3-M5 ,M3-M6 。 第二步: 经过第一步的计算, V 发生了改变。第一步不满足条件的点与交叉点带入模 型计算最短路径。 则 V=M1 ,M2,M3,M5,M6,A,B,C,D 。 (1)利用 Microsoft Visual C+ 6.0 软件进行编程计算两点距离得到: - 8 - 表 5-5 入口点与交叉点两两之间直线距离表 入口点M1 M2 M3 M5
18、 M6 A B C D M1 0 150 700 707.11 505.6 408.89 223.06 538.5 590 M2 0 550 610.33 505.59 375 206.16 403.1 447.6 M3 0 538.52 800.39 665.68 632.46 282.8 416.1 M5 0 425 371.65 500 300 152.1 M6 0 145.77 301.04 520.2 427.2 A 0 182 391.3 326 B 0 400 403.9 C 0 152.1 D 0 (2)用给出点的坐标值带入到上述模型中,进行MATLAB计算机编程,将V 点进
19、行编号 1,2,3,4,5,6,7,8,9 。 得到的结果如下所示: 1 2 7 6 6 9 9 8 2 7 6 5 9 4 8 3 150.00 206.16 182.00 145.77 326.00 152.10 152.10 282.80 根据上述 Matlab 计算出的结果利用 PHOTOSHOP画出得到没有边界的最小生成树 示意图: - 9 - 图 5-2 没有边界的最小生成树示意图 5.1.3 综合分析 园区内所有点最短路径最小生成树如下图: - 10 - 图 5-3 园区内所有点最短路径最小生成树示意图 根据计算机得出的最小生成树结果,进行画图: - 11 - 010020030
20、04005006007008009001000 0 50 100 150 200 250 300 350 400 450 500 M1 M2M3 M4 M5M6M7 M8 A B C D 图 5-4 园区内最短路径示意图 其中,园区内最短路径规划为: A-M6;A-D;A-B;B-M2;D-M5;D-C;C-M3; 园区边界路径入口之间规划路径为: M2-M1;M1-M8;M3-M4;M6-M7; 其中园区内最短路径规划长度S 为: S=AM6+AD+DB+BM2+DC+DM5+CM3=1446.93m 5.2 问题二 该问题是在问题一的基础上加入一个矩形海洋馆,根据题知海洋馆的四个点 坐标分
21、别为 1 N (700,350), 2 N (700,225), 3 N (825,225), 4 N (825,350),要求新建 道路不能穿过海洋馆,但可以到达四边,以此绕过海洋馆。所以首先考虑问题二 的路径是否穿过海洋馆。 利用 MATLAB 软件做出加入海洋馆之后的最短路径规划 图,结果发现海洋馆不穿过已经规划好的最短路径,则问题二得到解; 下图是 MATLAB 做出的加入海洋馆之后的示意图: - 12 - 01002003004005006007008009001000 0 50 100 150 200 250 300 350 400 450 500 M1 M2 M3 M4 M5 M
22、6M7 M8 A B C D N1 N2N3 N4 图 5-5 加入海洋馆园区内最短路径示意图 结果发现,问题一中得出的最优路线并没有穿过海洋馆,所以问题二不必进 行进一步优化,最优解还是1446.93米。 六、问题的检验 由于问题受到“任意两个入口点的最短路径不能超过两点连线的1.5 倍” 限制, 所以,基于从这个限制条件出发,在第一个问题中,通过prim 算法得出最小生成 树而得到了最优路径,所以要对其进行验证,看是否满足符合题目所给的限制条 件。 首先,先任取动物园周边道路八个点中的一个,由于矩形动物园的周边道路 是可以通行的,并且不计入道路规划的总体长度,所以,在同一边的点不需要进 行
23、比较,只需要对其不同边上点进行比较,看它们是否符合任意两个入口点的连 - 13 - 线不超过 1.5 倍的限制条件,如果满足,则完全符合题意,如不满足,则增添最优 道路。 然后从问题一中由最小生成树得到的园区最短路径示意图横坐标的点M8 开 始,分别对( M8,M7),(M8,M6),(M8,M5),(M8,M4)进行比较,通 过计算可以得出,都满足题目给出的限制条件,所以,不需要增添最优道路。 由上述的验证可知,经prim 算法得到最小生成树所得的最优路径满足“ 两个 入口最短道路长不超过两点连线1.5 倍” 这个约束条件的限制。即符合题述条件的 最短路线为 1446.93米。 七、模型的评
24、价与推广 7.1、模型优点 本文在建立模型的基础上充分利用了矩形动物园四周原有的道路,来使得总 体的道路长度最小。 prim 算法的时间复杂度不依赖于排序算法,而其主要与点的 个数有关,适用于点少的密集图,并且prim 算法的优化方案可以大大提高效率, 也给人们的生活带来许多必要的益处。而对于整体考虑较为困难的问题,先通过 逐步筛选,来使满足条件的尽可能变的越来越少,最后达到可以人工计算的目的。 7.2、模型缺点 由于模型的建立是在 “任意两个入口的最短路长不超过两点连线的1.5 倍”的 条件限制下,而该条件在现实生活中应用并不广泛,从而降低了模型的适用范 围。 并且该模型是基于多种假设所建立
25、的,和实际情况还有一些差距。例如:道 路为直线、在施工工程中完全可以按照规定方案进行等,均不太符合实际。 7.3、模型推广 优化方案的提出,可以给人们带来很多的便利,虽然本文主要讨论的是动物 - 14 - 园内部道路建设问题,但其使用的方法适于大部分的最短路问题,包括网络的布 局、城市道路及修建、公共场所的修建等问题。并且,最短路径问题在人们的实 际生活中的应用也非常之广泛,如在生产生活、商业利润估算及道路建设与规划 等方面都有着重要意义,而且该模型对节约社会资源,方便人们活动等各个方面 的问题有重大意义。 参考文献 1姜启源,谢金星,叶俊. 数学模型(第三版)M 。北京:高等教育出版社, 2
26、003 。 2孙蓬,MATLAB 基础教程,北京:清华大学出版社。 2011.10. 3 Douglas B.West , 图论导引,北京:机械工业出版社。2006,05。 3王莲芬,许树柏,层次分析法引论。中国人民大学出版社,1990。 4 孙蓬, MATLAB 基础教程。北京:清华大学出版社,2011,10。 5 Douglas B.West,图论导引。北京:机械工业出版社,2006,05。 6司守奎孙玺菁,数学建模算法与应用。北京:国防工业出版社,2013,02。 - 15 - 附 录 附录一 公园的出入点以及交叉点图代码MATLAB a= 0,1000,1000,0;b = 0,0,5
27、00,500;plot(a,b);hold on; x=100,250,800,1000,600,175,50,0; y=0,0,0,250,500,500,500,125; plot(x,y,o); hold on;gtext(M1); hold on;gtext(M2); hold on;gtext(M3); hold on;gtext(M4); hold on;gtext(M5); hold on;gtext(M6); hold on;gtext(M7); hold on;gtext(M8); hold on;N=250,200,600,575;M=375,200,200,350; pl
28、ot(N,M,x); hold on;gtext(A); hold on;gtext(B); hold on;gtext(C); hold on;gtext(D); 附录二 计算两点间距离代码C+ #include #include int main() int n; double a,b,c,d,s; scanf(“%d“, while(n-) - 16 - scanf(“%lf%lf%lf%lf“, s=sqrt(c-a)*(c-a)+(d-b)*(d-b); printf(“%.2lfn“,s); return 0; 附录三 最小生成树计算最短路径 a=zeros(9); a(1,2)=
29、150;a(1,3)=700;a(1,4)=707.11;a(1,5)=505.6;a(1,6)=408.89;a(1,7)=223.06;a(1,8) =538.5;a(1,9)=590; a(2,3)=550;a(2,4)=610.33;a(2,5)=505.59;a(2,6)=375;a(2,7)=206.16;a(2,8)=403.1;a(2,9) =447.6; a(3,4)=538.52;a(3,5)=800.39;a(3,6)=665.68;a(3,7)=632.46;a(3,8)=282.8;a(3,9)=416.1; a(4,5)=425;a(4,6)=371.65;a(4,
30、7)=500;a(4,8)=300;a(4,9)=152.1; a(5,6)=145.77;a(5,7)=301.04;a(5,8)=520.2;a(5,9)=427.2; a(6,7)=182;a(6,8)=391.3;a(6,9)=326; a(7,8)=400;a(7,9)=403.9; a(8,9)=152.1; a(9,9)=0 a=a+a; a(a=0)=inf; result=; p=1;tb=2:length(a); while size(result,2)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=fi
31、nd(a(p,tb)=d); j=p(jb(1); k=tb(kb(1); result=result,j;k;d; - 17 - p=p,k; tb(find(tb=k)=; end Result 附录四 园区最小路径规划图 a= 0,1000,1000,0;b = 0,0,500,500;plot(a,b);hold on; x=100,250,800,1000,600,175,50,0; y=0,0,0,250,500,500,500,125; plot(x,y,o); hold on;gtext(M1); hold on;gtext(M2); hold on;gtext(M3); ho
32、ld on;gtext(M4); hold on;gtext(M5); hold on;gtext(M6); hold on;gtext(M7); hold on;gtext(M8); hold on;N=250,200,600,575;M=375,200,200,350; plot(N,M,x); hold on;gtext(A); hold on;gtext(B); hold on;gtext(C); hold on;gtext(D); hold on; A=250,575;D=375,350;plot(A,D,r); hold on; A=250,200;B=375,200;plot(A
33、,B,r); hold on; B=200,250;M2=200,0;plot(B,M2,r); hold on; M2=250,0;Q=0,0;plot(M2,Q,g); hold on; Q=0,0;M8=0,125;plot(Q,M8,g); hold on; M6=175,50;M7=500,500;plot(M6,M7,g); hold on; D=575,600;M5=350,500;plot(D,M5,r); hold on; D=575,600;C=350,200;plot(D,C,r); - 18 - hold on; C=600,800;M3=200,0;plot(C,M3
34、,r); hold on; M3=800,1000;W=0,0;plot(M3,W,g); hold on; W=1000,1000;M4=0,250;plot(W,M4,g); hold on; A=250,175;M6=375,500;plot(A,M6,r); hold on; M8=0,0;T=125,500;plot(M8,T,b); 附录五 加入海洋馆的园区最小路径规划图 a= 0,1000,1000,0;b = 0,0,500,500;plot(a,b);hold on; x=100,250,800,1000,600,175,50,0; y=0,0,0,250,500,500,5
35、00,125; plot(x,y,o); hold on;gtext(M1); hold on;gtext(M2); hold on;gtext(M3); hold on;gtext(M4); hold on;gtext(M5); hold on;gtext(M6); hold on;gtext(M7); hold on;gtext(M8); hold on;N=250,200,600,575;M=375,200,200,350; plot(N,M,x); hold on;gtext(A); hold on;gtext(B); hold on;gtext(C); hold on;gtext(D
36、); hold on;Q=700,700,825,825;W=350,225,225,350; plot(Q,W,x); hold on;gtext(N1); hold on;gtext(N2); hold on;gtext(N3); hold on;gtext(N4); hold on; A=250,575;D=375,350;plot(A,D,r); - 19 - hold on; A=250,200;B=375,200;plot(A,B,r); hold on; B=200,250;M2=200,0;plot(B,M2,r); hold on; M2=250,0;Q=0,0;plot(M
37、2,Q,g); hold on; Q=0,0;M8=0,125;plot(Q,M8,g); hold on; M6=175,50;M7=500,500;plot(M6,M7,g); hold on; D=575,600;M5=350,500;plot(D,M5,r); hold on; D=575,600;C=350,200;plot(D,C,r); hold on; C=600,800;M3=200,0;plot(C,M3,r); hold on; M3=800,1000;W=0,0;plot(M3,W,g); hold on; W=1000,1000;M4=0,250;plot(W,M4,g); hold on; A=250,175;M6=375,500;plot(A,M6,r); hold on; M8=0,0;T=125,500;plot(M8,T,b); hold on; N1=700,700;N2=350,225;plot(N1,N2,b); hold on; N2=700,825;N3=225,225;plot(N2,N3,b); hold on; N3=825,825;N4=225,350;plot(N3,N4,b); hold on; N4=825,700;N1=350,350;plot(N4,N1,b);
链接地址:https://www.31doc.com/p-5206743.html