自來水管道的連接優(yōu)化問題

1、自來水管道的連接優(yōu)化問題摘要為了使自來水管道總長度最小，現(xiàn)我們考慮通過分兩步來解決。首先，先確定點是否屬于不可連接區(qū)域。我們分別通過點坐標轉(zhuǎn)換為極坐標后擴大區(qū)域再二維比大小、離散法分割區(qū)域后點坐標帶入比對、以及邊界限定后整體線性規(guī)劃的方法確定點是否處于區(qū)域中。最終考慮線性規(guī)劃法的精確度最高，得出第4、23、36、99點在不可連接區(qū)域內(nèi)。再參考網(wǎng)上資料考慮最小連接問題，剔除無效點后，對剩余點間距離以歐式距離賦值，通過不可連接區(qū)域的距離賦值為無窮，生成帶權(quán)鄰接矩陣，再使用kruskal算法解出最小生成樹，結(jié)果為653.0196。最后，對此最小生成樹結(jié)果進行優(yōu)化，考慮加入一點使得此值更小，于是利用循

2、環(huán)語句，將x=1100 ；y=1100共10000個整數(shù)點分別帶入，使之成為第97個點，利用上述算法重新生成新的帶權(quán)鄰接矩陣，再使用kruskal算法求得結(jié)果為642.1555。同理再從優(yōu)化矩陣中返回點，依次加入，作為第98個點，再求的結(jié)果為。，依次類推，可以找到最理想值。關(guān)鍵詞：長度最段；線性規(guī)劃；最小生成樹；極坐標；離散一、 問題的重述及分析1.1問題的重述：自來水是人們?nèi)粘Ｉ钪胁豢扇鄙俚纳钜兀欢詠硭芫W(wǎng)的組建卻有很多問題需要解決。一般來說，我們假設(shè)管網(wǎng)中任意兩個用戶之間存在直線段相連，但是在連接過程中，有些區(qū)域是必須繞開的，這些必須繞開的區(qū)域我們稱為障礙區(qū)域。表1給出了若干個可

3、能的用戶的地址的橫縱坐標，可能的用戶的含義是：如果用戶的地址不在障礙區(qū)域內(nèi)，那么該用戶就是需要使用自來水的用戶（即有效用戶），否則如果用戶的地址在障礙區(qū)域內(nèi)，那么該用戶就是無效用戶（即不要將該用戶連接在網(wǎng)絡(luò)中）。表2-表5是分別是4個障礙區(qū)域必須要覆蓋的點的坐標，而對應(yīng)障礙區(qū)域就是覆蓋這些要覆蓋的點的最小凸集。(1)請您判定表1中那些用戶為有效用戶。(2)請設(shè)計一個算法將有效用戶連接起來，并且連接的距離總和最小。1.2問題的分析：問題（1）：根據(jù)題目要求，我們需要對用戶的100個點位置進行評判，判斷其是否屬于可連接區(qū)域內(nèi)。我們考慮到區(qū)域具有不規(guī)則性，無法利用簡單的二維數(shù)值直接比較，于是考慮把區(qū)

4、域做適當放大，化為極坐標區(qū)域進行二維判斷。由于實際情況中，區(qū)域放大會有誤差，為提高精度，考慮將不可連接區(qū)域分割離散化，將離散出的小格視為點，判斷用戶情況。進而綜合上述兩種方案，進一步優(yōu)化，可利用線性規(guī)劃的方法，將邊界利用方程表示，以此更精確的限定區(qū)域。問題（2）：由題目，此題需同時考慮管道的經(jīng)濟成本（即連線的長度最短）和躲避不可連接區(qū)域這兩個問題，由于躲避不可連接區(qū)域為必須條件，所以我們考慮將整個區(qū)域自行分塊（按照處理的便利程度躲避不可連接區(qū)域），再利用最小生成樹來將各區(qū)域內(nèi)的點連上，再取相鄰兩區(qū)域的最小距離相連。由于此方案不夠自動化，需要人為分區(qū)，故我們考慮對全體點運用最小生成樹的方案，對不

