自来水管道连接规划模型
摘要
现代日常生活中，需要通过自来水管道将自来水运输至各个用户处，本文主要分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径且自来水管道中各个供水点及用户以最短路径连接的问题。
排除障碍区域：面积分析法即在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域。
最优路径规划：通过Prim算法计算最小生成树，得出最优连接方案 （prim算法：在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U={v0}，集合T(E)为空。 2. 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1 }，同时将该边加入集合T(E)中。 3. 重复2，直到U=V为止。 这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树）。
关键词：管道连接 面积法 障碍点筛选 Prim算法 最小生成树
一．问题重述
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。
表1若干个可能的用户的地址的横纵坐标 可能的用户的序号 1.0000 2.0000 3.0000 4.0000 5.0000 可能的用户横坐标 95.0129 23.1139 60.6843 48.5982 89.1299
可能的用户纵坐标 58.2792 42.3496 51.5512 33.3951 43.2907
6.0000 7.0000 8.0000 9.0000 10.0000 11.0000 12.0000 13.0000 14.0000 15.0000 16.0000 17.0000 18.0000 19.0000 20.0000 21.0000 22.0000 23.0000 24.0000 25.0000 26.0000 27.0000 76.2097 45.6468 1.8504 82.1407 44.4703 61.5432 79.1937 92.1813 73.8207 17.6266 40.5706 93.5470 91.6904 41.0270 89.3650 5.7891 35.2868 81.3166 0.9861 13.8891 20.2765 19.8722
22.5950 57.9807 76.0365 52.9823 64.0526 20.9069 37.9818 78.3329 68.0846 46.1095 56.7829 79.4211 5.9183 60.2869 5.0269 41.5375 30.4999 87.4367 1.5009 76.7950 97.0845 99.0083
28.0000 29.0000 30.0000 31.0000 32.0000 33.0000 34.0000 35.0000 36.0000 37.0000 38.0000 39.0000 40.0000 41.0000 42.0000 43.0000 44.0000 45.0000 46.0000 47.0000 48.0000 49.0000 60.3792 27.2188 19.8814 1.5274 74.6786 44.5096 93.1815 46.5994 41.8649 84.6221 52.5152 20.2647 67.2137 83.8118 1.9640 68.1277 37.9481 83.1796 50.2813 70.9471 42.8892 30.4617
78.8862 43.8659 49.8311 21.3963 64.3492 32.0036 96.0099 72.6632 41.1953 74.4566 26.7947 43.9924 93.3380 68.3332 21.2560 83.9238 62.8785 13.3773 20.7133 60.7199 62.9888 37.0477
自来水管道规划模型-数学建模
