自来水管道连接问题摘要 自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有 很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。为了节约成本，需要找到最优的连通路线，使距离最短。对于问题一，为判断各点是否为有效用户，利用角度的方法来找出在障碍区内的无效用户。首先由所给信息在坐标系中画出所有用户点及障碍区顶点坐标，再找出能够包围障碍区域的最小矩形。考虑矩形中各点，将该点与障碍区域各顶点依次连接，算出相邻两条线段之间的交角1，2,3，（i180）并算得它们的总和为。若360，则该点不再障碍区域内，即为有效用户;若=360，则该点在障碍区域内,即为无效用户。最后确定了第4,23,36,99号点处在障碍区域内，为无效用户，其余所有点为有效用户。对于问题二，应用最优化模型来求最小连通距离。先通过障碍区域顶点与用户点的直线方程筛选有效用户之间的有效线段，构造有效线段的带权临接矩阵，将无效线段的距离赋值无穷大，利用带权临接矩阵，使用Kruskal最小生成树算法解出最小连通图，并解得最小连通距离为。最后，对模型进行了分析，并对此做出了改进。考虑到两有效用户点之间可以用通过第三点的折线连接而使线路更短。在第一步改进中，先分别加入障碍区的十四个顶点中的一个再次生成有效线段的带权临接矩阵，求得各自的最小连通距离。在这十四个距离中，最小值为643.8404。接下来加入十四个障碍区域顶点中的两个顶点后发现都比加入一个顶点时距离要长。分析加入多个顶点距离变大的原因后，确定应加入区域四的顶点3（90,75）获得最小距离。在上步改进基础上进行第二步改进，对连接线路中两相邻线段的夹角进行分析，当且仅当夹角为锐角时，可作较短边上的高以代替较长边，此时该三个有效用户点仍然连通，而路径长度可以大大缩小。对此改进方法进行模型求解，最终确定了最优路径。关键字：管道连接 内外点角度判断 最小生成树 Kruskal 权值矩阵 1目录第一部分：问题重述 问题一 问题二第二部分：问题分析 问题一 问题二第三部分：模型假设第四部分：符号说明第五部分：模型的建立与求解 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 一 问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有 很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。问题一：本题给出了若干个可能的用户的地址的横纵坐标，以及各个障碍区域的顶点坐标（见附录），我们需要根据这些数据信息确定出哪些用户为有效用户。可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户。已知障碍区域各顶点坐标，对应障碍区域就是覆盖这些要覆盖的点的最小凸集。问题二：在找出所有有效用户后，设计一个算法，避开障碍区域，将有效用户全部连接起来，使连接的距离总和最小。二 问题分析本问题主要根据各用户和障碍区的数据信息，对各用户点进行检测，找出有效用户的点，再设计一个算法，将全部有效用户连接起来，使得路径不经过障碍区域，并且连接路线总和最小。问题一：根据题目可知，当用户点在障碍区域外时，为有效用户；当用户点在障碍区域内时，为无效用户。为找出所有的有效用户点，可将目标区域缩小。分别作出包含各障碍区域的最小矩形，考虑对矩形区域中的用户点，将该点与障碍区域各顶点按顺序依次连接，再算出相邻两条线段的交角1，2,3，（i180）并算得它们的总和为。若360，则该点不再障碍区域内，即为有效用户;若=360，则该点在障碍区域内,即为无效用户。问题二：解决问题2需要两步。第一需筛选有效用户之间的有效线段。将任意两个有效用户用线段连接，如果任意两个用户点之间的线段通过障碍区域之内，则为无效线段，作剔除处理，筛选出有效线段。第二步，根据筛选出来的有效用户点和有效线段生成最小生成树连接有效用户点，画出连接路线图形，并计算生成树长度。 接下来需要设计程序将所有有效用户点连接起来，并使管道总距离最小。但相较以往最小生成树问题又有着其特别之处，就是障碍区域的干扰，即管道无法穿过障碍区，这使得坐标系并非是一个连通区域。可以将穿过障碍区的线段赋权值为无穷大，利用Kruskal算法，生成最优路径。 三 模型假设1.假设所给数据全部真实可靠。32.任何两个用户点之间都可以直接连接。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最小生成树的点以及连接的信息Sum最小生成树管道的总长Inf邻接矩阵中对应无效线段的位置的值 五 模型的建立与求解5.1.问题一的模型建立与求解 4本题已知各用户点与障碍区域的坐标信息，可应用角度的方法判断哪些为有效用户。分为四个步骤：一是先在坐标系中描出各用户点及障碍区顶点坐标。二是由各障碍区域顶点作出包含该区域的最小矩形，并找出矩形区域内的用户点。三是将矩形区域中某用户点与对应区域顶点连线，并求出相邻两条线段的交角1，2，3（i180）四是将这些角度加和得，若=360，说明该用户点在障碍区域内，为无效用户；若360,说明该用户点在障碍区域外，为有效用户。5.1.1在坐标系中画出各用户点及障碍区域的图像根据题目中给出的各用户点和各障碍区域顶点的坐标信息，在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编出程序运行（见附录），可得到图像，如下图所示： 图二 包含障碍区的最小矩形记矩形从左到右依次为区域一，二，三，四，通过比较在最小矩形区域的条件，得到在各个区域的内点和边界点，用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.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,y2-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 图三 用户点