基于Floyd算法的道路優(yōu)化設(shè)計(jì)問題

數(shù)學(xué)建模基于Floyd算法的公園道路優(yōu)化設(shè)計(jì)問題小組編號(hào)：02小組成員：隊(duì)員1張聰-建模隊(duì)員2汪濤-建模隊(duì)員3胡娜-建模隊(duì)員4薛向龍-建模隊(duì)員5蔡詩(shī)聶-編程隊(duì)員6楊志誠(chéng)-編程 2023年7月21日基于Floyd算法的公園道路優(yōu)化設(shè)計(jì)問題摘要本文重要研究了以公園內(nèi)部道路修建為背景的途徑優(yōu)化問題。對(duì)于問題一，已知四個(gè)交叉點(diǎn)的情況下，考慮到邊沿道路不計(jì)入修建道路總長(zhǎng)的題目規(guī)定和最短道路長(zhǎng)不大于兩點(diǎn)連線1.4倍前提規(guī)定，首選邊沿途徑，將那些無(wú)需借助交叉點(diǎn)即可滿足1.4倍前提規(guī)定的點(diǎn)從考慮范圍內(nèi)剔除。然后對(duì)剩余不滿足條件的途徑運(yùn)用Kruskal算法，生成最小生成樹的途徑，再在此基礎(chǔ)上，運(yùn)用Floyd算法，找出其中不符合1.4倍約束的途徑的邊，綜合對(duì)其途徑進(jìn)行調(diào)整并將滿足條件的所有途徑的邊用窮舉法進(jìn)行篩選，最終選取最優(yōu)途徑，其總路程為393。對(duì)于問題二，我們?cè)诘谝粏柦Y(jié)果上進(jìn)行改善，運(yùn)用兩點(diǎn)之間線段最短原理將第一問最短途徑進(jìn)行優(yōu)化，然后引入費(fèi)馬點(diǎn)定義，通過數(shù)理計(jì)算分析，劃分三角形區(qū)域，建立非線性規(guī)劃模型進(jìn)行局部?jī)?yōu)化。遞增交叉點(diǎn)的個(gè)數(shù)，并在前一個(gè)交叉點(diǎn)的最優(yōu)途徑的基礎(chǔ)上對(duì)后一個(gè)交叉點(diǎn)的取點(diǎn)范圍進(jìn)行考量，用lingo對(duì)不同數(shù)目交叉點(diǎn)的情況下的最短途徑目的函數(shù)進(jìn)行規(guī)劃，并以1.4倍的數(shù)學(xué)關(guān)系作為約束條件，進(jìn)行局部最優(yōu)解逼近全局最優(yōu)解，最終擬定最優(yōu)交叉點(diǎn)個(gè)數(shù)為3個(gè)，坐標(biāo)分別為、、，計(jì)算出最短途徑。對(duì)于問題三，我們?cè)趯?duì)比道路穿過湖的情況下，考慮到湖邊的修路計(jì)算到總路程內(nèi)的情況，分析得到在以湖的頂點(diǎn)R2、R4為道路交叉點(diǎn)時(shí)比以湖邊其他點(diǎn)作為交叉點(diǎn)時(shí)的途徑要短，所以分別以湖的頂點(diǎn)R2、R4為道路交叉點(diǎn)時(shí)進(jìn)行討論，在問題二的最短途徑的基礎(chǔ)上建立非線性規(guī)劃模型，然后運(yùn)用費(fèi)馬點(diǎn)逐步進(jìn)行優(yōu)化，比較兩種不同交叉點(diǎn)的優(yōu)化模型情況，最終擬定出最優(yōu)方案下的四個(gè)交叉點(diǎn)的坐標(biāo)分別,,，計(jì)算出該情況下最優(yōu)路程長(zhǎng)為。關(guān)于模型的優(yōu)化，對(duì)于問題二，我們考慮到可以通過蒙特卡洛的方法對(duì)公園矩形區(qū)域范圍內(nèi)進(jìn)行撒點(diǎn)，并借用橢圓法來(lái)約束1.4倍的條件關(guān)系，此方法可以求出選擇不同數(shù)目交叉點(diǎn)時(shí)的最優(yōu)途徑，結(jié)果更精確，但是計(jì)算量大、程序運(yùn)營(yíng)緩慢。關(guān)鍵詞：Kruskal算法Floyd算法局部?jī)?yōu)化費(fèi)馬點(diǎn)非線性規(guī)劃一、問題重述為了美化校園環(huán)境，同時(shí)為學(xué)生提供更好的生活條件，西安某大學(xué)計(jì)劃建一個(gè)形狀為矩形或其他不規(guī)則圖形的公園。該公園計(jì)劃有若干個(gè)入口，讓任意兩個(gè)入口相連且任意的兩個(gè)入口之間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍。路線的選擇可以運(yùn)用公園四周的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng)。矩形公園相關(guān)數(shù)據(jù)為：長(zhǎng)200米，寬100米，1至8各入口的坐標(biāo)分別為：P1(20,0),P2(50,0),P3(160,0),P4(200,50),P5(120,100),P6(35,100),P7(10,100),P8(0,25)。圖1公園及入口示意圖我們的任務(wù)就是結(jié)合該公園已有的計(jì)劃，對(duì)其進(jìn)行合理的道路安排，建立相應(yīng)的數(shù)學(xué)模型，解決以下問題：1、在公園假定要使用A(50,75)，B(40,40)，C(120,40)，D(115,70）這4個(gè)點(diǎn)作為道路交叉點(diǎn)時(shí)，如何設(shè)計(jì)出新的道路在滿足1.4倍規(guī)定的前提下使公園內(nèi)道路總路程最短。2、在公園內(nèi)可以任意修建道路的情況下，如何擬定交叉點(diǎn)的個(gè)數(shù)及坐標(biāo)設(shè)計(jì)道路使其在滿足1.4倍條件下使總路程最少。3、在公園內(nèi)有一條矩形的湖的，新修的道路不能通過，但可以到達(dá)湖四周的邊的前提下，如何設(shè)計(jì)交叉點(diǎn)的個(gè)數(shù)及坐標(biāo)設(shè)計(jì)道路使其在滿足1.4倍條件下使總路程最少。注：以上問題中都規(guī)定公園內(nèi)新修的道路與四周的連接只能與8個(gè)路口相通，而不能連到四周的其它點(diǎn)。圖2有湖的示意圖二、問題分析本題是一個(gè)道路設(shè)計(jì)的最優(yōu)化的問題，即是如何設(shè)計(jì)途徑使公園內(nèi)部新修路總長(zhǎng)最小，但要滿足以下兩個(gè)控制條件：1、任意兩個(gè)入口連通；2、任意兩個(gè)入口的最短途徑不超過其直線距離的1.4倍。對(duì)于問題一，題中已給出A(50,75)，B(40,40)，C(120,40)，D(115,70）這4個(gè)點(diǎn)作為道路交叉點(diǎn)，由于題設(shè)中說明公園四周存在修好的道路且允許通行，所以我們先運(yùn)用四周道路，找出，，，，，，，，，這些沿邊道路不能滿足1.4倍關(guān)系的途徑。然后對(duì)剩余不滿足第2個(gè)控制條件的途徑運(yùn)用Kruskal算法，生成最小生成樹，再在此基礎(chǔ)上，運(yùn)用Floyd算法，找出其中不符合條件2的途徑用窮舉法進(jìn)行優(yōu)化。對(duì)于問題二，我們?cè)诘谝粏柦Y(jié)果上進(jìn)行改善，考慮到兩點(diǎn)之間線段最短原理我們將與、與直接相連。引入費(fèi)馬點(diǎn)定義，通過度析劃分三角形區(qū)域，建立非線性規(guī)劃模型進(jìn)行局部?jī)?yōu)化。假設(shè)公園內(nèi)有m個(gè)交叉點(diǎn)，從m=0開始，我們繼續(xù)討論m=1、m=2和m=3這三種情況，進(jìn)行局部最優(yōu)解逼近全局最優(yōu)解，最終擬定交叉點(diǎn)數(shù)及坐標(biāo)并求解出最短途徑。對(duì)于問題三，一方面考慮問題二中設(shè)計(jì)的道路是否不通過矩形湖，若不通過，則問題二的結(jié)果即為問題三的結(jié)果；否則，對(duì)問題二方案中穿過湖的道路進(jìn)行調(diào)整－將其調(diào)整為穿過湖的頂點(diǎn)。運(yùn)用費(fèi)馬點(diǎn)到三個(gè)頂點(diǎn)的距離最短，建立出相應(yīng)的非線性規(guī)劃模型，求出相應(yīng)的交叉點(diǎn)，然后再運(yùn)用費(fèi)馬點(diǎn)來(lái)進(jìn)行優(yōu)化，直到不能再優(yōu)化為止，最終可得到最優(yōu)方案。三、模型假設(shè)1、假設(shè)所有點(diǎn)間道路均修建為直線，且都在同一水平面內(nèi)；2、假設(shè)入口形狀與路寬忽略不計(jì)，即將入口抽象為點(diǎn)，道路抽象為線；3、假設(shè)交叉點(diǎn)位置的選取不受地理位置的限制，且交叉點(diǎn)的修建不會(huì)影響道路的總長(zhǎng)4、假設(shè)湖的四周沒有修建好的道路，若要沿湖則同樣需修建道路并計(jì)入道路總長(zhǎng)。四、符號(hào)說明符號(hào)說明點(diǎn)的坐標(biāo)點(diǎn)、間的距離點(diǎn)與點(diǎn)間的距離、、道路交叉點(diǎn)最優(yōu)路線長(zhǎng)度道路交叉點(diǎn)的個(gè)數(shù)五、模型的建立與求解5.1問題一的模型建立與求解由題所給出的條件可以看出，這與最短路問題聯(lián)系密切，于是考慮用Kruskal算法和Floyd算法來(lái)建立問題的模型。圖3、模型一流程圖5.1.1Kruskal算法描述： kruskal算法每次選擇n-1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小花費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不也許形成一棵生成樹。kruskal算法分e步，其中e是網(wǎng)絡(luò)中邊的數(shù)目。按花費(fèi)遞增的順序來(lái)考慮這e條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。算法環(huán)節(jié):（1）在公園的矩形區(qū)域內(nèi)的12個(gè)點(diǎn)中,運(yùn)用勾股定理算出任意兩點(diǎn)所構(gòu)成的各邊的權(quán)值。（2）逐步比較各邊的權(quán)值，依次選出構(gòu)成權(quán)值最小的邊的兩個(gè)點(diǎn)構(gòu)成連線，與此同時(shí)，運(yùn)用邊與邊之間不能構(gòu)成連線的條件，對(duì)權(quán)值盡也許小的邊逐步篩選。（3）根據(jù)選出的邊逐步構(gòu)成連線，生成無(wú)圈的最小樹。5.1.2Floyd算法描述：（1）從任意節(jié)點(diǎn)A到任意節(jié)點(diǎn)B的最短途徑有2種也許，1是直接從A到B，2是從A通過若干個(gè)節(jié)點(diǎn)X到B。（2）假設(shè)Dis(AB)為節(jié)點(diǎn)A到節(jié)點(diǎn)B的最短途徑的距離，對(duì)于每一個(gè)節(jié)點(diǎn)X，檢查Dis(AX)+Dis(XB)<1.4*Dis(AB)是否成立。（3）假如成立，證明從A到X再到B的途徑比A直接到B的途徑短，便設(shè)立Dis(AB)=Dis(AX)+Dis(XB)，這樣一來(lái)，當(dāng)遍歷完所有節(jié)點(diǎn)X，Dis(AB)中記錄的便是A到B的最短途徑的距離。基本環(huán)節(jié)：（1）運(yùn)用kruskal算法得到的最短途徑計(jì)算出兩點(diǎn)間的通過途徑的長(zhǎng)度和兩點(diǎn)間的徑直線段長(zhǎng)度；（2）判斷兩點(diǎn)間的徑直線段長(zhǎng)度是否滿足不大于兩點(diǎn)間的通過途徑的長(zhǎng)度1.4倍的關(guān)系；（3）若滿足此條件則擬定為最小生成樹；若不滿足此條件則顯示那條邊不符合。5.1.3算法求解結(jié)果通過數(shù)據(jù)分析發(fā)現(xiàn)部分入口間最短途徑不滿足1.4倍的關(guān)系條件，如表1中突出顯示數(shù)據(jù)（由于這是一個(gè)無(wú)向圖，因此下三角數(shù)據(jù)不予列出）：表1：入口間最短途徑（粗體表達(dá)不滿足條件的入口）0301402302401551305501102002701851607509022029527018501302151402750851101950251100850（1）運(yùn)用Kruskal算法生成最小生成樹的matlab程序，我們通過程序運(yùn)營(yíng)結(jié)果可以得到圖4的最短途徑：圖4、Kruskal算法生成的最小生成樹途徑（2）但是通過Floyd算法對(duì)所求得的最短途徑經(jīng)行1.4倍關(guān)系約束條件的檢查時(shí)得到之間最短途徑不滿足1.4倍關(guān)系。由圖4分析，運(yùn)用窮舉法對(duì)之間的所有途徑進(jìn)行計(jì)算，最后求得最優(yōu)途徑如圖5所示。圖5、Folyd篩選后運(yùn)用窮舉法得到的最優(yōu)途徑經(jīng)計(jì)算，在滿足題目1.4倍規(guī)定且使用A(50,75)，B(40,40)，C(120,40)，D(115,70）這4個(gè)點(diǎn)作為道路交叉點(diǎn)時(shí)，公園內(nèi)道路總路程最短距離為393。5.2問題二的模型建立與求解由于問題二中在公園內(nèi)可以任意修路，交叉點(diǎn)個(gè)數(shù)無(wú)限制，結(jié)合問題一的分析及求解結(jié)果知，兩條道路必須修建，且在滿足題目規(guī)定下使修路的總路程最短的基礎(chǔ)上對(duì)交叉點(diǎn)的個(gè)數(shù)以及坐標(biāo)位置進(jìn)行優(yōu)化。5.2.1一個(gè)交叉點(diǎn)的情況問題一中已經(jīng)驗(yàn)證在無(wú)交叉點(diǎn)的前提下不能滿足題目的規(guī)定，下面我們討論一個(gè)交叉點(diǎn)的情況。在問題一的基礎(chǔ)上根據(jù)兩點(diǎn)之間線段最短原理將和直接連接，所得結(jié)果如圖6所示：圖6、無(wú)道路交叉點(diǎn)的優(yōu)化圖對(duì)圖中路線進(jìn)行1.4倍驗(yàn)證得到不滿足題目規(guī)定，所以我們考慮到在點(diǎn)將、、三點(diǎn)所構(gòu)成三角形中尋找一個(gè)局部最優(yōu)點(diǎn)來(lái)滿足的1.4倍關(guān)系。此處為了找到這個(gè)最優(yōu)點(diǎn)，由于其它點(diǎn)間距離固定，只需考慮、、之間的距離關(guān)系，因此我們引入費(fèi)馬點(diǎn)定義。定義：在幾何學(xué)中，費(fèi)馬點(diǎn)是位于三角形內(nèi)的一點(diǎn)，給定一個(gè)三角形△ABC的話，從費(fèi)馬點(diǎn)P到三角形的三頂點(diǎn)A、B、C的距離之和比其它點(diǎn)都要小。假如三角形的內(nèi)角所有小于120度則費(fèi)馬點(diǎn)存在，在、、所構(gòu)成三角形（如圖7）內(nèi)部必存在費(fèi)馬點(diǎn)。圖7、第一個(gè)道路交叉點(diǎn)的三角分割區(qū)域由于點(diǎn)在、、三點(diǎn)所構(gòu)成三角形內(nèi)部，且滿足費(fèi)馬點(diǎn)定義。設(shè)交叉點(diǎn)坐標(biāo)為，建立非線性優(yōu)化模型：目的函數(shù)：約束條件：運(yùn)用LINGO軟件求出最優(yōu)解（程序見附錄4）一個(gè)交叉點(diǎn)的坐標(biāo)為。計(jì)算得到局部最優(yōu)途徑，總的道路長(zhǎng)道路設(shè)計(jì)圖如圖8所示圖8、一個(gè)交叉點(diǎn)的道路分布5.2.2兩個(gè)交叉點(diǎn)的情況一個(gè)交叉點(diǎn)我們?cè)跐M足1.4倍的前提下求得了局部途徑最短，但是忽略了、、三點(diǎn)之間的最優(yōu)化問題。圖9、第二個(gè)道路交叉點(diǎn)的三角分割區(qū)域考慮兩個(gè)交叉點(diǎn)的情況，設(shè)第二個(gè)交叉點(diǎn)坐標(biāo)為，由于點(diǎn)在、、三點(diǎn)所構(gòu)成三角形內(nèi)部，且滿足費(fèi)馬點(diǎn)定義，由此建立非線性約束模型：目的函數(shù)：約束條件：運(yùn)用LINGO軟件求出最優(yōu)解（程序見附錄5）兩個(gè)交叉點(diǎn)坐標(biāo)分別為和。道路設(shè)計(jì)如圖10所示圖10、兩個(gè)交叉點(diǎn)的道路分布計(jì)算得到局部最優(yōu)途徑,總的道路長(zhǎng)。5.2.3三個(gè)交叉點(diǎn)的情況結(jié)合一個(gè)交叉點(diǎn)和兩個(gè)交叉點(diǎn)的局部?jī)?yōu)化情況，由圖。。。知在E、F、P5三點(diǎn)所構(gòu)成三角形內(nèi)部存在一個(gè)費(fèi)馬點(diǎn)，根據(jù)對(duì)區(qū)域的分割我們進(jìn)行總的優(yōu)化，建立如下非線性規(guī)劃模型：目的函數(shù)：約束條件：運(yùn)用LINGO軟件求出最優(yōu)解（程序見附錄6）三個(gè)交叉點(diǎn)坐標(biāo)分別為、、。道路設(shè)計(jì)圖如圖11所示圖11、三個(gè)交叉點(diǎn)的道路分布計(jì)算得到全局最優(yōu)途徑。對(duì)于更多交叉點(diǎn)的情況，我們將兩個(gè)交叉點(diǎn)和三個(gè)交叉點(diǎn)優(yōu)化后的最短途徑相比較得出三個(gè)交叉點(diǎn)的最短途徑和兩個(gè)交叉點(diǎn)的最短途徑相差不大，以此推測(cè)出四個(gè)甚至更多交叉點(diǎn)的設(shè)立并不能大幅度的優(yōu)化路線?？紤]到增長(zhǎng)交叉點(diǎn)對(duì)施工帶來(lái)的麻煩，以及給交通帶來(lái)不便利，所以于人性化角度設(shè)立3個(gè)交叉點(diǎn)比較合理。5.3問題三的模型建立與求解一方面，判斷問題二最終所修道路是否不通過湖泊，運(yùn)用MATLAB作出道路設(shè)計(jì)圖（見附錄9），如圖12所示：圖12判斷問題二的方案是否滿足新修道路不通過湖泊由圖12知，在問題二的新修道路方案中G-F穿過了湖泊，從而G-F需重新設(shè)計(jì)。若借助湖邊的道路來(lái)使G到達(dá)F，由假設(shè)若沿湖建路，則所修道路的長(zhǎng)度要計(jì)入路程總長(zhǎng)，故需四條直線才使G到達(dá)F，不符合兩點(diǎn)之間直線最短，故考慮借助湖的頂點(diǎn)R4、R2來(lái)使G到達(dá)F，同時(shí)G、F的位置也需調(diào)整。有兩種情況，G-R4-F，G-R2-F，現(xiàn)分別考慮這兩種情況。5.對(duì)于圖12，當(dāng)調(diào)整連接G-R4-F時(shí)，我們考慮到在到到R4之間，有費(fèi)馬點(diǎn)定義可知既為費(fèi)馬點(diǎn)，所以我們將點(diǎn)移動(dòng)到，所得道路如圖13所示。圖13以R4為交叉點(diǎn)的改善圖對(duì)調(diào)整后的路線用非線性規(guī)劃進(jìn)行優(yōu)化，優(yōu)化模型如下：目的函數(shù)：約束條件：運(yùn)用LINGO（程序見附錄7）可求出交叉點(diǎn)經(jīng)驗(yàn)證，所連之后的任意兩入口之間的最短道路長(zhǎng)全滿足不大于兩連線點(diǎn)之間的1.4倍。最短路長(zhǎng)為。道路設(shè)計(jì)圖如圖14所示。圖14以R4為交叉點(diǎn)的改善圖5.對(duì)于以R2為交叉點(diǎn)的途徑，我們對(duì)點(diǎn)和點(diǎn)繼續(xù)用費(fèi)馬點(diǎn)來(lái)進(jìn)行優(yōu)化，建立非線性規(guī)劃模型：目的函數(shù)：約束條件：運(yùn)用LINGO程序（見附錄8）可計(jì)算出調(diào)整后的交叉點(diǎn)G和交叉點(diǎn)F。經(jīng)驗(yàn)證，所連之后的任意兩入口之間的最短道路長(zhǎng)全滿足不大于兩連線點(diǎn)之間的1.4倍。最短路長(zhǎng)為360.5394。道路設(shè)計(jì)圖如圖15所示圖15以R2為交叉點(diǎn)的改善圖在圖15中，不存在三角形可繼續(xù)優(yōu)化，在此方案下，最短路程長(zhǎng)為360.5394。通過比較最短路程長(zhǎng)，最終選擇圖35作為最后方案，四個(gè)交叉點(diǎn)分別為,,,，總路程長(zhǎng)為。道路設(shè)計(jì)圖如圖15所示。六、模型的評(píng)價(jià)及推廣6.1模型優(yōu)點(diǎn)(1)對(duì)于問題一，在建立模型求解之前，一方面運(yùn)用邊沿道路不計(jì)入修建道路總長(zhǎng)的題目規(guī)定和最短道路長(zhǎng)不大于兩點(diǎn)連線1.4倍前提規(guī)定，將那些無(wú)需借助交叉點(diǎn)即可滿足1.4倍前提規(guī)定的點(diǎn)從考慮范圍內(nèi)剔除，將8個(gè)點(diǎn)之間的兩兩互連問題簡(jiǎn)化為十組點(diǎn)之間的連通問題，大大簡(jiǎn)化了題目。(2)對(duì)于問題二，從交叉點(diǎn)的個(gè)數(shù)出發(fā)，分情況進(jìn)行討論求解，既考慮多種情況，又減少了解題難度。（3）對(duì)于問題三，引入費(fèi)馬點(diǎn)大大減少了計(jì)算的繁雜性。6.2模型缺陷（1）問題二中采用局部最優(yōu)解逼近全局最優(yōu)解，存在誤差。（2）問題二及問題三沒有計(jì)算更多交叉點(diǎn)的情況。6.3模型推廣最短途徑問題是現(xiàn)實(shí)生活中常見問題，本題的實(shí)際情景為公園內(nèi)部建設(shè)道路。模型還可以推廣到求解運(yùn)送路線選擇問題，商業(yè)利潤(rùn)估算問題和生產(chǎn)生活各個(gè)方面，所以該模型的建立具有重要意義。七、參考文獻(xiàn)龔純，王正林.精通matlab最優(yōu)化計(jì)算.北京：電子工業(yè)出版社，2023.1司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用.北京：國(guó)防工業(yè)出版社，2023.8姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].北京：高等教育出版社，2023.8維基百科費(fèi)馬點(diǎn)薛金星，薛毅.優(yōu)化建模與LINDO/LINGO軟件.北京：清華大學(xué)出版社，2023.7趙繼俊,Lingo優(yōu)化技術(shù)與Matlab優(yōu)化工具箱[M].機(jī)械工業(yè)出版社，2023,201-212.八、附錄附錄1：各點(diǎn)之間的距離030140186.82141.42101.12100.5032.02300110158.11122.07101.12107.7055.90140110064.03107.70160.08180.28161.94186.82158.1164.03094.34172.41196.47201.56141.42122.07107.7094.34085110141.51101.12101.12160.08172.418502582.76100.50107.70180.28196.4711025075.6632.0255.90161.94201.56141.5182.760附錄2：?jiǎn)栴}一Kruskal算法程序functionE=Kruskal(w)%圖論最小生成樹Kruskal避圈算法%w為連接權(quán)矩陣[m,n]=size(w);%m為w行數(shù)，n為w列數(shù)k=1;fori=1:n-1forj=i+1:n%為了提高效率ifw(i,j)~=0x(1,k)=w(i,j);%記錄不為0的邊長(zhǎng)x(2,k)=i;%不為0的行數(shù)x(3,k)=j;%不為0的列數(shù)k=k+1;endendend%構(gòu)造x為不為0的元素的信息，涉及邊長(zhǎng)，所在列數(shù)，行數(shù)k=k-1;%記錄不為0的邊數(shù)%環(huán)節(jié)一%冒泡法完畢邊的從小到大排序fori=1:kforj=i+1:kifx(1,i)>x(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(3,j)=a;endendend%給各點(diǎn)標(biāo)號(hào)賦初值fori=1:nl(i)=i;end%初始時(shí)選e1加入集合EE(1,1)=x(1,1);%E矩陣的第一行記錄最小生成樹的邊長(zhǎng)E(2,1)=x(2,1);%E矩陣的第二行記錄邊的起點(diǎn)E(3,1)=x(3,1);%E矩陣的第三行記錄邊的終點(diǎn)a=min([l(E(2,1)),l(E(3,1))]);l(E(2,1))=a;l(E(3,1))=a;b=1;%記錄E中邊數(shù)fori=2:kifb==n-1%假如樹中邊數(shù)達(dá)成n-1break%算法終止endifl(x(2,i))~=l(x(3,i))%假如兩頂點(diǎn)標(biāo)號(hào)不同b=b+1;%將這條邊加入EE(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i);forj=1:n%對(duì)于所有頂點(diǎn)ifl(j)==max([l(E(2,b)),l(E(3,b))])%假如該頂點(diǎn)的標(biāo)號(hào),等于=,新加入邊中的頂點(diǎn)標(biāo)號(hào)較大的值l(j)=min([l(E(2,b)),l(E(3,b))]);%將其改為較小的那一個(gè)以避圈endendendend附錄3：?jiǎn)栴}一中Floyd算法程序：clc;n=12;a=zeros(n);a(1,2)=30;a(1,8)=32;a(1,2)=30;a(1,3)=140;a(2,10)=41;a(2,3)=100;a(3,4)=64;a(3,11)=57;a(5,6)=85;a(5,12)=30;a(6,7)=25;a(6,9)=29;a(9,10)=36;a(9,12)=65;a(11,12)=30;a(1,4)=230;a(1,5)=240;a(1,6)=155;a(1,7)=130;a(2,4)=200;a(2,5)=270;a(2,6)=185;a(2,7)=160;a(2,8)=70;a(3,5)=120;a(3,6)=295;a(3,7)=270;a(3,8)=180;a(4,5)=130;a(4,6)=215;a(4,7)=240;a(4,8)=270;a(5,8)=200;a(6,8)=115;a(7,8)=90;a=a+a';M=max(max(a))*n^2;%M為充足大的正實(shí)數(shù)a=a+((a==0)-eye(n))*M;path=zeros(n);fork=1:nfori=1:nforj=1:nifa(i,j)>a(i,k)+a(k,j)a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendenda,path附錄4:問題二中1個(gè)交叉點(diǎn)情況時(shí)的lingo程序:min=@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+@sqrt((x9-120)^2+(y9-100)^2)+16.0078*2+53.85165*2+32.01562*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)<=1.4*50.55937*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)<=1.4*61.03278*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+25<=1.4*53.85165*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)+30<=1.4*70.71068*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+30<=1.4*50.55937*2;20*x9+3*y9-1000>=0;-10*x9+7*y9+500>=0;y9>=0;y9<=100;附錄5:問題二中2個(gè)交叉點(diǎn)情況時(shí)的lingo程序:min=@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+@sqrt((x9-120)^2+(y9-100)^2)+@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-200)^2+(y10-50)^2)+@sqrt((x10-120)^2+(y10-100)^2)+16.0078*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)<=1.4*50.55937*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)<=1.4*61.03278*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+25<=1.4*53.85165*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)+30<=1.4*70.71068*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+30<=1.4*50.55937*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-120)^2+(y10-100)^2)<=1.4*53.85165*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-200)^2+(y10-50)^2)<=1.4*32.01562*2;20*x9+3*y9-1000>=0;-10*x9+7*y9+500>=0;5*x10-4*y10-800<=0;5*x10+2*y10-800>=0;5*x10+8*y10-1400<=0;y9>=0;y9<=100;y10>=0;y10<=100;附錄6:問題二中3個(gè)交叉點(diǎn)情況時(shí)的lingo程序:min=@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-200)^2+(y10-50)^2)+@sqrt((x11-x9)^2+(y11-y9)^2)+@sqrt((x11-120)^2+(y11-100)^2)+@sqrt((x11-x10)^2+(y11-y10)^2)+16.0078*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)<=1.4*50.55937*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)<=1.4*61.03278*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+25<=1.4*53.85165*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-120)^2+(y9-100)^2)+30<=1.4*70.71068*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x9-35)^2+(y9-100)^2)+30<=1.4*50.55937*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-120)^2+(y10-100)^2)<=1.4*53.85165*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x10-200)^2+(y10-50)^2)<=1.4*32.01562*2;@sqrt((x9-50)^2+(y9)^2)+@sqrt((x11-x9)^2+(y11-y9)^2)+@sqrt((x11-120)^2+(y11-100)^2)<=1.4*61.03278*2;@sqrt((160-x10)^2+(0-y10)^2)+@sqrt((x10-x9)^2+(y10-y9)^2)+@sqrt((35-x9)^2+(100-y9)^2)<=1.4*80.03905*2;30+@sqrt((x9-50)^2+(y9)^2)+@sqrt((x11-x9)^2+(y11-y9)^2)+@sqrt((x11-120)^2+(y11-100)^2)<=1.4*70.71068*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x11-x10)^2+(y11-y10)^2)+@sqrt((x11-120)^2+(y11-100)^2)+110<=1.4*90.13878*2;@sqrt((x10-160)^2+(y10)^2)+@sqrt((x11-x10)^2+(y11-y10)^2)+@sqrt((x11-120)^2+(y11-100)^2)<=1.4*53.85165*2;20*x9+3*y9-1000>=0;-10*x9+7*y9+500>=0;5*x10-4*y10-800<=0;5*x10+2*y10-800>=0;5*x10+8*y10-1400<=0;y9>=0;y9<=100;y10>=0;y10<=100;x11>=0;x11<=200;y11>=0;y11<=100;附錄7:問題三對(duì)過R4途徑的求解程序:min=@sqrt((x12-165)^2+(y12-70)^2)+@sqrt((x12-160)^2+(y12-0)^2)+@sqrt((x12-200)^2+(y12-50)^2);@sqrt((x12-160)^2+(y12)^2)+@sqrt((x12-165)^2+(y12-70)^2)+@sqrt((120-165)^2+(100-70)^2)<=1.4*107.7033;@sqrt((x12-160)^2+(y12)^2)+@sqrt((x12-165)^2+(y12-70)^2)+@sqrt((120-165)^2+(100-70)^2)+85<=1.4*160.07981;@sqrt((x12-160)^2+(y12)^2)+@sqrt((x12-165)^2+(y12-70)^2)+@sqr