西工大數(shù)模競賽B題公園道路設(shè)計(jì)論文答案

裝訂線“工大出版社杯”第十三屆西北工業(yè)大學(xué)數(shù)學(xué)建模競賽暨全國大學(xué)生數(shù)學(xué)建模競賽選拔賽題目B題密封號(hào)2012年5月2日剪切線密封號(hào)2012年5月2日理學(xué)院第182隊(duì)隊(duì)員1隊(duì)員2隊(duì)員3姓名杜雅麗賈天一潘琦明班級(jí)110210021102100211021002裝訂線公園內(nèi)新修道路路徑設(shè)計(jì)問題摘要本題討論的是公園內(nèi)道路設(shè)計(jì)最優(yōu)化問題，即在公園的任意兩個(gè)入口之間的最短道路不大于兩點(diǎn)連線的1.4倍的前提下，使得新修路的總路程最短，并繪出相應(yīng)的道路設(shè)計(jì)圖。由于公園的四周默認(rèn)存在已經(jīng)修好的路，因此先利用公園四周的路找出不滿足題意條件的路徑，以這些路徑為主要研究對(duì)象，根據(jù)題目的具體條件找出最優(yōu)建設(shè)路徑。對(duì)于4個(gè)交叉點(diǎn)已經(jīng)確定的問題，先將包括入口在內(nèi)的12個(gè)點(diǎn)構(gòu)成完全圖，根據(jù)完全圖的鄰接矩陣，用Kruskal算法，生成最小生成樹。再在此基礎(chǔ)上，利用Floyd算法，將不符合條件的路徑進(jìn)行刪除或替換，并依據(jù)總路程最短的原則，找出最優(yōu)解。根據(jù)逐步逼近的算法，可求得優(yōu)化后所得的最后結(jié)果，即是新修路總長為394.5米。在最后的模型討論中，通過進(jìn)一步假設(shè)，可求得進(jìn)一步最優(yōu)解為351.9米。針對(duì)可以任意修建道路的情形，本文從0開始逐步增加公園內(nèi)部交叉點(diǎn)的數(shù)目，發(fā)現(xiàn)至少有2個(gè)交叉點(diǎn)才能滿足題中所給前提條件。本文先找出2個(gè)交叉點(diǎn)（）情況下的最優(yōu)解，修路總長為375.3米。通過添加交叉點(diǎn)來對(duì)它進(jìn)行優(yōu)化，得到3個(gè)交叉點(diǎn)時(shí)的最優(yōu)解為361.6米。最后，通過交替迭代優(yōu)化算法，控制一部分點(diǎn)，改變其他點(diǎn)的位置，找出最終最優(yōu)解為327.5米。對(duì)于有湖存在的問題，根據(jù)假設(shè)，湖邊的道路距離不計(jì)入新修建道路的總長，因此在第二問的基礎(chǔ)上，利用湖邊的道路對(duì)道路修建方案進(jìn)行進(jìn)一步優(yōu)化，再次利用交替迭代優(yōu)化算法，逐步求解得到最終結(jié)果297.68米。關(guān)鍵詞：交替迭代優(yōu)化法Kruskal局部優(yōu)化貪婪算法Floyd算法目錄TOC\o"1-3"\h\u一、問題重述1二、問題分析 1三、符號(hào)說明與模型假設(shè) 23.1符號(hào)說明 23.2模型假設(shè) 3四、模型的建立與求解 34.1問題一的模型與解答 34.1.1模型的建立 34.1.2模型的求解 34.2問題二的模型與解答 64.2.1模型的建立 64.2.2模型的求解 74.3問題三的模型與解答 124.3.1模型的建立 124.3.2模型的求解 12五、模型的擴(kuò)展和討論 14六、模型評(píng)價(jià) 15七、參考文獻(xiàn) 16八、程序附錄 168.1附錄1求最小生成樹的克魯斯卡爾算法 168.2附錄2求解問題二兩個(gè)交叉點(diǎn)的源程序 188.3附錄3問題二交替迭代求最優(yōu)解的源程序 218.4附錄4求解問題三的源程序 23一、問題重述現(xiàn)在要修建一個(gè)有8個(gè)入口的公園，即確定公園入口與園內(nèi)交叉點(diǎn)的適當(dāng)連線，使得公園的任意兩個(gè)入口相連，但需滿足道路總長度和最小，而且任意的兩個(gè)入口之間的最短道路長不大于兩點(diǎn)連線的1.4倍。同時(shí)公園四周的邊上存在已經(jīng)建好的道路，且不計(jì)入道路總長。我們將主要設(shè)計(jì)對(duì)象假設(shè)為一個(gè)長200米，寬100米的矩形公園。我們要做的有以下三項(xiàng)工作：1、假定公園內(nèi)確定要使用4個(gè)道路交叉點(diǎn)為：A(50,75)，B(40,40)，C(120,40)，D(115,70）。問如何設(shè)計(jì)道路可使公園內(nèi)道路的總路程最短。建立模型并給出算法。畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。2、現(xiàn)在公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最少。建立模型并給出算法。給出道路交叉點(diǎn)的坐標(biāo)，畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。3、若公園內(nèi)有一條矩形的湖，新修的道路不能通過，但可以到達(dá)湖四周的邊，以此為前提，重復(fù)完成上一問題中的任務(wù)。二、問題分析本題是一個(gè)道路設(shè)計(jì)的最優(yōu)化的問題，即是如何設(shè)計(jì)路徑使公園內(nèi)部新修路總長最小，但要滿足以下兩個(gè)控制條件：任兩個(gè)入口連通；任兩個(gè)入口的最短路徑不超過其直線距離的1.4倍。由于題設(shè)中說明公園四周存在修好的道路且允許通行，我們先利用四周道路，找出經(jīng)過這些道路不能滿足條件的路徑，通過計(jì)算我們得出，，，，，，，，，這10條邊不滿足題意條件，在后續(xù)的問題中我們可將其作為主要條件，主要考慮這些路徑，不考慮其他路徑，這樣就可以使問題簡化，然后根據(jù)各個(gè)問題的具體要求，進(jìn)行求解。三、符號(hào)說明與模型假設(shè)3.1符號(hào)說明，公園的8個(gè)入口；，公園8個(gè)入口及內(nèi)部所設(shè)的m=n-8個(gè)交叉點(diǎn)依次編號(hào)。m，公園內(nèi)交叉點(diǎn)數(shù)目；，公園內(nèi)部修建道路總長。條件，控制條件，即任兩入口之間的最短路徑不大于其直線距離的1.4倍；條件，控制條件，即公園中新修路的總路程最短。D=，圖中第i個(gè)和第j個(gè)點(diǎn)之間的直線距離。為控制矩陣，即為了保證設(shè)計(jì)路線中兩入口間最短路徑長度小于其直線距離1.4倍。S=，S為最短路徑矩陣，元素表示在設(shè)計(jì)路徑中第i和第j個(gè)點(diǎn)間（n個(gè)入口點(diǎn)）最短路徑。，引入0-1矩陣；其中。是表征圖中n個(gè)點(diǎn)之間關(guān)系的鄰接矩陣，借助距離矩陣,有。3.2模型假設(shè)1、假設(shè)所有點(diǎn)間道路均修建為直線；2、交叉點(diǎn)的修建不影響道路總長；3、對(duì)于第三問，假設(shè)湖的四周已有修建好的道路，且不計(jì)入新修建道路的總長。四、模型的建立與求解4.1問題一的模型與解答4.1.1模型的建立已確定有4個(gè)交叉點(diǎn)要使用，可構(gòu)造一個(gè)點(diǎn)集。現(xiàn)在需要建立連通網(wǎng)，其中網(wǎng)的頂點(diǎn)表示8個(gè)入口點(diǎn)及4個(gè)交叉點(diǎn)，邊表示兩點(diǎn)之間的連線，賦予邊的權(quán)值表示相應(yīng)的直線距離。由于在此實(shí)際問題中，允許有連通分量，即環(huán)路的存在，因此我們不能直接通過構(gòu)造最小生成樹來求解最小路徑。但鑒于直接求解最優(yōu)解算法的復(fù)雜性，我們引用了一種直觀快捷的問題求解方法：貪婪算法。根據(jù)貪婪算法，我們將問題的求解分為3步：首先不考慮網(wǎng)中環(huán)路的存在，構(gòu)造最小生成樹；再利用Floyd算法計(jì)算出任意兩點(diǎn)之間的最短路徑，做出最短路徑矩陣，檢驗(yàn)是否滿足條件，若不滿足，繼續(xù)尋找；若滿足，執(zhí)行下一步。最后進(jìn)行邊的刪除和替換（此時(shí)可以有環(huán)路的存在），使得任意點(diǎn)間最短路徑滿足不超過直線距離1.4倍的要求。根據(jù)實(shí)際問題的要求，網(wǎng)中可以刪除和替換的邊并不多，因此利用窮舉法可以逐步逼近得到最優(yōu)解.4.1.2模型的求解現(xiàn)有，表示入口與交叉點(diǎn)構(gòu)成的點(diǎn)集，坐標(biāo)分別為接下來我們分3步對(duì)此模型進(jìn)行求解：1）利用MATLAB，根據(jù)克魯斯卡爾（Kruskal）算法，我們求得了最小生成樹（程序見附錄），為了直觀的顯示，我們做出如下反應(yīng)網(wǎng)中各點(diǎn)是否有道路連接的X矩陣（0-1）矩陣，其中0表示對(duì)應(yīng)兩點(diǎn)之間沒有連線，1則表示兩點(diǎn)之間有連線；；同時(shí)利用MATLAB繪出如下可能的道路設(shè)計(jì)圖：圖4-1對(duì)應(yīng)最小生成樹的可能道路設(shè)計(jì)圖針對(duì)上面在假設(shè)無環(huán)路存在條件下得出的道路設(shè)計(jì)圖，用Floyd算法進(jìn)行了如下檢驗(yàn)：先計(jì)算出已有條件下8個(gè)入口最短路徑矩陣如下：并與事先已求得的控制矩作比較，發(fā)現(xiàn)部分入口間最短路徑不滿足條件，如下表中突出顯示數(shù)據(jù)（由于這是一個(gè)無向圖，因此下三角數(shù)據(jù)不予列出）：A1A2A3A4A5A6A7A8A103014023024015513055A2011020027018516075A3090220295270185A40130215140275A5085110195A6025110A7085A80表4-1最小生成樹對(duì)應(yīng)最短路徑不滿足條件的路徑由于墻的存在，入口間路徑長度已經(jīng)滿足條件。而且涉及到的路徑中可替換的邊是有限的，因此利用窮舉法，我們進(jìn)一步求出了滿足條件的近似最優(yōu)解，對(duì)應(yīng)道路設(shè)計(jì)圖如下：圖4-24個(gè)交叉點(diǎn)的最優(yōu)道路設(shè)計(jì)圖4.2問題二的模型與解答4.2.1模型的建立由于在公園里可以任意修建道路，但仍需滿足條件及條件，因此，我們需要對(duì)用到的交叉點(diǎn)的個(gè)數(shù)、位置這兩個(gè)因素進(jìn)行依次討論，確定應(yīng)修建交叉點(diǎn)的數(shù)目m，以及它們的坐標(biāo)。我們依次令m=0、1、2、3，分別進(jìn)行討論。當(dāng)交叉點(diǎn)數(shù)目較多，即m>=2時(shí)，求解全局最優(yōu)解時(shí)，考慮到問題的復(fù)雜性，通過控制局部變量，我們將求解若干部分的局部最優(yōu)解交替進(jìn)行來逼近全局最優(yōu)解。4.2.2模型的求解m=0時(shí)實(shí)現(xiàn)8個(gè)入口的連通，我們僅能依賴四周的圍墻。根據(jù)我們計(jì)算出的兩點(diǎn)之間最短路徑，與控制矩陣比較后，不符合條件的數(shù)據(jù)如下表顯示：P1P2P3P4P5P6P7P8P10.030.0259.8323.8203.2136.8161.832.0P20.0229.8293.8173.2106.8131.862.0P30.064.0117.4181.3206.3291.8P40.0181.4245.4270.4355.9P50.0124.8149.8235.3P60.025.0168.8P70.0193.8P80.0表4-2不添加交叉點(diǎn)時(shí)公園各入口的最短距離與1.4倍距離比較結(jié)果因此必須通過添加交叉點(diǎn)才能使得新修道路滿足條件.m=1時(shí)僅可在公園內(nèi)建立一個(gè)交叉點(diǎn)。根據(jù)條件，我們可繪出橢圓來尋找交點(diǎn)的可能存在區(qū)域。分別以入口、和、為橢圓的焦點(diǎn)，以1.4倍焦距作為長半軸，繪出如下橢圓。根據(jù)橢圓的性質(zhì)易知，左邊灰色區(qū)域是使、最短路徑滿足條件的交叉點(diǎn)可能存在區(qū)域，右邊灰色區(qū)域是使、最短路徑滿足條件的交叉點(diǎn)可能存在區(qū)域，圖形如下：圖4-3繪出的橢圓但它們并無交集，故易知，一個(gè)交叉點(diǎn)的情況也不能滿足條件，因此仍須繼續(xù)添加交叉點(diǎn)。m=2時(shí)為了使問題簡化，求解方便，我們先假設(shè)路徑以及存在，然后考慮點(diǎn)集。在確定有2個(gè)交叉點(diǎn)的情況下，設(shè)為和，我們用C++語言編程，采用逐步逼近及窮舉的方法，尋找到了使得路徑之和滿足條件的兩點(diǎn),坐標(biāo)為，最短路徑。下面是對(duì)C++編程思想的簡單介紹（具體程序見附錄2）：建立4個(gè)for循環(huán)，分別以作為循環(huán)變量，以5為單位進(jìn)行變化；先讓N的縱坐標(biāo)由100減到0,找到的最佳位置，再依次讓N的橫坐標(biāo)由200減到0，M的縱坐標(biāo)由0加到100，M的橫坐標(biāo)由0加到200，找到兩點(diǎn)，此時(shí)最短路徑；采用逐步逼近的方法，以上面已求得的點(diǎn)為基礎(chǔ)，縮小尋找范圍。以1為單位進(jìn)行坐標(biāo)加減，讓N的縱坐標(biāo)由55加到65,找到的最佳位置，再依次讓N的橫坐標(biāo)由100加到110，M的縱坐標(biāo)由50加到60，M的橫坐標(biāo)由60加到70，找到兩點(diǎn)，此時(shí)最短路徑；考慮到這是一個(gè)實(shí)際問題，再縮小尋找范圍，對(duì)的長度的影響幅度在米以內(nèi)，故不再繼續(xù)尋找，因此求得的兩個(gè)交叉點(diǎn)時(shí)坐標(biāo)為，作為最后結(jié)果。得到道路設(shè)計(jì)圖如下：圖4-42個(gè)交叉點(diǎn)時(shí)的最優(yōu)道路設(shè)計(jì)圖m=3時(shí)我們?cè)谠瓉?個(gè)點(diǎn)的基礎(chǔ)上進(jìn)行局部優(yōu)化，我們的優(yōu)化分為兩步：A)、由圖3中M和N點(diǎn)的位置，我們發(fā)現(xiàn)，，均要經(jīng)過路徑，因此我們要對(duì)和兩條路徑在滿足條件的前提下，進(jìn)行繼續(xù)優(yōu)化，用了與求解2個(gè)交叉點(diǎn)時(shí)相同的C++編程思想，求得了點(diǎn)。第一步優(yōu)化后的道路設(shè)計(jì)圖如下：圖4-53個(gè)交叉點(diǎn)時(shí)第一步優(yōu)化后的道路設(shè)計(jì)圖B）、在固定點(diǎn)的情況下，繼續(xù)運(yùn)用上面求解2個(gè)交叉點(diǎn)時(shí)逐步逼近的C++編程思想，重新對(duì)點(diǎn)進(jìn)行優(yōu)化,先將優(yōu)化算法的控制條件寫成表達(dá)式如下：記上一步中的、、、、的距離之和為,求得最后三點(diǎn)最優(yōu)位置為,最短距離。并用Floyd算法進(jìn)行檢驗(yàn)，滿足條件。繪出最優(yōu)道路設(shè)計(jì)圖如下：圖4-63個(gè)交叉點(diǎn)時(shí)第二步優(yōu)化的道路設(shè)計(jì)圖P1P2P3P4P5P6P7P8P10.0-12.0-56.0-31.5-28.2-0.01-10.7-12.8P2-12.00.0-44.0-21.4-34.5-49.4-33.7-3.3P3-56.0-44.00.0-15.8-27.8-30.5-33.8-41.7P4-31.5-21.4-15.80.0-2.1-26.4-135.1-7.2P5-28.2-34.5-27.8-2.10.0-34.0-44.0-3.1P6-0.01-49.5-30.5-26.4-34.00.0-10.0-5.9P7-10.7-33.7-33.8-135.1-44.0-10.00.0-20.9P8-12.8-3.3-41.7-7.2-3.1-5.9-20.90.0表4-3上圖設(shè)計(jì)方案的（滿足條件）從上表中我們可以看到其每個(gè)元素都是小于0，即滿足題意條件。4.3問題三的模型與解答4.3.1模型的建立現(xiàn)在由于公園內(nèi)有一個(gè)矩形的湖，新修的道路不能通過，故需對(duì)問題二中的道路設(shè)計(jì)進(jìn)行改進(jìn)來滿足新的要求。我們選擇對(duì)上一問題中存在兩個(gè)交叉點(diǎn)的道路設(shè)計(jì)方案進(jìn)行改進(jìn)。由于湖的邊可以利用且不計(jì)入道路總長度，因此將圖4-4中路徑和進(jìn)行優(yōu)化，如圖，當(dāng)矩形湖的邊、、存在交點(diǎn)時(shí)可使新修建總路程優(yōu)化最短。設(shè)存在點(diǎn)、、，現(xiàn)需解決的問題是求得此3點(diǎn)的最優(yōu)位置，并求得最優(yōu)距離。4.3.2模型的求解我們?nèi)詫?yōu)化的過程分為兩步：利用條件作為限制條件，條件作為控制條件，通過在湖的三條邊上不斷變化位置，我們可以找到交點(diǎn)、、的最優(yōu)位置，坐標(biāo)分別為。求得總路程=304.684，得到優(yōu)化后圖形如下：圖4-7第三題時(shí)第一步優(yōu)化的道路設(shè)計(jì)圖現(xiàn)在進(jìn)行進(jìn)一步的優(yōu)化，保持交點(diǎn)、、不動(dòng)，改變點(diǎn)的位置，利用解決問題二時(shí)確定兩個(gè)交叉點(diǎn)時(shí)的算法思想，最后得到結(jié)果新修建總路程=297.68米。圖4-8第三題第二步優(yōu)化的道路設(shè)計(jì)圖P1P2P3P4P5P6P7P8P10.00-12.00-56.00-31.54-23.93-0.02-10.70-12.81P2-12.000.00-44.00-21.36-26.83-30.02-14.24-3.26P3-56.00-44.000.00-0.05-18.86-16.01-19.29-41.72P4-31.54-21.36-0.050.00-2.08-26.37-135.1-7.18P5-23.93-26.83-18.86-2.080.00-34.00-44.00-3.11P6-0.02-30.02-16.01-26.37-34.000.00-10.00-5.87P7-10.70-14.24-19.29-135.1-44.00-10.000.00-20.93P8-12.81-3.26-41.72-7.18-3.11-5.87-20.930.00表4-4上圖設(shè)計(jì)方案的矩陣后的結(jié)果五、模型的擴(kuò)展和討論由于問題一中確定使用四個(gè)交叉點(diǎn)，在第一次的求解中，我們考慮了只存在四個(gè)點(diǎn)的情況，現(xiàn)在根據(jù)問題二及問題三的加點(diǎn)優(yōu)化模型，對(duì)問題一附近的區(qū)域用條件進(jìn)行限制，找出滿足條件的最優(yōu)解。具體通過C語言編程實(shí)現(xiàn)。加入的點(diǎn)的坐標(biāo)為E（115，95）F（158,22）.最優(yōu)距離為351.895.圖5-1對(duì)第一題進(jìn)一步優(yōu)化的道路設(shè)計(jì)圖P1P2P3P4P5P6P7P8P10.00-12.00-56.00-31.54-15.28-4.7821.09-12.81P2-12.000.00-44.00-21.36-18.18-34.78-19.00-3.26P3-56.00-44.000.00-15.79-24.16-12.49-15.77-41.72P4-31.54-21.36-15.790.00-2.08-26.37-135.1-7.18P5-15.28-18.18-24.16-2.080.00-34.00-44.00-3.11P6-4.78-34.78-12.49-26.37-34.000.00-10.00-5.87P721.09-19.00-15.77-135.1-44.00-10.000.00-20.93P8-12.81-3.26-41.72-7.18-3.11-5.87-20.930.00表5-1上圖設(shè)計(jì)方案的矩陣比較結(jié)果六、模型評(píng)價(jià)本文是在任意的兩個(gè)入口之間的最短道路長不大于兩點(diǎn)連線的1.4倍的前提下，考慮總的道路長度和最小。建立了一個(gè)逐步逼近最優(yōu)解的模型，通過計(jì)算機(jī)編程窮舉其所有可能的點(diǎn)來實(shí)現(xiàn)的。6.1模型優(yōu)點(diǎn)相對(duì)于整體考慮問題所帶來的難度來說，進(jìn)行局部之間的交替優(yōu)化可簡化問題。充分利用了公園四周的邊，使得總的道路長度最小。對(duì)于第一題，我們?cè)谝呀?jīng)得到結(jié)果的基礎(chǔ)上，進(jìn)一步通過對(duì)局部的計(jì)算，得到更優(yōu)解。6.2模型不足對(duì)局部的點(diǎn)進(jìn)行交替來求最優(yōu)解，雖然簡化了問題的難度，但是計(jì)算量龐大，使用C語言編程過于繁雜，增加了勞動(dòng)量。局部最優(yōu)化處理只能無限逼近全局的最優(yōu)解，但無法證明我們所得結(jié)果是最優(yōu)解。七、參考文獻(xiàn)[1]姜啟源、謝金星、葉俊.數(shù)學(xué)模型[M]（第三版）.北京：高等教育出版社，2003.8.[2]趙靜、但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（第三版）.北京：高等教育出版社，2008.1.[3]孫蓬.MATLAB基礎(chǔ)教程.北京：清華大學(xué)出版社，2011.10.[4]嚴(yán)蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社，2009.7.八、程序附錄8.1附錄1求最小生成樹的克魯斯卡爾算法functionE=Kruskal(w)%圖論最小生成樹Kruskal避圈算法(使用時(shí)根據(jù)題目修改w和n)%w為鄰接矩陣w=xlsread('distance.xls')[m,n]=size(w);k=1;fori=1:n-1forj=i+1:nifw(i,j)~=0x(1,k)=w(i,j);%記錄邊x(2,k)=i;%記錄起點(diǎn)x(3,k)=j;%記錄終點(diǎn)k=k+1;endendendk=k-1;%統(tǒng)計(jì)邊數(shù)k為邊數(shù)%步驟一%冒泡法給邊的大小排序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矩陣的第一行記錄最小生成樹的邊長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:k%步驟四ifb==n-1%如果樹中邊數(shù)達(dá)到n-1break%算法終止end%步驟二ifl(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è)以避圈endendendEndE8.2附錄2求解問題二兩個(gè)交叉點(diǎn)的源程序求解問題二中兩個(gè)交叉點(diǎn)時(shí)點(diǎn)最優(yōu)位置的C++源程序：#include<iostream>//兩個(gè)交叉點(diǎn)#include<cmath>usingnamespacestd;intmain(){ doubleA[6][2],D[2][6]; A[0][0]=20; A[0][1]=0; A[1][0]=50; A[1][1]=0; A[2][0]=160; A[2][1]=0; A[3][0]=120; A[3][1]=100; A[4][0]=35; A[4][1]=100; A[5][0]=10; A[5][1]=100; doubleB[2][2],B0[2][2]; doubled15,d015,d16,d016,d25,d025,d26,d026,d27,d027,d35,d035,d36,d036,d37,d037; d015=141.421;d016=101.119;d025=122.066;d026=101.119;d027=107.703;d035=107.703;d036=160.078;d037=180.278; B[0][0]=65; B[0][1]=55; B[1][0]=105; B[1][1]=60; doublek1,k2,k3,k4; doubles0=500,s=0; doublem;for(k1=-10;k1<=10;k1=k1+1) { for(k2=-10;k2<=10;k2=k2+1) { for(k3=-10;k3<=10;k3=k3+1) { for(k4=-10;k4<=10;k4=k4+1) { D[0][1]=sqrt((B[0][0]+k1-A[1][0])*(B[0][0]+k1-A[1][0])+(B[0][1]+k2-A[1][1])*(B[0][1]+k2-A[1][1])); D[0][0]=D[0][1]+30; D[0][2]=sqrt((B[0][0]+k1-A[2][0])*(B[0][0]+k1-A[2][0])+(B[0][1]+k2-A[2][1])*(B[0][1]+k2-A[2][1])); D[0][3]=sqrt((B[0][0]+k1-A[3][0])*(B[0][0]+k1-A[3][0])+(B[0][1]+k2-A[3][1])*(B[0][1]+k2-A[3][1])); D[0][4]=sqrt((B[0][0]+k1-A[4][0])*(B[0][0]+k1-A[4][0])+(B[0][1]+k2-A[4][1])*(B[0][1]+k2-A[4][1])); D[0][5]=D[0][4]+25; D[1][1]=sqrt((B[1][0]+k3-A[1][0])*(B[1][0]+k3-A[1][0])+(B[1][1]+k4-A[1][1])*(B[1][1]+k4-A[1][1])); D[1][0]=D[1][1]+30; D[1][2]=sqrt((B[1][0]+k3-A[2][0])*(B[1][0]+k3-A[2][0])+(B[1][1]+k4-A[2][1])*(B[1][1]+k4-A[2][1])); D[1][3]=sqrt((B[1][0]+k3-A[3][0])*(B[1][0]+k3-A[3][0])+(B[1][1]+k4-A[3][1])*(B[1][1]+k4-A[3][1])); D[1][4]=sqrt((B[1][0]+k3-A[4][0])*(B[1][0]+k3-A[4][0])+(B[1][1]+k4-A[4][1])*(B[1][1]+k4-A[4][1])); D[1][5]=D[1][4]+25;m=sqrt((B[0][0]+k1-B[1][0]-k3)*(B[0][0]+k1-B[1][0]-k3)+(B[0][1]+k2-B[1][1]-k4)*(B[0][1]+k2-B[1][1]-k4)); d15=D[0][0]+D[1][3]+m; d16=D[0][0]+D[0][4]; d25=D[0][1]+D[1][3]+m; d26=D[0][1]+D[0][4]; d27=D[0][1]+D[0][5]; d35=D[1][2]+D[1][3]; d36=D[1][2]+D[0][4]+m; d37=D[1][2]+D[0][5]+m; if(d15<=1.4*d015) if(d16<=1.4*d016) if(d25<=1.4*d025) if(d26<=1.4*d026) if(d27<=1.4*d027) if(d35<=1.4*d035) if(d36<=1.4*d036) if(d37<=1.4*d037) { s=d26+d35+m; if(s<s0) { s0=s; B0[0][0]=B[0][0]+k1; B0[0][1]=B[0][1]+k2; B0[1][0]=B[1][0]+k3; B0[1][1]=B[1][1]+k4; } } } } } } cout<<B0[0][0]<<","<<B0[0][1]<<endl; cout<<B0[1][0]<<","<<B0[1][1]<<endl;cout<<s0<<endl; return0;}8.3附錄3問題二交替迭代求最優(yōu)解的源程序問題二中交替迭代算法求最優(yōu)解的源程序：#include<stdio.h>#include<cmath>voidmain(){ doublemx=65,my=58,nx=107,ny=65,mn,m2,m6,n5,no,s0=255.738,ans,s=500;doubleX[2][2]; doubles12=30,s16=101.119,s15=141.421,s25=122.066,s26=101.119,s27=107.703,s36=160.078,s37=180.278,s35=107.703; doublep2x=50,p2y=0,p3x=160,p3y=0,pox=161,poy=30,p5x=120,p5y=100,p6x=35,p6y=100; doublek1,k2,k3,k4;doubleo3=30.017; doublemn0,m20,m60,n50,no0; inti,j; for(k1=-20;k1<=20;k1=k1+0.5) { for(k2=-20;k2<=20;k2=k2+0.5) { for(k3=-20;k3<=20;k3=k3+0.5) { for(k4=-20;k4<=20;k4=k4+0.5) { mn=sqrt((mx+k1-nx-k3)*(mx+k1-nx-k3)+(my+k2-ny-k4)*(my+k2-ny-k4)); m2=sqrt((mx+k1-p2x)*(mx+k1-p2x)+(my+k2-p2y)*(my+k2-p2y)); m6=sqrt((mx+k1-p6x)*(mx+k1-p6x)+(my+k2-p6y)*(my+k2-p6y)); n5=sqrt((nx+k3-p5x)*(nx+k3-p5x)+(ny+k4-p5y)*(ny+k4-p5y)); no=sqrt((nx+k3-pox)*(nx+k3-pox)+(ny+k4-poy)*(ny+k4-poy)); if(m6+mn+m2+n5+no<s0) { if(m2+mn+n5<1.4*s25) { if(o3+no+mn+m6<1.4*s36) { if(o3+no+mn+m6+25<1.4*s37) { if(m2+m6<1.4*s26) { if(m2+m6+25<1.4*s27) { if(o3+no+n5<1.4*s35) { if(s12+m2+m6<1.4*s16) { if(s12+m2+mn+n5<1.4*s15) { ans=mn+m6+m2+no+n5; if(ans<s) { s=ans; X[0][0]=mx+k1;X[0][1]=my+k2;X[1][0]=nx+k3; X[1][1]=ny+k4; mn0=mn; m20=m2; m60=m6; n50=n5; no0=no; } } } } } } } } } } } } } } printf("最小距離"); printf("%lf\n",s); printf("各個(gè)點(diǎn)對(duì)應(yīng)的距離mnm2m6n5no\n"); printf("%lf\n",mn0)