試題十 天然氣的管道連接問題

1、試題十試題十天然氣的管道連接問題天然氣的管道連接問題如今使用天然氣的人越來越多，作為天然氣的供應(yīng)商如何向用戶供氣，即如何使用戶之間連接成一個(gè)樹形網(wǎng)絡(luò)是很重要的。一般來說，我們假設(shè)任意兩個(gè)用戶之間存在直線道相連，但是在連接過程中，有些區(qū)域是必須繞開的，這些必須繞開的區(qū)域我們稱為障礙區(qū)域。表1給出了若干個(gè)可能的用戶的地址的橫縱坐標(biāo)，可能的用戶的含義是：如果用戶的地址不在障礙區(qū)域內(nèi)，那么該用戶就是需要使用天然氣的用戶（即有效用戶），否則如果用

2、戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。表2表5是分別是4個(gè)障礙區(qū)域必須要覆蓋的點(diǎn)的坐標(biāo)，而對(duì)應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋的點(diǎn)的最小凸集。⑴請(qǐng)您判定表1中那些用戶為有效用戶。⑵請(qǐng)您設(shè)計(jì)一個(gè)算法將有效用戶連接起來，并且連接的距離總和最小。表1：若干個(gè)可能的用戶的地址的橫縱坐標(biāo)可能的用戶的序號(hào)可能的用戶橫坐標(biāo)可能的用戶縱坐標(biāo)可能的用戶的序號(hào)可能的用戶橫坐標(biāo)可能的用戶縱坐標(biāo)195.012958.279226

3、20.276597.0845223.113942.34962719.872299.0083360.684351.55122860.379278.8862448.598233.39512927.218843.8659589.129943.29073019.881449.8311676.209722.5950311.527421.3963745.646857.98073274.678664.349281.850476.03653344.50

4、9632.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

5、.213793.33801640.570656.78294183.811868.33321793.547079.4211421.964021.25601891.69045.91834368.127783.92381941.027060.28694437.948162.87852089.36505.02694583.179613.3773215.789141.53754650.281320.71332235.286830.49994770