通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題

1、通信網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題摘要本文針對(duì)通訊網(wǎng)絡(luò)設(shè)訃問(wèn)題，使用圖論中最小生成樹法、節(jié)點(diǎn)排除法、網(wǎng)絡(luò)故障分析法、 對(duì)比分析法等方法，分別構(gòu)建普里姆(prim)模型、節(jié)點(diǎn)故障模型、鏈路故障模型等模型， 使用Matlab軟件編輯算法，得到通訊網(wǎng)絡(luò)總費(fèi)用最省的鋪設(shè)方案、可靠性條件下最省鋪設(shè)方 案以及綜合條件下最省鋪設(shè)方案。針對(duì)問(wèn)題一要求，具體要求為使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，首先使用了簡(jiǎn)化模型分 析、反證法等方法，證明最小生成樹算法能測(cè)算無(wú)向圖遍歷節(jié)點(diǎn)的最省方案，其次應(yīng)用最小 生成樹法中的普里姆(prim)算法構(gòu)造通訊網(wǎng)絡(luò)總費(fèi)用最省模型使用Matlab軟件編程，得到 最優(yōu)鋪設(shè)方案并作圖。針對(duì)問(wèn)題二要求任意一個(gè)

2、結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié)點(diǎn)間仍然能夠保持通信暢通的可能性 都達(dá)到90%時(shí)最省鋪設(shè)方案設(shè)計(jì)問(wèn)題，首先使用節(jié)點(diǎn)排除法進(jìn)行處理，找到重要節(jié)點(diǎn)，利用 樹圖將節(jié)點(diǎn)分類，再通過(guò)分類失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求，最后使用Matlab軟 件編程得出節(jié)點(diǎn)故障模型下最省鋪設(shè)方案。針對(duì)問(wèn)題三要求，任意一條鏈路被破壞時(shí)，能夠保持通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%時(shí) 最省鋪設(shè)方案設(shè)計(jì)問(wèn)題，首先找到重要鏈路，并分析鏈路影響的節(jié)點(diǎn)，用樹圖將節(jié)點(diǎn)分類， 再通過(guò)分類失效節(jié)點(diǎn)與有效節(jié)點(diǎn)連接達(dá)到通暢性要求，最后使用Matlab軟件編程得出鏈路故 障模型下最省鋪設(shè)方案。針對(duì)問(wèn)題四要求，綜合考慮網(wǎng)絡(luò)的可鼎性以及鋪設(shè)費(fèi)用確定合理的鋪設(shè)

3、方案問(wèn)題，首先 對(duì)比分析問(wèn)題二與問(wèn)題三的節(jié)點(diǎn)分類，得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更重要的結(jié)論；再通過(guò) 節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%、90%、95%時(shí)所對(duì)應(yīng)的最低鋪設(shè)費(fèi)用， 使用Matlab軟件編程，得到綜合考慮下的鋪設(shè)方案。本文后續(xù)對(duì)模型進(jìn)行了誤差分析。還基于對(duì)問(wèn)題四中可靠性不僅僅與節(jié)點(diǎn)和鏈路的穩(wěn)定 性有關(guān)，還與節(jié)點(diǎn)的度有關(guān)，故引進(jìn)節(jié)點(diǎn)的度對(duì)模型進(jìn)行改進(jìn)，并利用蟻群算法建立綜合LI 標(biāo)下的鋪設(shè)模型；最后對(duì)模型做出了縱向的推廣和橫向的推廣。關(guān)鍵詞：網(wǎng)絡(luò)通訊設(shè)計(jì)；最小生成樹法；故障分析法；蟻群算法；matlab1問(wèn)題的重述一、背景知識(shí)傳統(tǒng)的通信網(wǎng)絡(luò)是山傳輸、交換和終端三大部分組成。