5、可連接區(qū)域內(nèi)的距離設(shè)定為正無窮大，以此解決問題。二、 模型的前提假設(shè)1、假設(shè)任意兩個用戶之間可以用直線連接。2、假設(shè)用戶的面積可近似為點。3、假設(shè)障礙區(qū)域的邊界是標準的直線。4、文中給出所有點的坐標值準確無誤。5、以所有管道總距離最小為目的。6、假設(shè)所有有效用戶的自來水都得通過這個自來水管網(wǎng)供應(yīng)。三、 符號說明變量定義x用戶點的橫坐標y用戶點的縱坐標用戶點極坐標的角度值r用戶點極坐標的半徑值temp一乘一百的賦值矩陣四、 模型的建立與求解4.1問題一：4.1.1極坐標法模糊簡化區(qū)域由于區(qū)域大多不規(guī)則，利用2維坐標做簡單的直接限定（如x5等）使之成為方形區(qū)域的精確度過低，于是我們考慮利用極坐標法

6、表示現(xiàn)有坐標，并用形如扇面的區(qū)域來代替原區(qū)域，以求用直接限定的方法，確定點是否處于危險區(qū)域內(nèi)。首先繪出四個限定區(qū)域：（編程過程見附1） 分別討論每一個區(qū)域以區(qū)域一為例，將其邊界點坐標轉(zhuǎn)化為極坐標附2，轉(zhuǎn)化出的極坐標為=1.3275 0.8365 1.3373r =13.3085 26.0518 20.5581由圖像可知，此扇面區(qū)域的r坐標的區(qū)間為13.3085，26.0518，坐標區(qū)間為0.8365，1.3373，故此扇形區(qū)域可以覆蓋整個區(qū)域一，同理可找出其他三個區(qū)域的r坐標區(qū)間，和坐標區(qū)間區(qū)域24的r、坐標區(qū)間分別為：r251.9106，73.9211；20.5404，0.9174r388.

7、8363，104.8269；30.9075，1.0403r4106.3015，124.1974；40.6947，0.8709 用極坐標模糊障礙區(qū)域后，障礙區(qū)域變大，如圖所示：利用算法語句將100個標記點轉(zhuǎn)化為極坐標，并判斷其是否屬于此極坐標區(qū)域中附3。執(zhí)行結(jié)果如下:QW = 4 7 13 17 23 28 33 36 37 74 89 99將這12個點進行驗證，可知其中一部分點并不在區(qū)域內(nèi)，所以該方法誤差較大。4.1.2離散法分解區(qū)域：由于將原區(qū)域轉(zhuǎn)化成扇面區(qū)域產(chǎn)生了一定的誤差（由于扇面面積大于實際面積所致），故我們考慮將連續(xù)的整體面積離散化，通過分割來提高精度。 通過matlab的grid

8、on功能，我們得出了離散后的障礙區(qū)域圖形，圖中每個網(wǎng)格我們都可以用坐標表示出來，于是我們可以利用題設(shè)點坐標直接對應(yīng)到區(qū)域圖內(nèi)，利用直接觀察的辦法判斷其是否屬于障礙區(qū)域。顯然，網(wǎng)格劃分的越密，對于區(qū)域的限定就越準確，判斷結(jié)果也就越準確。但此方法，需要的精度太高，并非matlab可以達到，而且也不夠智能（需要人為界定），故我們提出對它的改進辦法。4.1.3線性規(guī)劃圈定區(qū)域：根據(jù)兩點式求直線的方法可求出每個障礙區(qū)域的邊界的直線方程，根據(jù)線性規(guī)劃的方法可知道障礙區(qū)域內(nèi)的點應(yīng)滿足的條件。然后用matlab軟件編程，首先產(chǎn)生一個一行一百列的零矩陣temp，然后采用for循環(huán)使得程序自動輸入每個點的坐標x,

