毕业设计论文-自来水管的连接问题论文.doc
《毕业设计论文-自来水管的连接问题论文.doc》由会员分享,可在线阅读,更多相关《毕业设计论文-自来水管的连接问题论文.doc(36页珍藏版)》请在咨信网上搜索。
1、自来水管道连接问题摘要 自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有 很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。为了节约成本,需要找到最优的连通路线,使距离最短。对于问题一,为判断各点是否为有效用户,利用角度的方法来找出在障碍区内的无效用户。首先由所给信息在坐标系中画出所有用户点及障碍区顶点坐标,再找出能够包围障碍区域的最小矩形。考虑矩形中各点,将该点与障碍区域各顶点依次连接,算出相邻两条线段之间的交角1,2,3,(i180)并算得它们的总和为。若360,则该点不再
2、障碍区域内,即为有效用户;若=360,则该点在障碍区域内,即为无效用户。最后确定了第4,23,36,99号点处在障碍区域内,为无效用户,其余所有点为有效用户。对于问题二,应用最优化模型来求最小连通距离。先通过障碍区域顶点与用户点的直线方程筛选有效用户之间的有效线段,构造有效线段的带权临接矩阵,将无效线段的距离赋值无穷大,利用带权临接矩阵,使用Kruskal最小生成树算法解出最小连通图,并解得最小连通距离为。最后,对模型进行了分析,并对此做出了改进。考虑到两有效用户点之间可以用通过第三点的折线连接而使线路更短。在第一步改进中,先分别加入障碍区的十四个顶点中的一个再次生成有效线段的带权临接矩阵,求
3、得各自的最小连通距离。在这十四个距离中,最小值为643.8404。接下来加入十四个障碍区域顶点中的两个顶点后发现都比加入一个顶点时距离要长。分析加入多个顶点距离变大的原因后,确定应加入区域四的顶点3(90,75)获得最小距离。在上步改进基础上进行第二步改进,对连接线路中两相邻线段的夹角进行分析,当且仅当夹角为锐角时,可作较短边上的高以代替较长边,此时该三个有效用户点仍然连通,而路径长度可以大大缩小。对此改进方法进行模型求解,最终确定了最优路径。关键字:管道连接 内外点角度判断 最小生成树 Kruskal 权值矩阵 1目录第一部分:问题重述 问题一 问题二第二部分:问题分析 问题一 问题二第三部
4、分:模型假设第四部分:符号说明第五部分:模型的建立与求解 5.1 问题一的模型建立与求解 5.1.1 在坐标系中画出各用户点及障碍区域的图像5.1.2 作出包含各障碍区域的最小矩形,找出其中的用户点5.1.3 矩形区域中,求用户点与障碍区顶点连线间夹角并求和5.1.4 判断有效用户点5.1.5 模型求解 5.2 问题二的模型建立与求解 5.2.1 筛选有效用户间的有效线段 5.2.2 用最小生成树连接有效线段 5.2.3 模型求解第六部分:模型检验第七部分:模型的优缺点分析第八部分:模型的推广与改进参考文献附录2 一 问题重述自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有
5、很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。问题一:本题给出了若干个可能的用户的地址的横纵坐标,以及各个障碍区域的顶点坐标(见附录),我们需要根据这些数据信息确定出哪些用户为有效用户。可能的用户的含义是:如果用户的地址不在障碍区域内,那么该用户就是需要使用自来水的用户(即有效用户),否则如果用户的地址在障碍区域内,那么该用户就是无效用户。已知障碍区域各顶点坐标,对应障碍区域就是覆盖这些要覆盖的点的最小凸集。问题二:在找出所有有效用户后,设计一个算法,避开障碍区域,将有效用户全部连接起来,使
6、连接的距离总和最小。二 问题分析本问题主要根据各用户和障碍区的数据信息,对各用户点进行检测,找出有效用户的点,再设计一个算法,将全部有效用户连接起来,使得路径不经过障碍区域,并且连接路线总和最小。问题一:根据题目可知,当用户点在障碍区域外时,为有效用户;当用户点在障碍区域内时,为无效用户。为找出所有的有效用户点,可将目标区域缩小。分别作出包含各障碍区域的最小矩形,考虑对矩形区域中的用户点,将该点与障碍区域各顶点按顺序依次连接,再算出相邻两条线段的交角1,2,3,(i180)并算得它们的总和为。若360,则该点不再障碍区域内,即为有效用户;若=360,则该点在障碍区域内,即为无效用户。问题二:解
7、决问题2需要两步。第一需筛选有效用户之间的有效线段。将任意两个有效用户用线段连接,如果任意两个用户点之间的线段通过障碍区域之内,则为无效线段,作剔除处理,筛选出有效线段。第二步,根据筛选出来的有效用户点和有效线段生成最小生成树连接有效用户点,画出连接路线图形,并计算生成树长度。 接下来需要设计程序将所有有效用户点连接起来,并使管道总距离最小。但相较以往最小生成树问题又有着其特别之处,就是障碍区域的干扰,即管道无法穿过障碍区,这使得坐标系并非是一个连通区域。可以将穿过障碍区的线段赋权值为无穷大,利用Kruskal算法,生成最优路径。 三 模型假设1.假设所给数据全部真实可靠。32.任何两个用户点
8、之间都可以直接连接。3.不在障碍区里的用户都能够通过自来水管获得自来水供应。4.假设障碍区域的边界是标准的直线。5.障碍区域就是障碍顶点围成的凸多边形区域。7.要保证在任意两点间线段不过障碍区的情况下求解连接形成的最短路线。 四 符号约束与说明符号 说明(xi,yi) i=1,2,3.障碍区域各顶点坐标(ai,bi) i=1,2,3各用户点的坐标i, i=1,2,3用户点与障碍区顶点各相邻连线的夹角 (i180时,取其为360-i所有夹角之和i (k,j)区域i中第k个点的j个角N有效用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS连接的长度M最小生成树的点以及连
9、接的信息Sum最小生成树管道的总长Inf邻接矩阵中对应无效线段的位置的值 五 模型的建立与求解5.1.问题一的模型建立与求解 4本题已知各用户点与障碍区域的坐标信息,可应用角度的方法判断哪些为有效用户。分为四个步骤:一是先在坐标系中描出各用户点及障碍区顶点坐标。二是由各障碍区域顶点作出包含该区域的最小矩形,并找出矩形区域内的用户点。三是将矩形区域中某用户点与对应区域顶点连线,并求出相邻两条线段的交角1,2,3(i180)四是将这些角度加和得,若=360,说明该用户点在障碍区域内,为无效用户;若360,说明该用户点在障碍区域外,为有效用户。5.1.1在坐标系中画出各用户点及障碍区域的图像根据题目
10、中给出的各用户点和各障碍区域顶点的坐标信息,在matlab中编出程序(见附录),可得如下图像:图一 障碍区域与各用户点示意图5.1.2 作出包含各障碍区域的最小矩形,并找出其中的用户点设某障碍区域各顶点坐标为 A(x1,y1),B(x2,y2),C(x3,y3) 5则取p=min(x1,x2,x3) q=max(x1,x2,x3)r=min(y1,y2,y3) s=max(y1,y2,y3)故包含该障碍区域的最小矩形即为 X=p,X=q,Y=r,Y=s四条直线所围成的矩形。对于任意用户点M(x,y),若满足pxq,rys,则M点就在矩形区域内,否则,M点不在矩形区域内。在matlab编出程序运
11、行(见附录),可得到图像,如下图所示: 图二 包含障碍区的最小矩形记矩形从左到右依次为区域一,二,三,四,通过比较在最小矩形区域的条件,得到在各个区域的内点和边界点,用MATLAB编程(见附录III)可得如下表格:(共计16个点)表一:区域一区域二区域三区域四最小矩形内点标号9967,22,16,36,33,4,5435,83,7790,23,89,37,84标号对应的坐标(6.4781,17.0793)(34.1971,36.7568)(35.2868,30.4999)(40.5706,56.7829)(41.8649,41.1953)(44.5096,32.0036)(48.5982,33
12、.3951)(54.1674,31.2685)(46.5994,72.6632)(52.2590,71.5883)(54.6571,69.9213)(73.7306,90.8398)(81.3166,87.4367)(87.5742,80.4872)(84.6221,74.4566)(88.0142,89.2842)5.1.3 将矩形区域中用户点与障碍区顶点连线,求各相邻连线间夹角并求和设矩形区域内某个用户点坐标为M(a,b),M与障碍区域各顶点连线后,某相邻两条线断分别为MA,MB.设A点坐标(x1,y1),B点坐标(x2,y2),则向量MA=(x1-a,y1-b),向量MB=(x2-a,y
13、2-b),MA与MB的内积为MAMB=| MA|MB| cos则=用matlab编写程序实现算法(见附录),可得如下示意图(以包含五边形障碍区的矩形中两点G,F为例)点G分别与五边形的顶点A,B,C,D,E相连见洋红色连线,记AGB, BGC, CGD, DGE, EGA分别为2(4,1),2(4,2),2(4,3),2(4,4), 2(4,5).点F与五边形的顶点A,B,C,D,E相连见蓝绿色连线.记为DFE,EFA,AFB,BFC. 分别为2(1,1), 2(1,2),2(1,3),2(1,4),2(1,5). 7 图三 用户点与障碍区顶点连线用MATLAB分别按区域一,区域二,区域三,区
14、域四中各点与顶点的夹角(必须是相邻两边且角度小于180)记为i (k,j)。以表一中最小矩形内的点按从左到右从上到下的顺序按区域标记为1,2,3依次类推。得到表二:区域点标号指定角弧度角度求和一991(1,1)2.4398139.7902360.01801 (1,2)1.9431111.33141 (1,3)1.9006108.8964二672 (1,1)0.943154.0356258.38102 (1,2)0.473227.11242 (1,3)0.13097.50002 (1,4)0.707640.54252 (1,5)2.2548129.1905222 (2,1)0.805346.14
15、03207.7487二2(2,2)0.387322.19072 (2,3)0.11786.74942 (2,4)0.502528.79112 (2,5)1.8130103.8772162 (3,1)0.668338.2908232.31152 (3,2)0.616935.34582 (3,3)0.233613.38432 (3,4)1.7937102.77142 (3,5)0.742142.5192362 (4,1)1.490585.3994360.00102 (4,2)0.715240.97802 (4,3)0.225212.90302 (4,4)1.8144103.95752 (4,5)2
16、.0379116.7631332 (5,1)1.408980.7240330.32152 (5,2)0.416023.83502 (5,3)0.15328.77772 (5,4)0.904551.82402 (5,5)2.8826165.160842 (6,1)2.4205138.6844359.99502 (6,2)0.400022.91832 (6,3)0.16449.41942 (6,4)0.938653.77782 (6,5)2.3596135.1951542 (7,1)1.8418105.5274211.05472 (7,2)0.248814.25522 (7,3)0.14248.1
17、5892 (7,4)0.766543.91722 (7,5)0.684139.1960三353 (1,1)1.497585.8004211.36993 (1,2)1.8445105.68213 (1,3)0.347119.8874833 (2,1)2.0674118.4533310.92703 (2,2)2.7133155.46063 (2,3)0.646037.0131773 (3,1)0.526630.1720130.16463 (3,2)1.135965.08233 (3,3)0.609334.9103四904 (1,1)1.357977.8020285.11534 (1,2)1.130
18、264.75574 (1,3)2.4881142.5576234 (2,1)2.7044154.9507359.99514 (2,2)1.598991.61024 (2,3)1.9798113.4342894 (3,1)3.0768176.2877352.57534 (3,2)1.9593112.25964 (3,3)1.117564.0280374 (4,1)1.691496.9101306.93354 (4,2)2.6785153.46674 (4,3)0.987156.5567844 (5,1)2.3285133.4132266.82664 (5,2)1.233170.65144 (5,
19、3)1.095462.76185.1.4判断有效用户点由题目所给信息,障碍区域最多为五边形,下面对三、四、五边形,就利用角度判断障碍区域内外点的方法给出证明。 三角形 四边形 五边形(1) 三角形情况: 9内点D与顶点A,B,C分别连接得向量DA,DB,DC,各相邻两向量的夹角分别为1,2,3,将ABC分成ADB,ADC,BDC,由三角形内角和为180,则1+2+3=3180-180=360。 外点E与顶点A,B,C分别连接得向量EA,EB,EC, 取相邻两向量的夹角分别为1,2,EA,EB相邻时AEB180时角度相加依然会小于360。即记为1+2+AEB360。(2)四边形,五边形情况类似讨
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业设计 论文 自来 水管 连接 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。