4、傳輸是傳送信息的媒體，交 換是各種終端交換信息的中介體，終端是指用戶使用的話機(jī)、手機(jī)、傳真機(jī)和計(jì)算機(jī)等?，F(xiàn)代電信網(wǎng)是曲專業(yè)機(jī)構(gòu)以通信設(shè)備（硬件）和相關(guān)工作程序（軟件）有機(jī)建立的 通信系統(tǒng)，為個(gè)人、企事業(yè)單位和社會(huì)提供各類通信服務(wù)的總和?，F(xiàn)在計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)在各個(gè)領(lǐng)域的應(yīng)用范圍已經(jīng)逐步廣泛起來(lái)，其發(fā)展也在不斷的 推動(dòng)人類社會(huì)逐漸走向信息時(shí)代。網(wǎng)絡(luò)技術(shù)的發(fā)展不僅促進(jìn)了社會(huì)生產(chǎn)力的提高，也為 人們的生活帶來(lái)了很大的方便。然而，與此同時(shí)也存在著很多不足，諸如安全隱患、信 息漏洞等，這些對(duì)于人們的工作和生活造成了很大的影響。我們?cè)谛枰谘芯客ㄐ啪W(wǎng)絡(luò) 鋪設(shè)問(wèn)題時(shí)的費(fèi)用問(wèn)題時(shí)，也要充分考慮其的可靠性?？煽啃允?/p>

5、其重要的整體指標(biāo)，通 信網(wǎng)絡(luò)的可靠性不僅與通信設(shè)備、鏈路有關(guān)，而且還與網(wǎng)絡(luò)結(jié)構(gòu)有關(guān)。山于網(wǎng)絡(luò)結(jié)構(gòu)的 復(fù)雜多變，通信網(wǎng)絡(luò)的可靠性分析一直是個(gè)棘手的問(wèn)題。二、相關(guān)資料1. 80個(gè)節(jié)點(diǎn)之間的距離表和鋪設(shè)線路的單位費(fèi)用表（見附表1）；三、要解決的問(wèn)題問(wèn)題1.要使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最省，請(qǐng)建立問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)求解算 法，給出鋪設(shè)方案，并討論方案的可鼎性；問(wèn)題2.考慮到通信網(wǎng)絡(luò)結(jié)點(diǎn)的可靠性，若要求任意一個(gè)結(jié)點(diǎn)出現(xiàn)故障時(shí)，其它結(jié) 點(diǎn)間仍然能夠保持通信暢通的可能性都達(dá)到90%,請(qǐng)建立問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)求解算 法，并給出使總鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問(wèn)題3：考慮到通信網(wǎng)絡(luò)鏈路的可靠性，若要求任意一條鏈路

6、被破壞時(shí)，能夠保持 通信暢通的結(jié)點(diǎn)都能夠達(dá)到90%,請(qǐng)建立問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)求解算法，并給出使總 鋪設(shè)費(fèi)用最少的鋪設(shè)方案；問(wèn)題4：綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)費(fèi)用，試確定合理的鋪設(shè)方案。2問(wèn)題的分析一、問(wèn)題的總分析對(duì)于問(wèn)題的總分析，可以給出四個(gè)問(wèn)題整體框架圖，見圖1圖1四個(gè)問(wèn)題的整體框架圖相應(yīng)呆優(yōu)方案確定通信網(wǎng)絡(luò)鋪設(shè)的合3方案二、對(duì)具體問(wèn)題的分析1. 對(duì)問(wèn)題一的分析某通信公司擬建一個(gè)具有80個(gè)結(jié)點(diǎn)的通信網(wǎng)絡(luò)，需要在這些結(jié)點(diǎn)之間鋪設(shè)線路，進(jìn) 行數(shù)據(jù)傳輸。我們需要根據(jù)附件內(nèi)容建立數(shù)學(xué)模型，并設(shè)計(jì)算法使得通信網(wǎng)絡(luò)的總鋪設(shè) 費(fèi)用最省，并證明可靠性。我們引入圖論中普里姆算法（Prim算法），算法對(duì)通信

7、網(wǎng)絡(luò) 的每條路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測(cè)算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過(guò)簡(jiǎn)化模型 進(jìn)行檢驗(yàn)算法的可鼎性。2. 對(duì)問(wèn)題二的分析問(wèn)題要求這80個(gè)節(jié)點(diǎn)任意一個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí)，其它節(jié)點(diǎn)間仍然能夠保持通信暢 通的可能性都達(dá)到90%,在問(wèn)題一所得出的最小生成樹的的基礎(chǔ)上，若其中只有一個(gè)重 要節(jié)點(diǎn)發(fā)生故障時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能達(dá)到90%, 故通過(guò)節(jié)點(diǎn)刪除法找到重要節(jié)點(diǎn)，再?gòu)闹匾?jié)點(diǎn)引起故障的其他失效節(jié)點(diǎn)中找到一個(gè)節(jié) 點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于八個(gè)即可，并且改進(jìn)方案所鋪設(shè)的費(fèi) 用是最省的。3. 對(duì)問(wèn)題三的分析問(wèn)題要求79個(gè)鏈路中任意一條鏈路被破壞時(shí)，能夠保持