9、y,接著判斷是否滿足在障礙區(qū)域二內(nèi)的條件，若滿足則不改變矩陣temp相應(yīng)位置的值，若不滿足則接著判斷是否在障礙區(qū)域一內(nèi)的條件，若滿足則不改變矩陣temp相應(yīng)位置的值，若不滿足則接著判斷是否在障礙區(qū)域三內(nèi)的條件，若滿足則不改變矩陣temp相應(yīng)位置的值，若仍不滿足則接著判斷是否在障礙區(qū)域四內(nèi)的條件，若滿足則不改變矩陣temp相應(yīng)位置的值，若還不滿足則將矩陣temp相應(yīng)位置的值改為1.最后尋找矩陣temp中為一的元素，將其列下標賦值給temp。執(zhí)行程序，最后所得到的temp的值就是無效用戶。區(qū)域內(nèi)的點應(yīng)滿足的條件 利用兩點式求直線方程，公示如下：y=b2-b1 a2-a1x+a1b2-a2b1a2-

10、b1障礙區(qū)域一為一三角形，區(qū)域內(nèi)的點應(yīng)滿足以下三個方程：0.4506*x+11.4720-y0-0.0522*x+20.2483-y0障礙區(qū)域二為一五邊形，區(qū)域內(nèi)的點應(yīng)滿足以下五個方程：0.2123*x+47.1579-y01.6865*x-16.3903-y0-0.5879*x+59.395-y04.9243*x-216.2150-y0障礙區(qū)域三為一三角形，區(qū)域內(nèi)的點應(yīng)滿足以下三個方程：1.4654*x+11.2402-y0-1.2860*x+140.3423-y0障礙區(qū)域四為一三角形，區(qū)域內(nèi)的點應(yīng)滿足以下三個方程：-2*x+255-y0-0.25*x+97.5-y0利用matlab語言編程

11、，帶入所有點求解附4判斷點是否在障礙區(qū)域內(nèi)：可判斷出編號為4,23,36,99的點在障礙區(qū)域內(nèi)，無效點的坐標為編號 橫坐標 縱坐標4.0000 48.5982 33.395123.0000 81.3166 87.436736.0000 41.8649 41.195399.0000 6.4781 17.0793 用matlab軟件根據(jù)點的坐標及障礙區(qū)域的邊長的直線方程可將所有用戶的情況表示出來，結(jié)果如下：4.2問題二：4.2.1限定區(qū)域的用戶最小連接：注：此部分參考學長論文，相同內(nèi)容不再贅述。為了求解最短路徑直接在平面內(nèi)通過求解障礙區(qū)域頂點與用戶點的直線方程篩選有效用戶之間的有效線段。構(gòu)造有效線

12、段的帶權(quán)臨接矩陣，將無效線段的距離賦值為無窮大。 利用帶權(quán)臨接矩陣，使用 Kruskal 算法解得最小連通圖，并解得最小連通距離設(shè)計程序執(zhí)行（建立兩個M文件附5）如下：距離為653.0196.附6 4.2.2對最小連接結(jié)果的優(yōu)化（加入一個點）：從圖中可看出為了躲避障礙區(qū)域程序所得路徑是不“自由”的所以不是最短的，容易想到沿著障礙區(qū)域走折線反而路徑更短。由此，考慮依次帶入平面內(nèi)的點。利用循環(huán)語句，我們考慮x=1100 ；y=1100共計一萬個整數(shù)點分別代入（由于計算機計算速度的限制，10000次帶入計算已經(jīng)很龐大了，故我們將精度定在整數(shù)位上），再次應(yīng)用最小生成樹的算法找出最短的路徑是：642.1

