自来水管的连接问题 2.docx
- 文档编号:15479195
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:28
- 大小:256.15KB
自来水管的连接问题 2.docx
《自来水管的连接问题 2.docx》由会员分享,可在线阅读,更多相关《自来水管的连接问题 2.docx(28页珍藏版)》请在冰点文库上搜索。
自来水管的连接问题2
目录
一、问题重述
二、问题分析
三、模型假设
四、符号说明
五、模型建立与求解
六、模型的检验
七、模型的优缺点分析
八、模型的推广与改进
附录
数学1101王耀东20111378
数学1101张启明20111383
数学1101解雅琴20111388
一问题重述:
自来水是人们日常生活中不可缺少的生活要素,然而自来水管网的组建却有很多问题需要解决。
一般来说,我们假设管网中任意两个用户之间存在直线段相连,但是在连接过程中,有些区域是必须绕开的,这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标,可能的用户的含义是:
如果用户的地址不在障碍区域内,那么该用户就是需要使用自来水的用户(即有效用户),否则如果用户的地址在障碍区域内,那么该用户就是无效用户(即不要将该用户连接在网络中)。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标,而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1)请您判定表1中那些用户为有效用户。
(2)请设计一个算法将有效用户连接起来,并且连接的距离总和最小。
表1若干个可能的用户的地址的横纵坐标
可能的用户的序号可能的用户横坐标可能的用户纵坐标
1.000095.012958.2792
2.000023.113942.3496
3.000060.684351.5512
4.000048.598233.3951
5.000089.129943.2907
6.000076.209722.5950
7.000045.646857.9807
8.00001.850476.0365
9.000082.140752.9823
10.000044.470364.0526
11.000061.543220.9069
12.000079.193737.9818
13.000092.181378.3329
14.000073.820768.0846
15.000017.626646.1095
16.000040.570656.7829
17.000093.547079.4211
18.000091.69045.9183
19.000041.027060.2869
20.000089.36505.0269
21.00005.789141.5375
22.000035.286830.4999
23.000081.316687.4367
24.00000.98611.5009
25.000013.889176.7950
26.000020.276597.0845
27.000019.872299.0083
28.000060.379278.8862
29.000027.218843.8659
30.000019.881449.8311
31.00001.527421.3963
32.000074.678664.3492
33.000044.509632.0036
34.000093.181596.0099
35.000046.599472.6632
36.000041.864941.1953
37.000084.622174.4566
38.000052.515226.7947
39.000020.264743.9924
40.000067.213793.3380
41.000083.811868.3332
42.00001.964021.2560
43.000068.127783.9238
44.000037.948162.8785
45.000083.179613.3773
46.000050.281320.7133
47.000070.947160.7199
48.000042.889262.9888
49.000030.461737.0477
50.000018.965457.5148
51.000019.343145.1425
52.000068.22234.3895
53.000030.27642.7185
54.000054.167431.2685
55.000015.08731.2863
56.000069.789838.3967
57.000037.837368.3116
58.000086.00129.2842
59.000085.36553.5338
60.000059.356361.2395
61.000049.655260.8540
62.000089.97691.5760
63.000082.16291.6355
64.000064.491019.0075
65.000081.797458.6918
66.000066.02285.7581
67.000034.197136.7568
68.000028.972663.1451
69.000034.119471.7634
70.000053.407969.2669
71.000072.71138.4079
72.000030.929045.4355
73.000083.849644.1828
74.000056.807235.3250
75.000037.041415.3606
76.000070.274067.5645
77.000054.657169.9213
78.000044.488072.7509
79.000069.456747.8384
80.000062.131055.4842
81.000079.482112.1047
82.000095.684345.0754
83.000052.259071.5883
84.000088.014289.2842
85.000017.295627.3102
86.000097.974725.4769
87.000027.144786.5603
88.000025.232923.2350
89.000087.574280.4872
90.000073.730690.8398
91.000013.651923.1894
92.00001.175723.9313
93.000089.38984.9754
94.000019.91387.8384
95.000029.872364.0815
96.000066.144319.0887
97.000028.440984.3869
98.000046.922417.3900
99.00006.478117.0793
100.000098.833599.4295
表2障碍区域1必须要覆盖的点的坐标
顶点序号顶点的横坐标顶点的纵坐标
13.206012.9166
217.457119.3377
34.757620
表3障碍区域2必须要覆盖的点的坐标
顶点序号顶点的横坐标顶点的纵坐标
15030
253.746548.4490
346.922257.1195
433.320739.8050
543.112356.3187
表4障碍区域3必须要覆盖的点的坐标
顶点序号顶点的横坐标顶点的纵坐标
154.698270
253.746590
346.922280
表5障碍区域4必须要覆盖的点的坐标
顶点序号顶点的横坐标顶点的纵坐标
19075
28095
37080
二问题分析:
在日常生活中水是不可或缺的,但是自来水管的连接就涉及到是否合理的问题。
由于相关人员的统计调查也存在误差,在一些障碍区域内居然也存在某些用户,所以在第一问中我们需要在表1提供的用户数据中将无效用户判别出来,图中标记出来的障碍区域已知,利用inpolygon函数确定点是否在区域内部。
第二问中需要把有效用户用最短的路径连接起来,实现所用水管最少,解决该问题的关键是利用最小生成树的方法,引入mintree函数。
三模型假设:
1:
利用inpolygon函数确定点是否在区域内部
2:
利用最小生成树mintree连接有效用户使水管最短
3利用sum函数求出总距离
四符号说明:
A是所有点的横纵坐标构成的矩阵;
Bi是各障碍区域内的点的横纵坐标构成的矩阵;
D是分区以后各区域内任意两点的距离矩阵;
E是各区域内的点的横纵坐标构成的矩阵;
F是任意两点间距离的邻间矩阵;
Gi是最小生成树的邻间矩阵;
五模型建立与求解:
1)由图中给定的障碍区域的坐标可以确定不可以铺设自开水管道的区域,由此建立模型,利用inpolygon函数确定点是否在区域内,给出所统计的用户数据A,如果满足在区域内则判别出该用户不可铺设管道,由此求解程序如下:
A=[1.0000,95.0129,58.2792;2.0000,23.1139,42.3496;3.0000,60.6843,51.5512;4.000,48.5982,33.3951;5.0000,89.1299,43.2907;6.0000,76.2097,22.5950;7.0000,45.6468,57.9807;8.0000,1.8504,76.0365;9.0000,82.1407,52.9823;10.0000,44.4703,64.0526;11.0000,61.5432,20.9069;12.0000,79.1937,37.9818;13.0000,92.1813,78.3329;14.0000,73.8207,68.0846;15.0000,17.6266,46.1095;16.0000,40.5706,56.7829;17.0000,93.5470,79.4211;18.0000,91.6904,5.9183;19.0000,41.0270,60.2869;20.0000,89.3650,5.0269;21.0000,5.7891,41.5375;22.0000,35.2868,30.4999;23.0000,81.3166,87.4367;24.0000,0.9861,1.5009;25.0000,13.8891,76.7950;26.0000,20.2765,97.0845;27.0000,19.8722,99.0083;28.0000,60.3792,78.8862;29.0000,27.2188,43.8659;30.0000,19.8814,49.8311;31.0000,1.527,21.3963;32.0000,74.6786,64.3492;33.0000,44.5096,32.0036;34.0000,93.1815,96.0099;35.0000,46.5994,72.6632;36.0000,41.8649,41.1953;37.0000,84.6221,74.4566;38.0000,52.5152,26.7947;39.0000,20.2647,43.9924;40.0000,67.2137,93.3380;41.0000,83.8118,68.3332;42.0000,1.9640,21.2560;43.0000,68.1277,83.9238;44.0000,37.9481,62.8785;45.0000,83.1796,13.3773;46.0000,50.2813,20.7133;47.0000,70.9471,60.7199;48.0000,42.8892,62.9888;49.0000,30.4617,37.0477;50.0000,18.9654,57.5148;51.0000,19.3431,45.1425;52.0000,68.2223,4.3895;53.0000,30.2764,2.7185;54.0000,54.1674,31.2685;55.0000,15.0873,1.2863;56.0000,69.7898,38.3967;57.0000,37.8373,68.3116;58.0000,86.0012,9.2842;59.0000,85.3655,3.5338;60.0000,59.3563,61.2395;61.0000,49.6552,60.8540;62.0000,89.9769,1.5760;63.0000,82.1629,1.6355;64.0000,64.4910,19.0075;65.0000,81.7974,58.6918;66.0000,66.0228,5.7581;67.0000,34.1971,36.7568;68.0000,28.9726,63.1451;69.0000,34.1194,71.7634;70.0000,53.4079,69.2669;71.0000,72.7113,8.4079;72.0000,30.9290,45.4355;73.0000,83.8496,44.1828;74.0000,56.8072,35.3250;75.0000,37.0414,15.3606;76.0000,70.2740,67.5645;77.0000,54.6571,69.9213;78.0000,44.4880,72.7509;79.0000,69.4567,47.8384;80.0000,62.1310,55.4842;81.0000,79.4821,12.1047;82.0000,95.6843,45.0754;83.0000,52.2590,71.5883;84.0000,88.0142,89.2842;85.0000,17.2956,27.3102;86.0000,97.9747,25.4769;87.0000,27.1447,86.5603;88.0000,25.2329,23.2350;89.0000,87.5742,80.4872;90.0000,73.7306,90.8398;91.0000,13.6519,23.1894;92.0000,1.1757,23.9313;93.0000,89.3898,4.9754;94.0000,19.9138,7.8384;95.0000,29.8723,64.0815;96.0000,66.1443,19.0887;97.0000,28.4409,84.3869;98.0000,46.9224,17.3900;99.0000,6.4781,17.0793;100.0000,98.8335,99.4295]
B1=[1,3.2060,12.9166;2,17.4571,19.3377;3,4.7576,20]
fori=1:
100,X1(i,1)=inpolygon(A(i,2),A(i,3),B1(:
2),B1(:
3));end
find(X1>=1)
B2=[1,50,30;2,53.7465,48.4490;3,33.3207,39.8050]
fori=1:
100,X2(i,1)=inpolygon(A(i,2),A(i,3),B2(:
2),B2(:
3));end
find(X2>=1)
B3=[1,54.6982,70;2,53.7465,90;3,46.9222,80]
fori=1:
100,X3(i,1)=inpolygon(A(i,2),A(i,3),B3(:
2),B3(:
3));end
find(X3>=1)
B4=[1,90,75;2,80,95;3,70,80]
fori=1:
100,X4(i,1)=inpolygon(A(i,2),A(i,3),B4(:
2),B4(:
3));end
find(X4>=1)
B5=[1,53.7465,48.4490;2,33.3207,39.8050;3,43.1123,56.3187]
fori=1:
100,X5(i,1)=inpolygon(A(i,2),A(i,3),B5(:
2),B5(:
3));end
find(X5>=1)
B6=[1,46.9222,57.1195;2,43.1123,56.3187;3,53.7465,48.4490]
fori=1:
100,X6(i,1)=inpolygon(A(i,2),A(i,3),B6(:
2),B6(:
3));end
find(X6>=1)
:
2)要实现水管的最节约,首先划分区域,如图
然后分别对不同区域采用最小生成树的方法进行。
(2)定义新函数mintrees:
function[b,u,w]=mintrees(a,k)
ifnargout==1
k=1;
end
[m,n]=size(a);
fori=1:
m
forj=1:
n
ifa(i,j)==0
a(i,j)=inf;
end
end
end
b=zeros(n);
u
(1)=k;
j=1;
v=zeros(1,n);
v(k)=1;
foro=1:
n-1
sn=ones(3,n)*inf;
forxk=1:
j
k=u(xk);
p=max(a(k,:
));
fori=1:
n
ifv(i)<1&a(k,i)
p=a(k,i);
end
end
fori=1:
n
ifv(i)<1&a(k,i)==p
break;
end
end
sn([123],k)=[i,p,u(xk)];
end
[w(j),k]=min(sn(2,:
));
j=j+1;
u(j)=sn(1,k);
b(sn(1,k),sn(3,k))=sn(2,k);
v(u(j))=1;
end
A区和F区因为没有用户,所以无需程序连接。
B区内的用户点建立模型如下:
A=[1.0000,95.0129,58.2792;2.0000,23.1139,42.3496;3.0000,60.6843,51.5512;4.000,48.5982,33.3951;5.0000,89.1299,43.2907;6.0000,76.2097,22.5950;7.0000,45.6468,57.9807;8.0000,1.8504,76.0365;9.0000,82.1407,52.9823;10.0000,44.4703,64.0526;11.0000,61.5432,20.9069;12.0000,79.1937,37.9818;13.0000,92.1813,78.3329;14.0000,73.8207,68.0846;15.0000,17.6266,46.1095;16.0000,40.5706,56.7829;17.0000,93.5470,79.4211;18.0000,91.6904,5.9183;19.0000,41.0270,60.2869;20.0000,89.3650,5.0269;21.0000,5.7891,41.5375;22.0000,35.2868,30.4999;23.0000,81.3166,87.4367;24.0000,0.9861,1.5009;25.0000,13.8891,76.7950;26.0000,20.2765,97.0845;27.0000,19.8722,99.0083;28.0000,60.3792,78.8862;29.0000,27.2188,43.8659;30.0000,19.8814,49.8311;31.0000,1.527,21.3963;32.0000,74.6786,64.3492;33.0000,44.5096,32.0036;34.0000,93.1815,96.0099;35.0000,46.5994,72.6632;36.0000,41.8649,41.1953;37.0000,84.6221,74.4566;38.0000,52.5152,26.7947;39.0000,20.2647,43.9924;40.0000,67.2137,93.3380;41.0000,83.8118,68.3332;42.0000,1.9640,21.2560;43.0000,68.1277,83.9238;44.0000,37.9481,62.8785;45.0000,83.1796,13.3773;46.0000,50.2813,20.7133;47.0000,70.9471,60.7199;48.0000,42.8892,62.9888;49.0000,30.4617,37.0477;50.0000,18.9654,57.5148;51.0000,19.3431,45.1425;52.0000,68.2223,4.3895;53.0000,30.2764,2.7185;54.0000,54.1674,31.2685;55.0000,15.0873,1.2863;56.0000,69.7898,38.3967;57.0000,37.8373,68.3116;58.0000,86.0012,9.2842;59.0000,85.3655,3.5338;60.0000,59.3563,61.2395;61.0000,49.6552,60.8540;62.0000,89.9769,1.5760;63.0000,82.1629,1.6355;64.0000,64.4910,19.0075;65.0000,81.7974,58.6918;66.0000,66.0228,5.7581;67.0000,34.1971,36.7568;68.0000,28.9726,63.1451;69.0000,34.1194,71.7634;70.0000,53.4079,69.2669;71.0000,72.7113,8.4079;72.0000,30.9290,45.4355;73.0000,83.8496,44.1828;74.0000,56.8072,35.3250;75.0000,37.0414,15.3606;76.0000,70.2740,67.5645;77.0000,54.6571,69.9213;78.0000,44.4880,72.7509;79.0000,69.4567,47.8384;80.0000,62.1310,55.4842;81.0000,79.4821,12.1047;82.0000,95.6843,45.0754;83.0000,52.2590,71.5883;84.0000,88.0142,89.2842;85.0000,17.2956,27.3102;86.0000,97.9747,25.4769;87.0000,27.1447,86.5603;88.0000,25.2329,23.2350;89.0000,87.5742,80.4872;90.0000,73.7306,90.8398;91.0000,13.6519,23.1894;92.0000,1.1757,23.9313;93.0000,89.3898,4.9754;94.0000,19.9138,7.8384;95.0000,29.8723,64.0815;96.0000,66.1443,19.0887;97.0000,28.4409,84.3869
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自来水管的连接问题 自来 水管 连接 问题