8、通信暢通的節(jié)點(diǎn)都能夠達(dá) 到90%。同樣在問(wèn)題一所得出的最小生成樹的的基礎(chǔ)上，我們考慮到若其中只要有一個(gè) 重要鏈路被破壞時(shí)，會(huì)造成八個(gè)節(jié)點(diǎn)以上故障，那么通信暢通的可能性就不能保證達(dá)到 90%,所以，我們可以通過(guò)逐個(gè)分析每條鏈路，找到重要鏈路，一個(gè)鏈路被破壞會(huì)使最 小生成樹分割成兩個(gè)部分，其中一部分則是失效的，然后再?gòu)闹匾溌繁黄茐亩鸬?其他失效節(jié)點(diǎn)中找到一個(gè)節(jié)點(diǎn)與其他正常節(jié)點(diǎn)連通使得發(fā)生故障的節(jié)點(diǎn)數(shù)少于或等于 八個(gè)，我就能保證通信暢通的可能性達(dá)到90%,并且我們要找到的這個(gè)節(jié)點(diǎn)與其他正常 節(jié)點(diǎn)連通所鋪設(shè)的費(fèi)用是最省的。4. 對(duì)問(wèn)題四的分析問(wèn)題要求是綜合考慮網(wǎng)絡(luò)的可靠性以及鋪設(shè)，試確定合理的鋪

9、設(shè)方案。首先對(duì)比分析問(wèn) 題二與問(wèn)題三的節(jié)點(diǎn)分類，發(fā)現(xiàn)問(wèn)題三中節(jié)點(diǎn)的分類包含了問(wèn)題二中節(jié)點(diǎn)的分類，若滿足了 了節(jié)點(diǎn)穩(wěn)定性的要求，則一定能滿足鏈路穩(wěn)定性的要求，故得出節(jié)點(diǎn)穩(wěn)定性比鏈路穩(wěn)定性更 重要的結(jié)論：再通過(guò)節(jié)點(diǎn)故障模型分別構(gòu)造通信暢通的可能性都達(dá)到85%. 90%、95%時(shí)所對(duì) 應(yīng)的最低鋪設(shè)費(fèi)用，使用Matlab軟件編程，綜合考慮穩(wěn)定性和鋪設(shè)費(fèi)用得出鋪設(shè)方案。3模型的假設(shè)1兩個(gè)節(jié)點(diǎn)之間的費(fèi)用僅由節(jié)點(diǎn)之間的距離和鋪設(shè)線路的單位費(fèi)用決定；2. 各節(jié)點(diǎn)和各鏈條間發(fā)生故障是相互獨(dú)立的，節(jié)點(diǎn)1發(fā)生故障不影響節(jié)點(diǎn)2發(fā)生 故障；3. 每個(gè)節(jié)點(diǎn)的重要性是相等的，不存在次級(jí)差別；4. 任意兩個(gè)節(jié)點(diǎn)之間可以進(jìn)行連

10、接，且一個(gè)節(jié)點(diǎn)可以連接的節(jié)點(diǎn)不受限制；5. 網(wǎng)路的穩(wěn)定性與節(jié)點(diǎn)所連的鏈路條數(shù)無(wú)關(guān)，即每個(gè)節(jié)點(diǎn)和鏈路出現(xiàn)故障的可能 性是相等的；4名詞解釋與符號(hào)說(shuō)明一、名詞解釋1. 最小生成樹：一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包 含原圖中的所有n個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。2. 普里姆算法（Prim算法）指可在加權(quán)連通圖里搜索最小生成樹。意即山此算法 搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)，且其所有邊的權(quán)值之 和亦為最小。二、主要符號(hào)說(shuō)明序號(hào)符號(hào)符號(hào)說(shuō)明1V表示加權(quán)連通圖的節(jié)點(diǎn)集合2E表示加權(quán)連通圖的邊集合3t表示V集合中的任意節(jié)點(diǎn)4%表示初始的節(jié)點(diǎn)集合5U表示集