13、555 此點坐標為90 75 附7此圖為分別代入所有整數(shù)點作為第97個點后的最小生成樹距離（10000個點的最小值詳細結(jié)果矩陣見運行結(jié)果.txt）。局部放大后的引入一點后的最優(yōu)解用紅叉表示：4.2.2對最小連接結(jié)果的優(yōu)化（加入多個點）：在加入點90 75后，我們考慮再加入一點，使得結(jié)果進一步優(yōu)化，由上圖所示，縱坐標在653.0196以下的點共有659個附8，利用循環(huán)語句，分別在加入這659個點作為第98個點，所得最小生成樹結(jié)果為五、 優(yōu)缺點分析5.1.1關(guān)于極坐標法模糊簡化區(qū)域優(yōu)點：將橫縱坐標x,y轉(zhuǎn)化為極坐標，轉(zhuǎn)變思考問題的角度，若障礙區(qū)域為圓形或橢圓形，能夠使問題得到很好的簡化。缺點：極坐

14、標法模糊簡化區(qū)域增大了障礙區(qū)域的范圍，不能夠準確的判斷出有效用戶，結(jié)果使得無效用戶由4個增加到12個，誤差較大。5.1.2 關(guān)于離散法分解區(qū)域優(yōu)點：可以通過控制不同的精度精確地判斷點是否屬于區(qū)域內(nèi)。缺點：不夠自動化，需要人為的確定精度，和比較大小。 5.1.3線性規(guī)劃圈定區(qū)域：優(yōu)點：此方法簡單易懂，容易想到，用最基本的方法解決了問題。且用C語言編寫程序較為簡單，方便。缺點：當障礙區(qū)域較多或障礙區(qū)域的邊長較多時，需要求很多個障礙區(qū)域的邊界的直線方程，過程過于繁瑣，且所編寫的程序需要根據(jù)直線方程的變動而變動，不具有普遍性。未加入額外點的最小生成樹的優(yōu)缺點：優(yōu)點：用最小生成樹解決最短路問題，較為方便

15、缺點：某兩個有效用戶之間用通過障礙物的頂點的折線連接，而這 樣得到的水道管總長度更短。如圖所示： 很顯然，紅色連線短于黑色連線。六、 參考文獻 1譚浩強.C程序設(shè)計（第四版）.清華大學出版社，20102許麗佳，穆炯.MATLAB程序設(shè)計及應(yīng)用.清華大學出版社，20113薛定宇，陳陽泉.高等應(yīng)用數(shù)學問題的MATLAB求解. 清華大學出版社，2008七、 附表 附1：（1）區(qū)域一x = 3.2060 17.4571 4.7576 3.2060 y=12.9166 19.3377 20 12.9166y = 12.9166 19.3377 20.0000 12.9166 plot(x,y,k-)x

16、= 3.2060 17.4571 4.7576 3.2060 y=12.9166 19.3377 20 12.9166y = 12.9166 19.3377 20.0000 12.9166 plot(x,y,k-)（2）區(qū)域二 x=50 53.7465 46.9222 43.1123 33.3207 50x = 50.0000 53.7465 46.9222 43.1123 33.3207 50.0000 y=30 48.4490 57.1195 56.3187 39.8050 30y = 30.0000 48.4490 57.1195 56.3187 39.8050 30.0000 plot

17、(x,y,k-)（3）區(qū)域三： x=54.6982 53.7465 46.9222 54.6982x = 54.6982 53.7465 46.9222 54.6982 y=70 90 80 70y = 70 90 80 70 plot(x,y,k-)（4）區(qū)域四 x=90 80 70 90x = 90 80 70 90 y=75 95 80 75y = 75 95 80 75 plot(x,y,k-)附2：區(qū)域一 y=12.9166 19.3377 20.0000; x=3.2060 17.4571 4.7576; theta,r = cart2pol(x,y)theta = 1.3275

18、0.8365 1.3373r = 13.3085 26.0518 20.5581區(qū)域二y=30 48.4490 57.1195 56.3187 39.8050; x=50 53.7465 46.9222 43.1123 33.3207; theta,r = cart2pol(x,y)theta = 0.5404 0.7336 0.8831 0.9174 0.8738r = 58.3095 72.3602 73.9211 70.9258 51.9106區(qū)域三y=70 90 80; x=54.6982 53.7465 46.9222; theta,r = cart2pol(x,y)theta =

