自来水管道问题.doc

自来水管道连接规划模型摘要在我们的日常生活中,有这样一个问题,那就是需要通过自来水管道将自来水运输至各个用户处,本文将着重分析讨论自来水管道连接规划问题,即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题,使自来水管道将各个供水点用最短路径连接。采用合理的方法排除障碍区域中的点,是对管道连接的效率、能耗、可行性起到决定性作用,是一个非常实际的问题。本文采用面积分析的方法,提供一种解决位于障碍区域中点的判定方法,在二维坐标系上标定各点,障碍区域用由阴影覆盖的凸多边形表出,通过对点坐标之间的向量运算判定各点是否位于阴影区域,在剔除障碍区中的点后,采用Kruskal避圈算法生成最优路径,对于通过障碍区域的线段,采用将其权值设定为∞(Inf)的处理方法,最终通过Matlab2009a编程、绘图,给出管道最优连接方案,解决本问题。最终通过Matlab2009a编程实现。Kruskal避圈算法是Kruskal在1956年提出的最小生成树算法,它的思路很容易理解。Kruskal算法每次选择n-1条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生回路的具有最小权重的边加入以选择的边的集合中。最后我们对模型的可行性,合理性,科学性进行了详细分析,对模型的优劣点进行阐述,得出了对模型的评价以及推广。关键词:管道连接面积法障碍点筛选有效线段的筛选矩阵的运算Kruskal算法权值最小生成树目录摘要 2一. 问题重述 13附录一:分工 13附录二:问题重述附录 13附录三:Matlab代码1(做图) 16附录四:求解最小生成树 17附录五:计算生成树长度 40附录六:Matlab代码2 77问题重述自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有很多问题需要解决。一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标,可能的用户的含义是:如果用户的地址不在障碍区域内,那么该用户就是需要使用自来水的用户(即有效用户),否则如果用户的地址在障碍区域内,那么该用户就是无效用户(即不要将该用户连接在网络中)。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标,而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来,并且连接的距离总和最小。