11、合中的兀素6V表示H中的節(jié)點(diǎn)但不是中的節(jié)點(diǎn)7Xij表示一個(gè)0、1變量，0, 1分別表示選中和未選中8%表示節(jié)點(diǎn)i到節(jié)點(diǎn)j鋪設(shè)線路所花費(fèi)的費(fèi)用9z表示所選的鋪設(shè)方案所花費(fèi)的總費(fèi)用10e表示最小生成樹的鏈路5模型的一、問(wèn)題一的分析與求解1. 問(wèn)題的分析問(wèn)題要求根據(jù)附件內(nèi)容建立數(shù)學(xué)模型，并設(shè)訃算法使得通信網(wǎng)絡(luò)的總鋪設(shè)費(fèi)用最 省，并證明可靠性：我們引入圖論中普里姆算法（Prim算法），算法對(duì)通信網(wǎng)絡(luò)的每條 路的鋪設(shè)費(fèi)用總額進(jìn)行模擬測(cè)算，形成鋪設(shè)費(fèi)用的最小生成樹，并通過(guò)簡(jiǎn)化模型進(jìn)行檢 驗(yàn)算法的可靠性。本文中連通圖的頂點(diǎn)為80個(gè)通訊網(wǎng)絡(luò)的節(jié)點(diǎn)，所有邊的權(quán)值為兩節(jié)點(diǎn)之間的鋪設(shè)通 訊鏈路的總費(fèi)用，通過(guò)普里姆算

12、法可以得出聯(lián)通所有頂點(diǎn)并且使總鋪設(shè)費(fèi)用最低的樹 圖，即相對(duì)于問(wèn)題一的最優(yōu)鋪設(shè)方案。2. 問(wèn)題的求解模型I總鋪設(shè)費(fèi)用最省模型（1）模型的建立普里姆算法（Prim算法）的步驟：從單一點(diǎn)開始，普里姆算法按照以下步驟逐步擴(kuò)大樹中所含節(jié)點(diǎn)的數(shù)U,直到遍歷 連通圖的所有節(jié)點(diǎn)。首先設(shè)加權(quán)連通圖的節(jié)點(diǎn)集合為V，邊集合為E，初始化=”， 其中/為集合V中的任意:節(jié)點(diǎn)，其次在集合中選取權(quán)數(shù)最小的邊（“*）,其中為集合 %中的元素，而卩不是，如果存在權(quán)數(shù)一樣的可任選其中之一，再次，將卩加入到匕， 重復(fù)第二第三步，直到K=Vo引入一個(gè)變量知，X9 = 0時(shí)說(shuō)明該路徑未被選中，1則表示被選中count（y）為總結(jié)n n

13、minZ =工工叫勺 j=i j=i點(diǎn)數(shù)建立的數(shù)學(xué)模型如下s.t=1 ;=1工七 |coz/nZ(V)| - 111 / 29算法流程圖見圖2圖2問(wèn)題一的算法流程圖為了更好的表現(xiàn)算法內(nèi)容，用以下簡(jiǎn)化模型來(lái)表示并驗(yàn)證: 表1普里姆算法示例圖 設(shè)置一個(gè)加權(quán)連通圖，頂點(diǎn)集合為 V,邊集合為E o （ So. a、b、c、為頂點(diǎn), 連線為邊，邊上數(shù)字為權(quán)值）So6cdS。cdSo6cd 選擇頂點(diǎn)集合中任意頂點(diǎn)，此處選 擇S。為初始點(diǎn)。頂點(diǎn)a、b、c、d都有與S（） 直接相連的邊，選取其中權(quán)重最小的點(diǎn)（圖 中為a） 下一個(gè)頂點(diǎn)為距離a或S最近的頂 點(diǎn)，a距離c為10,距d為6,距b為5； So 距c為1