19、0.9075 1.0325 1.0403r = 88.8363 104.8269 92.7453區(qū)域四y=75 95 80; x=90 80 70; theta,r = cart2pol(x,y)theta = 0.6947 0.8709 0.8520r = 117.1537 124.1974 106.3015附3：Q=zeros(1,100);for i=1:100 thera=JI(i,1);r=JI(i,2);if(thera0.8365&thera13.3085&r0.5404&thera51.9106&r0.9075&thera88.8363&r0.6947&thera106.301

20、5&r0&1.6865*x-16.3903-y0&(-0.5879)*x+59.395-y0&4.9243*x-216.2150-y0)temp(i)=0;else if(0.4506*x+11.4720-y0&(-0.0522)*x+20.2483-y0)temp(i)=0;else if(1.4654*x+11.2402-y0&(-1.2860)*x+140.3423-y0)temp(i)=0;else if(-2)*x+255-y0&(-0.25)*x+97.5-y0)temp(i)=0;elsetemp(i)=1;endendendend附5：建立兩個M文件M文件一、questiond

21、ata=1.0000 95.0129 58.27922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0000 82.1407 52.982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0000 92.1813 78.332914.0000

22、 73.8207 68.084615.0000 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000 35.2868 30.499923.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20.2765 97.084527.0000 19.87

23、22 99.008328.0000 60.3792 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5994 72.663236.0000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2647 43.992440.0000 67.2137

24、 93.338041.0000 83.8118 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.8892 62.988849.0000 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000 68.2223 4.389553.0000 30.2764 2.

25、718554.0000 54.1674 31.268555.0000 15.0873 1.286356.0000 69.7898 38.396757.0000 37.8373 68.311658.0000 86.0012 9.284259.0000 85.3655 3.533860.0000 59.3563 61.239561.0000 49.6552 60.854062.0000 89.9769 1.576063.0000 82.1629 1.635564.0000 64.4910 19.007565.0000 81.7974 58.691866.0000 66.0228 5.758167.

26、0000 34.1971 36.756868.0000 28.9726 63.145169.0000 34.1194 71.763470.0000 53.4079 69.266971.0000 72.7113 8.407972.0000 30.9290 45.435573.0000 83.8496 44.182874.0000 56.8072 35.325075.0000 37.0414 15.360676.0000 70.2740 67.564577.0000 54.6571 69.921378.0000 44.4880 72.750979.0000 69.4567 47.838480.00

27、00 62.1310 55.484281.0000 79.4821 12.104782.0000 95.6843 45.075483.0000 52.2590 71.588384.0000 88.0142 89.284285.0000 17.2956 27.310286.0000 97.9747 25.476987.0000 27.1447 86.560388.0000 25.2329 23.235089.0000 87.5742 80.487290.0000 73.7306 90.839891.0000 13.6519 23.189492.0000 1.1757 23.931393.0000

28、 89.3898 4.975494.0000 19.9138 7.838495.0000 29.8723 64.081596.0000 66.1443 19.088797.0000 28.4409 84.386998.0000 46.9224 17.390099.0000 6.4781 17.0793100.0000 98.8335 99.4295data2=1 3.2060 12.91662 17.4571 19.33773 4.7576 20data3=1 50 302 53.7465 48.44903 46.9222 57.11954 33.3207 39.80505 43.1123 5

