试题十天然气的管道连接问题.doc

《试题十天然气的管道连接问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试题十天然气的管道连接问题如今使用天然气的人越来越多，作为天然气的供应商如何向用户供气，即如何使用户之间连接成一个树形网络是很重要的。一般来说，我们假设任意两个用户之间存在直线道相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用天然气的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。⑴请您判定

2、表1中那些用户为有效用户。⑵请您设计一个算法将有效用户连接起来，并且连接的距离总和最小。表1：若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标195.012958.27922620.276597.0845223.113942.34962719.872299.0083360.684351.55122860.379278.8862448.598233.39512927.218843.8659589.129943.29073019.881449.8311676.209722.5950311.527421.3963745.

3、646857.98073274.678664.349281.850476.03653344.509632.0036982.140752.98233493.181596.00991044.470364.05263546.599472.66321161.543220.90693641.864941.19531279.193737.98183784.622174.45661392.181378.33293852.515226.79471473.820768.08463920.264743.99241517.626646.10954067.213793.33801640.570656.78294183

4、.811868.33321793.547079.4211421.964021.25601891.69045.91834368.127783.92381941.027060.28694437.948162.87852089.36505.02694583.179613.3773215.789141.53754650.281320.71332235.286830.49994770.947160.71992381.316687.43674842.889262.9888240.98611.50094930.461737.04772513.889176.79505018.965457.51485119.3

5、43145.14257670.274067.56455268.22234.38957754.657169.92135330.27642.71857844.488072.75095454.167431.26857969.456747.83845515.08731.28638062.131055.48425669.789838.39678179.482112.10475737.837368.31168295.684345.07545886.00129.28428352.259071.58835985.36553.53388488.014289.28426059.356361.23958517.29

6、5627.31026149.655260.85408697.974725.47696289.97691.57608727.144786.56036382.16291.63558825.232923.23506464.491019.00758987.574280.48726581.797458.69189073.730690.83986666.02285.75819113.651923.18946734.197136.7568921.175723.93136828.972663.14519389.38984.97546934.119471.76349419.91387.83847053.4079

7、69.26699529.872364.08157172.71138.40799666.144319.08877230.929045.43559728.440984.38697383.849644.18289846.922417.39007456.807235.3250996.478117.07937537.041415.360610098.833599.4295表2障碍区域1必须要覆盖的点的坐标顶