14、0,距d為15,距b為15；所以最 短的距離是a到b得距離為5,連接a與b 繼續(xù)重復(fù)上面的步驟?？梢园l(fā)現(xiàn)距 離6 b和S。最短的是b到c得距離為5,連 接b和6反證法：設(shè)生成的樹為0,假設(shè)存在d使得總花費(fèi)cosr(a)1將兩個(gè)因素綜合考慮，這里利用線性加權(quán)的辦法將其綜合，首先將式(1)、(2)歸 一化，然后定義偏好系數(shù)/e(O,l), /越接近0表是決策者越傾向于費(fèi)用因素，越接近 于1越傾向于流量因素，所以，最終的目標(biāo)函數(shù)為：f = sfd (土 丈叫j/-I 7-1七)+冏(M (deg)5/(deg)設(shè)置約束條件，其中假定每一個(gè)節(jié)點(diǎn)的度數(shù)屬于2,5的閉區(qū)間。凡是有節(jié)點(diǎn)度數(shù)不 在詞區(qū)間的方案

15、都被認(rèn)為是不可行解。為防止螞蟻在尋優(yōu)的過(guò)程中產(chǎn)生不可行解，定義(low,up)為度的約束區(qū)間。對(duì)于每一個(gè)節(jié)點(diǎn)i,其度deg(/),在此定義一個(gè)函數(shù):0s = nunxlOO%f min相應(yīng)的最大容忍度為兒仁節(jié)點(diǎn)穩(wěn)定性的約束：首先引入一個(gè)故障矩陣DP, D表示在節(jié)點(diǎn)i和節(jié)點(diǎn)丿之間 存在連接線時(shí)，連接線出現(xiàn)故障的概率。仍然假定節(jié)點(diǎn)不會(huì)出現(xiàn)故障，所有故障都來(lái)自 于鏈路。而每一條邊對(duì)于點(diǎn)來(lái)說(shuō)是并聯(lián)的，利用概率統(tǒng)計(jì)的知識(shí)，可以求得節(jié)點(diǎn)，能夠 正常工作的概率為：心=1-口令RPmin為用戶規(guī)定的平均最小工作概率。如果在整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)工作的概率 的算數(shù)平均值大于RPmm，則這個(gè)網(wǎng)絡(luò)是可接受的，否則是不可

16、接受的。故RP, %由上述分析，這個(gè)優(yōu)化的模型是一個(gè)組合優(yōu)化模型，可以用蟻群算法來(lái)求解，這里 簡(jiǎn)要介紹一下蟻群算法的求解過(guò)程。1. 初始化參數(shù)2. 利用概率的方法構(gòu)建螞蟻的路徑。本文綜合考慮了最小成本模型和度約束條件, 同時(shí)在本模型中乂加入了流量及鏈路概率的影響。如當(dāng)前位于節(jié)點(diǎn)i的螞蟻k選擇丿作為 下一個(gè)節(jié)點(diǎn)的概率為：”2伽/.Vj其中，5為鏈路信息素強(qiáng)度；竹 為一個(gè)預(yù)先給定的啟發(fā)式信息，初始值為鏈路 (/距離的倒數(shù)。為本算法設(shè)置了啟發(fā)式信息的優(yōu)先級(jí)：鏈路“如果有一個(gè)端點(diǎn)的度為1, 則加1倍，若鏈路(/ 2個(gè)端點(diǎn)的度都為1, %加2倍。a、卩是2個(gè)參數(shù)，它們分 別決定了信息素和啟發(fā)式信息的相對(duì)

17、影響力。代表位于節(jié)點(diǎn)j的螞蟻斤可以直接到達(dá) 的相鄰節(jié)點(diǎn)的集合，也就是還沒(méi)有被螞蟻&訪問(wèn)的節(jié)點(diǎn)的集合。Step3本文使用的后臺(tái)策略是在螞蟻前進(jìn)一步時(shí)就計(jì)算各個(gè)約束的值，看是否滿足 要求，當(dāng)有一個(gè)約束不再滿足要求時(shí)，螞蟻不再前行。一輪路徑探索完之后，計(jì)算LI標(biāo) 函數(shù)的值，進(jìn)而挑選出最優(yōu)的路徑。Step4在每一輪路徑探索之后，更新信息素，更新規(guī)則如下：tn5 ( +1) = PD (n) + Ar/ (/?)其中p為信息素?fù)]發(fā)程度；Ar/(/O表示第k次循環(huán)是否選擇了鏈路“，如果先擇(/ , XjS = Q/diSij,否則，= 0, Q是常數(shù)。5 當(dāng)路徑探索的論述達(dá)到NCmax時(shí)輸出結(jié)果。因?yàn)橄伻?/p>

18、算法有較強(qiáng)的收斂性，故當(dāng)經(jīng)過(guò)不同次數(shù)的迭代實(shí)驗(yàn)是，會(huì)得出較為相近 的結(jié)果，此時(shí)則為最優(yōu)的結(jié)果，最終的結(jié)果可有C語(yǔ)言編程完成。參考文獻(xiàn)：11 .2基于蟻群算法的多目標(biāo)網(wǎng)絡(luò)鋪設(shè)策略研究龔承柱1,諸克軍I,郭海湘1,2(1.中 國(guó)地質(zhì)大學(xué)經(jīng)濟(jì)管理學(xué)院，武漢430074： 2.西安交通大學(xué)管理學(xué)院，西安710049).3姜啟源，謝金星，葉俊.數(shù)學(xué)模型M北京；高等教育出版社，2011, 1.21 / 29附錄程序1:%A表示權(quán)值矩陣%C表示生成樹的權(quán)和%visit標(biāo)記是否訪問(wèn)過(guò)(1表示訪問(wèn)，0表示未訪問(wèn))，dis記錄當(dāng)前最短距離，R矩 陣表示結(jié)點(diǎn)序號(hào)之間從前往后依次連接clc,clearAzzxlsre

19、adCdate.xls);%權(quán)值矩陣(節(jié)點(diǎn)之間的費(fèi)用表二距離*單位費(fèi)用)L=length(A);A(A=O)=inf;% 初始化鄰接矩陣 dis=zeros(l ,L);dis(:)=inf;%初始化 dis 數(shù)組 visit=zeros( 1 ,L)；RESUET=zeros(L,L)； visit(l )= 1 ;dis(l)=O;next= 1 ;C=0;a=zeros(l,80);%初始時(shí)刻1點(diǎn)加入集合中R=zeros(2,79);R(l,:)=l:79;%初始化結(jié)果矩陣for k=l:L-l;now=next;%now表示計(jì)算的當(dāng)前節(jié)點(diǎn) m=inf;%m保存當(dāng)前節(jié)點(diǎn)到集合的最短距離