29、6.3187data4=1 54.6982 702 53.7465 903 46.9222 80data5=1 90 752 80 953 70 80M文件二、function r=line_cross(x1,y1,x2,y2,x3,y3,x4,y4)LD1x=min(x1,x2);LD1y=min(y1,y2); LD2x=min(x3,x4);LD2y=min(y3,y4); RU1x=max(x2,x1);RU1y=max(y2,y1); RU2x=max(x3,x4);RU2y=max(y3,y4); X=(RU1xLD2x)&(RU2xLD1x); Y=(RU1yLD2y)&(RU2

30、yLD1y); if X&Y M1=x3-x1,y3-y1;x2-x1,y2-y1; M2=x4-x1,y4-y1;x2-x1,y2-y1; M3=x1-x3,y1-y3;x3-x4,y3-y4; M4=x2-x3,y2-y3;x3-x4,y3-y4; P1=det(M1); P2=det(M2); P3=det(M3); P4=det(M4); Q1=P1*P2;Q2=P3*P4; if Q10&Q2x(1,j) a=x(1,i);x(1,i)=x(1,j);x(1,j)=a; a=x(2,i);x(2,i)=x(2,j);x(2,j)=a; a=x(3,i);x(3,i)=x(3,j);x

31、(3,j)=a; end end end R=zeros(1,n); for i=1:n l(i)=i; end EE(1,1)=x(1,1); EE(2,1)=x(2,1); EE(3,1)=x(3,1); a=min(l(x(2,1),l(x(3,1); l(x(2,1)=a;l(x(3,1)=a; b=1; R(1)=x(2,1); R(2)=x(3,1); c=2; for i=2:k if b=n-1 breakend O1=find(R=x(2,i); O2=find(R=x(3,i); size1=size(O1,2); size2=size(O2,2); if(size1=0&

32、size2=0) if l(x(2,i)=l(x(3,i); elseb=b+1;EE(1,b)=x(1,i); EE(2,b)=x(2,i); EE(3,b)=x(3,i); a=min(l(x(2,i),l(x(3,i); b1=max(l(x(2,i),l(x(3,i); S1=find(l=b1); len=size(S1,2); for j=1:len l(S1(j)=a; end end else if(size1=0&size2=0) R(c+1)=x(2,i); c=c+1; end if(size2=0&size1=0) R(c+1)=x(3,i); c=c+1; end i

33、f(size2=0&size1=0) R(c+1)=x(2,i); R(c+2)=x(3,i); c=c+2; end b=b+1;EE(1,b)=x(1,i); EE(2,b)=x(2,i); EE(3,b)=x(3,i); a=min(l(x(2,i),l(x(3,i); b1=max(l(x(2,i),l(x(3,i); S1=find(l=b1); len=size(S1,2); for j=1:len l(S1(j)=a; end end end EE; sum=0; for i=1:n-1 sum=sum+EE(1,i); end sumall=sumall,sum 附7data(

34、99,36,23,4,:)=;sumall1=1000;A=;for m=1:100for w=1:100a=97,m,w;data=data;a; datastill=data; ad_matrix=;sumall=; h,l=size(data); fori=1:hfor j=1:h ad_matrix(i,j)=(data(i,2)-data(j,2)2+(data(i,3)-data(j,3)2)(1/2); end end fori=1:hfor k=i+1:h x1=data(i,2);y1=data(i,3); x2=data(k,2);y2=data(k,3); r=line_

35、cross(x1,y1,x2,y2,3.2060 ,12.9166,17.4571,19.3377); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,17.4571 ,19.3377,4.7576 ,20); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,4.7576 ,20,3.2060 ,12.9166); if(r=0) ad_matrix(i,k

36、)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,50,30,53.7465,48.4490); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,53.7465,48.4490,46.9222,57.1195); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,46.9222,57.

37、1195,43.1123,56.3187); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,43.1123,56.3187,33.3207,39.8050);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,33.3207,39.8050,50,30); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue en

38、d r=line_cross(x1,y1,x2,y2,54.6982 ,70,53.7465 ,90); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,53.7465 ,90,46.9222 ,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,46.9222 ,80,54.6982 ,70);if(r=0)ad_matrix(i,k)=inf;ad_matri

39、x(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,90 ,75,80 ,95);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,80 ,95,70,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,70 ,80,90,75);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendendendW=ad_matrix; n=h; k=1; for i=1:n-1 for j=i+1:n if (W(i,j)=inf) x(1,k)=W(i,j); x(2,k)=i;