20、for i=l:L;if visit(i)=O%如果沒(méi)有標(biāo)記，開始這個(gè)點(diǎn) dis(i)=min(dis(i),A(now,i)；%更新這個(gè)i點(diǎn)到集合的最短距離，保存到 dis中if(dis(i)m) m=dis(i); nex t=i; %記錄下最小的那個(gè)點(diǎn)，作為下一個(gè)計(jì)算的點(diǎn)。endendendC=C+m;%加權(quán)值visit(next)=l;%標(biāo)記進(jìn)集合的點(diǎn)RESULT(k,next)= 1;%整合每次標(biāo)記endfor t=l:79;R(2,t)=find(RESULT(t,:)= 1);%按順序輸出節(jié)點(diǎn)表示連接過(guò)程endR %結(jié)果矩陣輸出，第一行表示連接順序，第二行表示表示依次連接節(jié)點(diǎn)數(shù)c

21、 %相應(yīng)情況下的最省鋪設(shè)費(fèi)用程序二：AzzxlsreadCate.xls1）; %權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表二距離*單位費(fèi)用）nl=l 34i2661503270368146667n2=51 30i384583159604812684665334173bn3=77 2366457757111747217104415ml=l 342661503270368146667624769229194928578 351208024m2=513038458315960481268466533417318215243916 5525J ,m3 二7723664577571117472171044157645

22、1；m4=5422 56；%輸入六個(gè)節(jié)點(diǎn)分類矩陣xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 ni4;Ll=length(nl);L2=length(n2);L3=length(n3);L4=length(ml);L5=Iength(m2);L6=length(m3);L7=length(m4);%分別求其長(zhǎng)度和兩兩組合長(zhǎng)度t=l;for i=l:Ll;for j=l:L2;R(t,:)二n 1 (i) n2(j) A(n 1 (i),n2(j) t=t+l;endend for i=l:Ll;for k=l:L3;R(t,:)=nl(i) n3(k) A(nl(i),n3

23、(k); t=t+l;endendfor j=l:L2;for k=l:L3;R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+l;endendfor i=l:Ll;for p=l:L5+L6+L7;R(t,:)=nl(i) xl(p) A(n 1 (i),xl(p); t=t+l;endendfor j=l:L2;for q= 1: L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+I;endendfor k=l:L3;for r=l:L4+L5+L7;R(t,:)=n3(k) x3(r) A(n3(k),x3(r); t

24、=t+l;endendR1 =sortrows(R( 1:192,:),3);Result(h：)=Rl(l,:);R2=sortrows(R(l 93:360,:),3);Result(2,:)=R2( 1R3=sortrows(R(361:584,:),3);Result(3,:)=R3( 1R4=sortrows(R(585:1101 ,:),3);Result(4,:)=R4(l,:);R5=sortrows(R(l 102:1997,:),3);Result(5,:)=R5(l,:);R6=sortrows(R( 1998:2893,:),3)；Result(6,:)=R6(l,:)

25、;%逐個(gè)計(jì)算最省費(fèi)用Result%輸出分類比較下的最省費(fèi)用及相應(yīng)連接節(jié)點(diǎn)序號(hào)程序三：AzzxlsreadCdate.xls1); %權(quán)值矩陣(節(jié)點(diǎn)之間的費(fèi)用表二距離*單位費(fèi)用)nl=I 342661503270368146667n2=51 30384583159604812684665334173n3=77 2366457757111747217104415m1=1 342661503270368146667624769229194928578 35208024m2=513038458315960481268466533417318215243916 5525J ,m3=77236645775

26、71117472171044157645；m4=5422 56；xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 m4;Ll=length(nl);L2=length(n2);L3=Iength(n3);L4=length(ml);L5=length(m2);L6=length(m3);L7=length(m4); %分別求其長(zhǎng)度和兩兩組合長(zhǎng)度t=l；for i=l:Ll;for j=l:L2;R(t,:)=nl(i) n2(j) A(nl(i),n2(j); t=t+l;endendfor i=l:Ll;for k=l:L3;R(t,:)=nl(i) n3(k) A(nl(i

27、),n3(k); t=t+I;endendfor j=l:L2;for k=l:L3;R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+l;endendfor i=l:Ll;for p=l:L5+L6+L7;R(t,：)=n l(i)xl(p) A(n 1 (i),x 1 (p)； t=t+l;endendfor j=l:L2;for q= 1: L4+L6+L7;R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+l;endendfor k=l:L3;for r=l:L4+L5+L7;R(t,:)=n3(k) x3(r) A(n3(k),x3

28、(r); t=t+I;endend%分別求其長(zhǎng)度和兩兩組合長(zhǎng)度R1 =sortrows(R( 1:192,:),3);Result(l,:)=Rl(l,:);R2=sortrows(R( 193:360, :),3);Result(25:)=R2( 1R3=sortrows(R(361:584,:),3);Result(3,:)=R3(l,:);R4=sortrows(R(585:1100,:)53)；Resul t(4,: )=R4( 1,:);R5=sortrows(R( 1101:1996,:),3);Result(5,:)=R5( 1R6=sortrows(R( 1997:2562,:

29、),3)；Result(6,:)=R6( 1Result%輸出分類比較下的最省費(fèi)用及相應(yīng)連接節(jié)點(diǎn)序號(hào)附錄四AzzxlsreadCate.xls1）; %權(quán)值矩陣（節(jié)點(diǎn)之間的費(fèi)用表二距離*單位費(fèi)用）nl=26 3415032;n2=66 6736814;n3=79 63402024 8039;n4=28 491929;ml =65 337341;m2=3159604838 458m3=6 645775;m4=17104415;xl=m2 m3 m4;x2=ml m3 m4;x3=ml m2 m4;Ll=length(nl);L2=length(n2);L3=length(n3);L4=lengt

30、h(n4);L5=length(ml);L6=length(m2);L7=length(m3);L8=length(m4); %求矩陣長(zhǎng)度t=lfor il=1:L1;for jl = l:L5;R(t,:)=nl(il)ml(jl)A(nl(il),ml(jl)l； tn+1；endend for il=1:L1;for jl = l:L6;R(t,:)=nl(il) m2(j 1) A(n 1 (il),m2(j 1); t=t+I;endendfor il=1:L1;fo 叮 1 = 1:L7;R(t,：)=nl(il) m3(j 1) A(n 1 (il),m3(j 1); t=t+I;endendfor il=1:L1;for jl = l:L 8;R(t,:)=nl(il) m4(jl) A(n 1 (il),m4(j 1); t=t+l;endendfor i2=l:L2;fo 叮 2=1 :L6;R(t,:)=n2(i2) m2(j2) A(n2(i2),m2(j2); t=t+l;endendfor i2=l:L2;for j2=l:L7;R(t,:)=n2(i2) m3(j2) A(n2(,m3(j2); t=t+l;endendfor i2=l:L2; f