1、通信網絡的設計問題摘 要本文針對通訊網絡設計問題，使用圖論中最小生成樹法、節點排除法、網絡故障分析法、對比分析法等方法，分別構建普里姆（prim）模型、節點故障模型、鏈路故障模型等模型，使用Matlab軟件編輯算法，得到通訊網絡總費用最省的鋪設方案、可靠性條件下最省鋪設方案以及綜合條件下最省鋪設方案。針對問題一要求，具體要求為使得通信網絡的總鋪設費用最省，首先使用了簡化模型分析、反證法等方法，證明最小生成樹算法能測算無向圖遍歷節點的最省方案，其次應用最小生成樹法中的普里姆（prim）算法構造通訊網絡總費用最省模型使用Matlab軟件編程，得到最優鋪設方案并作圖。針對問題二要求任意一個結點出現故

2、障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%時最省鋪設方案設計問題，首先使用節點排除法進行處理，找到重要節點，利用樹圖將節點分類，再通過分類失效節點與有效節點連接達到通暢性要求，最后使用Matlab軟件編程得出節點故障模型下最省鋪設方案。針對問題三要求，任意一條鏈路被破壞時，能夠保持通信暢通的結點都能夠達到90%時最省鋪設方案設計問題，首先找到重要鏈路，并分析鏈路影響的節點，用樹圖將節點分類，再通過分類失效節點與有效節點連接達到通暢性要求，最后使用Matlab軟件編程得出鏈路故障模型下最省鋪設方案。針對問題四要求，綜合考慮網絡的可靠性以及鋪設費用確定合理的鋪設方案問題，首先對比分析

3、問題二與問題三的節點分類，得出節點穩定性比鏈路穩定性更重要的結論；再通過節點故障模型分別構造通信暢通的可能性都達到85%、90%、95%時所對應的最低鋪設費用，使用Matlab軟件編程，得到綜合考慮下的鋪設方案。本文后續對模型進行了誤差分析。還基于對問題四中可靠性不僅僅與節點和鏈路的穩定性有關，還與節點的度有關，故引進節點的度對模型進行改進，并利用蟻群算法建立綜合目標下的鋪設模型；最后對模型做出了縱向的推廣和橫向的推廣。關鍵詞：網絡通訊設計；最小生成樹法；故障分析法；蟻群算法；matlab §1 問題的重述一、背景知識傳統的通信網絡是由傳輸、交換和終端三大部分組成。傳輸是傳送信息的媒

4、體，交換是各種終端交換信息的中介體，終端是指用戶使用的話機、手機、傳真機和計算機等。現代電信網是由專業機構以通信設備（硬件）和相關工作程序（軟件）有機建立的通信系統，為個人、企事業單位和社會提供各類通信服務的總和。現在計算機網絡技術在各個領域的應用范圍已經逐步廣泛起來，其發展也在不斷的推動人類社會逐漸走向信息時代。網絡技術的發展不僅促進了社會生產力的提高，也為人們的生活帶來了很大的方便。然而，與此同時也存在著很多不足，諸如安全隱患、信息漏洞等，這些對于人們的工作和生活造成了很大的影響。我們在需要在研究通信網絡鋪設問題時的費用問題時，也要充分考慮其的可靠性?？煽啃允瞧渲匾恼w指標，通信網絡的可

5、靠性不僅與通信設備、鏈路有關，而且還與網絡結構有關。由于網絡結構的復雜多變，通信網絡的可靠性分析一直是個棘手的問題。二、相關資料180個節點之間的距離表和鋪設線路的單位費用表（見附表1）；三、要解決的問題問題1要使得通信網絡的總鋪設費用最省，請建立問題的數學模型，設計求解算法，給出鋪設方案，并討論方案的可靠性；問題2考慮到通信網絡結點的可靠性，若要求任意一個結點出現故障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%，請建立問題的數學模型，設計求解算法，并給出使總鋪設費用最少的鋪設方案；問題3：考慮到通信網絡鏈路的可靠性，若要求任意一條鏈路被破壞時，能夠保持通信暢通的結點都能夠達到90%

6、，請建立問題的數學模型，設計求解算法，并給出使總鋪設費用最少的鋪設方案；問題4：綜合考慮網絡的可靠性以及鋪設費用，試確定合理的鋪設方案。§2 問題的分析一、問題的總分析 對于問題的總分析，可以給出四個問題整體框架圖，見圖1圖1 四個問題的整體框架圖二、對具體問題的分析1對問題一的分析某通信公司擬建一個具有80個結點的通信網絡，需要在這些結點之間鋪設線路，進行數據傳輸。我們需要根據附件內容建立數學模型，并設計算法使得通信網絡的總鋪設費用最省，并證明可靠性。我們引入圖論中普里姆算法（Prim算法），算法對通信網絡的每條路的鋪設費用總額進行模擬測算，形成鋪設費用的最小生成樹，并通過簡化模型

7、進行檢驗算法的可靠性。2對問題二的分析問題要求這80個節點任意一個節點出現故障時，其它節點間仍然能夠保持通信暢通的可能性都達到90%，在問題一所得出的最小生成樹的的基礎上，若其中只有一個重要節點發生故障時，會造成八個節點以上故障，那么通信暢通的可能性就不能達到90%，故通過節點刪除法找到重要節點，再從重要節點引起故障的其他失效節點中找到一個節點與其他正常節點連通使得發生故障的節點數少于八個即可，并且改進方案所鋪設的費用是最省的。3對問題三的分析問題要求79個鏈路中任意一條鏈路被破壞時，能夠保持通信暢通的節點都能夠達到90%。同樣在問題一所得出的最小生成樹的的基礎上，我們考慮到若其中只要有一個重

8、要鏈路被破壞時，會造成八個節點以上故障，那么通信暢通的可能性就不能保證達到90%，所以，我們可以通過逐個分析每條鏈路，找到重要鏈路，一個鏈路被破壞會使最小生成樹分割成兩個部分，其中一部分則是失效的，然后再從重要鏈路被破壞而引起的其他失效節點中找到一個節點與其他正常節點連通使得發生故障的節點數少于或等于八個，我就能保證通信暢通的可能性達到90%，并且我們要找到的這個節點與其他正常節點連通所鋪設的費用是最省的。4對問題四的分析問題要求是綜合考慮網絡的可靠性以及鋪設，試確定合理的鋪設方案。首先對比分析問題二與問題三的節點分類，發現問題三中節點的分類包含了問題二中節點的分類，若滿足了了節點穩定性的要求

9、，則一定能滿足鏈路穩定性的要求，故得出節點穩定性比鏈路穩定性更重要的結論；再通過節點故障模型分別構造通信暢通的可能性都達到85%、90%、95%時所對應的最低鋪設費用，使用Matlab軟件編程，綜合考慮穩定性和鋪設費用得出鋪設方案。§3 模型的假設1 兩個節點之間的費用僅由節點之間的距離和鋪設線路的單位費用決定；2 各節點和各鏈條間發生故障是相互獨立的，節點1發生故障不影響節點2發生故障；3每個節點的重要性是相等的，不存在次級差別；4任意兩個節點之間可以進行連接，且一個節點可以連接的節點不受限制；5網路的穩定性與節點所連的鏈路條數無關，即每個節點和鏈路出現故障的可能性是相等的；

10、67;4 名詞解釋與符號說明一、名詞解釋1最小生成樹：一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。2普里姆算法（Prim算法） 指可在加權連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點，且其所有邊的權值之和亦為最小。二、主要符號說明序號符號符號說明1表示加權連通圖的節點集合2表示加權連通圖的邊集合3表示集合中的任意節點4表示初始的節點集合5表示集合中的元素6表示中的節點但不是中的節點7表示一個0、1變量，0，1分別表示選中和未選中 8表示節點i到節點j鋪設線路所花費的費用9Z表

11、示所選的鋪設方案所花費的總費用10表示最小生成樹的鏈路§5 模型的建立與求解一、問題一的分析與求解1問題的分析問題要求根據附件內容建立數學模型，并設計算法使得通信網絡的總鋪設費用最省，并證明可靠性；我們引入圖論中普里姆算法（Prim算法），算法對通信網絡的每條路的鋪設費用總額進行模擬測算，形成鋪設費用的最小生成樹，并通過簡化模型進行檢驗算法的可靠性。本文中連通圖的頂點為80個通訊網絡的節點，所有邊的權值為兩節點之間的鋪設通訊鏈路的總費用，通過普里姆算法可以得出聯通所有頂點并且使總鋪設費用最低的樹圖，即相對于問題一的最優鋪設方案。2問題的求解模型總鋪設費用最省模型 模型的建立普里姆算法

12、（Prim算法）的步驟：從單一點開始，普里姆算法按照以下步驟逐步擴大樹中所含節點的數目，直到遍歷連通圖的所有節點。首先設加權連通圖的節點集合為，邊集合為，初始化，其中為集合中的任意節點，其次在集合中選取權數最小的邊，其中為集合中的元素，而不是，如果存在權數一樣的可任選其中之一，再次，將加入到，重復第二第三步，直到。引入一個變量，時說明該路徑未被選中，1則表示被選中為總結點數建立的數學模型如下算法流程圖見圖2圖2 問題一的算法流程圖為了更好的表現算法內容，用以下簡化模型來表示并驗證：表1普里姆算法示例圖設置一個加權連通圖，頂點集合為，邊集合為。（為頂點，連線為邊,邊上數字為權值）選擇頂點集合中任

13、意頂點，此處選擇為初始點。頂點a、b、c、d都有與直接相連的邊，選取其中權重最小的點（圖中為a）下一個頂點為距離a或最近的頂點，a距離c為10，距d為6，距b為5；距c為10，距d為15，距b為15；所以最短的距離是a到b得距離為5，連接a與b繼續重復上面的步驟。可以發現距離a,b和最短的是b到c得距離為5，連接b和c。最后d與a,b,c, 之中最短的距離為c到d的連線為6，故連接c到d,得出了最小生成樹。軌跡為到a到b到c到d 模型可靠性的檢驗反證法：設生成的樹為,假設存在使得總花費；則一定存在一個不屬于；將加入，而 在本被其他點連接，加入后會形成一個環；而一定小于環中某一邊的權重，這與在生

14、成樹時每次都取權重最小值的步驟矛盾；故假設不成立，原模型成立。 模型的求解根據matlab運行結果見表1（程序見附錄1），可以得到通信網絡的總鋪設費用為2947800元。得到的最優鋪設方案如圖3。表1 問題一結果圖連接順序12345678節點序號346170623647219連接順序910111213141516節點序號5352737849713連接順序1718192021222324節點序號4028425366672254連接順序2526272829304647節點序號1652561851127417連接順序4849505152535455節點序號10442367564821連接順序5657

15、585960616263節點序號1129201550327226連接順序6465666768697071節點序號439637924396569連接順序7273747576777879節點序號5737482541146080圖3最優鋪設方案圖二、問題二的分析與求解1對問題的分析在問題一所得出的最小生成樹的的基礎上，我們考慮到若其中只要有一個重要節點發生故障時，會造成八個節點以上故障，那么通信暢通的可能性就不能保證達到90%，所以，我們可以通過節點刪除法找到重要節點，然后再從重要節點引起故障的其他失效節點中找到一個節點與其他正常節點連通使得發生故障的節點數少于八個，我們就能保證通信暢通的可能性達到

16、90%，并且我們要找到的這個節點與其他正常節點連通所鋪設的費用是最省的。可以給出具體的算法流程圖，如圖4，圖4問題二的算法流程圖2對問題的求解我們以節點22為中心節點，可以將最小生成樹分成四個大部分：為節點22左邊部分，為節點22右上方部分，為節點22右下方部分，即為剩下的部分，即=22 56 54。例如部分，當這部分有節點出現故障時，我們通過或的點與這個故障點引起的失效點之間用最省的方案再鋪設一條線路后，保證任一點發生故障后也能使通信暢通的可能性達到90%。通過此方法，我們可以在部分找到重要節點70，部分找到重要節點51，部分找到重要節點77。找到重要節點后，要考慮這三個重要節點任一發生故障

17、時，怎么增加最省的鋪設線路問題，然后我們再分別將、分成兩個部分，第一部分是重要節點出現故障后造成可靠性小于90%的節點之和，即我們必需增加鋪設線路的點，第二部分是重要節點發生故障后不影響可靠性的節點之和。所以可分為:BC=703681466676247692291949285783520802439406379273713425337;可分為:D=303845831596048E=5112463341686573182152439165525可分為:F=71 11 74 7217104415G=772366457757645對于任意節點發生故障時，要通過增加鋪設后保證

18、至少有70個節點是通信暢通的。所以這六個部分要考慮連接的方案有：BD和； BF和D；DF 和B；B、D和；可以通過matlab編程（見附錄程序2）分別計算9條線路各自最小的費用，然后計算4個方案費用。費用最小的方案所對應的線路即是我們要增加的鋪設線路。Matlab算出的結果見表2：表2 問題二結果圖節點1節點2鋪設費用6168528817645467152861685282354465102470BD是60-61連接，對應費用為209100元；是2-10連接，對應費用為47000元，所以增加的總費用為256100元。BF是1-72連接，對應費用為78000元；D是15-38連接，對應費用為53

19、600元，所以增加的總費用為131600元。DF 是15-38連接，對應費用為53600元， B是61-68連接，對應費用為52800元，所以增加的總費用為106400元。B是61-68連接，對應費用為52800元；D是15-38連接，對應費用為53600元；是2-10連接，對應費用為47000元；所以增加的總費用為153400元。通過比較4個方案，可以得知第三個方案所需要增加的費用是106400元，所以總的鋪設費用=+106400=3054200元。增加的路線如圖5。圖5 任一節點出現故障可靠性達到90%的最優鋪設方案圖三、問題三的分析與求解1對問題的分析同樣在問題一所得出的最小生成樹的的基

20、礎上，我們考慮到若其中只要有一個重要鏈路被破壞時，會造成八個節點以上故障，那么通信暢通的可能性就不能保證達到90%，所以，我們可以通過逐個分析每條鏈路，找到重要鏈路，一個鏈路被破壞會使最小生成樹分割成兩個部分，其中一部分則是失效的，然后再從重要鏈路被破壞而引起的其他失效節點中找到一個節點與其他正常節點連通使得發生故障的節點數少于或等于八個，我就能保證通信暢通的可能性達到90%，并且我們要找到的這個節點與其他正常節點連通所鋪設的費用是最省的。2對問題的求解在第二問的基礎上，我們已經將最小生成樹分成四個大部分、和。再比如部分，當這部分的一個鏈路被破壞時，我們通過或的點與這個故障點引起的失效點之間用

21、最省的方案再鋪設一條線路后，保證任何一條鏈路被破壞后也能使通信暢通的可能性達到90%。通過此方法，我們可以在部分找到的重要鏈路是70與62之間的鏈路，在部分找到重要鏈路是18與51之間的鏈路，在部分找到重要鏈路是76與77之間的鏈路。找到三個重要的鏈路、和后，我們要研究這三個重要鏈路任一發生故障時，怎么增加最省的鋪設線路問題，這三個重要的鏈路任意一個被破壞時都會導致其所在的部分被分割成兩個小的部分，一個部分中的節點都是有效的，一個部分的節點都是失效的。所以我們將分成：= 1342661503270368146667= 62476922919492857835208024394063792737

22、13425337所以我們將分成：= 5130384583159604812684665334173= 182152439165525所以我們將分成：= 7723664577571117472171044157645= 7645=22 56 54比如鏈路被破壞后，會導致部分的節點都失效，保持通信暢通的節點就不能達到90%，同樣，和也是如此，即要保證這三條鏈路之一破壞時，、和都不能失效，所以要考慮的連接方案有：和； 和；和；、和通過Matlab（見附錄程序3）算出的結果如表3：表3 問題三結果圖節點1節點2鋪設費用6168528817645467152861685282354465102470是6

23、1-68連接，對應費用為52800元；是2-10連接，對應費用為47000元，所以增加的總費用為998000元。是8-17連接，對應費用為64500元；是23-54連接，對應費用為46500元，所以增加的總費用為111000元。是46-71連接，對應費用為52800元， 是61-68連接，對應費用為52800元，所以增加的總費用為105600元。是是2-10連接，對應費用為47000元，是23-54連接，對應費用為46500元，；是61-68連接，對應費用為52800元，；所以增加的總費用為146300元。通過比較4個方案，可以得知第一個方案所需要增加的費用最省，費用是是99800元，所以總的

24、鋪設費用=+99800=3047600元。圖6 任一鏈路出現故障可靠性達到90%的最優鋪設方案圖四、問題四的分析與求解1對問題的分析在問題二及問題三的基礎上，首先對比分析問題二與問題三的節點分類，發現問題三中節點的分類包含了問題二中節點的分類，若滿足了了節點穩定性的要求，則一定能滿足鏈路穩定性的要求，故得出節點穩定性比鏈路穩定性更重要的結論；再通過節點故障模型分別構造通信暢通的可能性都達到85%、90%、95%時所對應的最低鋪設費用，使用Matlab軟件編程，綜合考慮穩定性和鋪設費用得出鋪設方案。2對問題的求解我們以節點22為中心節點，可以將最小生成樹分成四個大部分：為節點22左邊部分，為節點

25、22右上方部分，為節點22右下方部分，即為剩下的部分，即=22 56 54。所問題二中可分為:BC=703681466676247692291949285783520802439406379273713425337;問題三中將可分為：= 1342661503270368146667= 6247692291949285783520802439406379273713425337可見問題三中的節點分類包括了問題二中的分類問題二中可分為:D=303845831596048E=5112463341686573182152439165525問題三中將分成：= 513038458

26、3159604812684665334173= 182152439165525利用matlab求解結果見表4。（程序間附錄程序4）表4 問題四結果圖節點1節點2鋪設費用節點1節點2鋪設費用26332070636425761382716246510302675342039413000110326340592738363810922431190066751296631011908176451962565364128101962565可見問題三中的節點分類包括了問題二中的分類故節點穩定性的要求更高，即只要滿足了節點穩定性就能滿足鏈條穩定性的要求，下面僅考慮節點穩定性需求下的故障模型。當若要求任意一個

27、結點出現故障時，其它結點間仍然能夠保持通信暢通的可能性都達到85%時，通過問題二與問題三的模型計算出的最省鋪設方案為3047600元。分配方案為：圖7 通暢度85%時最省鋪設方案同樣若要求任意一個結點出現故障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%時，通過問題二與問題三的模型計算出的最省鋪設方案為3054200元。分配方案為：圖8 通暢度90%時最省鋪設方案同樣若要求任意一個結點出現故障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%時，通過問題二與問題三的模型計算出的最省鋪設方案為3578800元。分配方案為：圖9 通暢度95%時最省鋪設方案可見當通暢度從85%增加至90

28、%時，費用僅僅增加了6400元，而當通暢度從90%增加至95%時，費用增加了524600元，故選擇90%的通暢度，此時可以滿足當一個節點或一個鏈條出現故障時，其它結點間仍然能夠保持通信暢通的可能性都達到90%，且費用適中，可以同時滿足穩定性和鋪設成本的條件，故本題選擇圖5所示的鋪設方案為綜合的最優方案。§6 誤差分析一、誤差分析1在取得兩節點之間的距離數據時由于人工記取數據或者測量距離的工具不標準，會造成讀取數據的誤差，從而造成模型的誤差。2在論文中直接認為總的鋪設費用是有距離和節點單位費用決定的，在實際解決問題中，總鋪設費用還要考慮其他因素的影響。3在問題二的分析方法中，我們直接認

29、為每個節點之間發生故障的概率是相同的，其實有的節點發生故障的概率大，我們考慮的太理想化，而且有的節點發生故障會導致其他某些節點發生故障的概率增大或者減小。§7 模型的評價與推廣一、模型的優點 1本文對問題有合理的猜想、假設、計算以及檢驗；2按照需要求解的問題靈活選取數據，而不是每次都使用同一個數據；3問題三在求解出來之后又提出一個新思路，并且有一個新的解法。一題兩解，并且可以互相驗證結果；4研究問題時循序漸進，在求解的過程中慢慢進步，逐步完善。二、模型的缺點1求解問題時用的數據是自己觀察，手工計數的，這樣得出的數據難免會有些誤差，有些沒有考慮到的因素；2在最后模型改進的時候，我們提出

30、了思路和解法但是由于時間有限，我們并沒有將最后的具體結果計算出來；三、模型的推廣1排隊論模型我們所研究的排隊論是把排隊論應用到交通中，道路發生事故時堵車所形成的類似排隊現象這種情況運用排隊論的相關知識來求解，我們還可以將排隊論延伸到其它的領域，比如車站買票、醫院取藥、通訊服務等其它領域；2交通流模型由于進出匝道或交通事故等原因而形成的交通瓶頸，是導致高速道路交通擁擠和堵塞的最主要的根源，我們通過這個模型不僅僅能夠對解決堵車時的排隊長度問題還可以解決密度，速度等其他的交通指標；3在解決第三問時，我們發現交通堵塞問題與管道收縮而導致的運動氣流中形成激動波過程很相似，所以我們就通過研究后者的模型來類

31、比我們要解決的問題，這種聯想類比法也可以推廣到其它問題。§8 模型的改進本題中線路的可靠性僅僅考慮了節點和鏈路的穩定性，在保證連通性的情況下最小化了鋪設成本；但未考慮流量因素，流量與節點的度有關，節點的度是指與節點直接連接的鏈路的數量，流量因素是指：一個節點的度越多，流過這個節點的最大流量就越大。所以，流量可以看作是圖中節點的度數之和的增函數。而在節點度之和一定的情況下，各個節點度數的波動越大，度數小的節點就成為流量的約束。因此，流量的大小是節點度數的方差函數。令代表圖中度的均值，代表方差構造流量函數： （1）而本文問題一中有鋪設成本的目標函數為： （2）將兩個因素綜合考慮，這里利用

32、線性加權的辦法將其綜合，首先將式（1）、（2）歸一化，然后定義偏好系數，越接近0表是決策者越傾向于費用因素，越接近于1越傾向于流量因素，所以，最終的目標函數為：設置約束條件，其中假定每一個節點的度數屬于2,5的閉區間。凡是有節點度數不在詞區間的方案都被認為是不可行解。為防止螞蟻在尋優的過程中產生不可行解，定義（low,up）為度的約束區間。對于每一個節點i，其度，在此定義一個函數：則可以定義罰函數為：預算成本的約束：因為前面推導出了一個新目標函數，所有鋪設成本不再是要優化的對象。而在實際過程中，決策放能夠承擔的最大鋪設成本一定不大于預算。所以，定義一個最大預算。根據心理學的知識，決策者對費用的

33、容忍度通常都是在與最小成本的比較中產生的，所以定義一個容忍百分比其取值如下：相應的最大容忍度為。節點穩定性的約束：首先引入一個故障矩陣， 表示在節點和節點之間存在連接線時，連接線出現故障的概率。仍然假定節點不會出現故障，所有故障都來自于鏈路。而每一條邊對于點來說是并聯的，利用概率統計的知識，可以求得節點能夠正常工作的概率為：令為用戶規定的平均最小工作概率。如果在整個網絡中所有節點工作的概率的算數平均值大于，則這個網絡是可接受的，否則是不可接受的。故由上述分析，這個優化的模型是一個組合優化模型，可以用蟻群算法來求解，這里簡要介紹一下蟻群算法的求解過程。1.初始化參數2. 利用概率的方法構建螞蟻的

34、路徑。本文綜合考慮了最小成本模型和度約束條件，同時在本模型中又加入了流量及鏈路概率的影響。如當前位于節點的螞蟻選擇作為下一個節點的概率為：其中，為鏈路信息素強度； 為一個預先給定的啟發式信息，初始值為鏈路距離的倒數。為本算法設置了啟發式信息的優先級：鏈路如果有一個端點的度為1，則加1 倍，若鏈路 2 個端點的度都為1，加2 倍。、 是2 個參數，它們分別決定了信息素和啟發式信息的相對影響力。代表位于節點的螞蟻可以直接到達的相鄰節點的集合，也就是還沒有被螞蟻訪問的節點的集合。Step3 本文使用的后臺策略是在螞蟻前進一步時就計算各個約束的值，看是否滿足要求，當有一個約束不再滿足要求時，螞蟻不再前

35、行。一輪路徑探索完之后，計算目標函數的值，進而挑選出最優的路徑。Step4 在每一輪路徑探索之后，更新信息素，更新規則如下：其中為信息素揮發程度；表示第次循環是否選擇了鏈路，如果先擇，否則，是常數。5.當路徑探索的論述達到時輸出結果。因為蟻群算法有較強的收斂性，故當經過不同次數的迭代實驗是，會得出較為相近的結果，此時則為最優的結果，最終的結果可有C語言編程完成。參考文獻：1 /wiki/Prim%E6%BC%94%E7%AE%97%E6%B3%95 .2 基于蟻群算法的多目標網絡鋪設策略研究龔承柱1，諸克軍1，郭海湘1,2(1. 中國地質大學經濟管理

36、學院，武漢 430074；2. 西安交通大學管理學院，西安 710049). 3 姜啟源，謝金星，葉俊.數學模型M 北京；高等教育出版社，2011，1.10附錄程序1：%A表示權值矩陣%C表示生成樹的權和%visit標記是否訪問過（1表示訪問，0表示未訪問），dis記錄當前最短距離，R矩陣表示結點序號之間從前往后依次連接clc,clearA=xlsread('date.xls');%權值矩陣（節點之間的費用表=距離*單位費用）L=length(A);A(A=0)=inf;%初始化鄰接矩陣dis=zeros(1,L);dis(:)=inf;%初始化dis數組visit=zeros

37、(1,L);RESULT=zeros(L,L);visit(1)=1;dis(1)=0;next=1;C=0;a=zeros(1,80);%初始時刻1點加入集合中R=zeros(2,79);R(1,:)=1:79;%初始化結果矩陣for k=1:L-1; now=next;%now表示計算的當前節點 m=inf;%m保存當前節點到集合的最短距離 for i=1:L; if visit(i)=0%如果沒有標記，開始這個點 dis(i)=min(dis(i),A(now,i);%更新這個i點到集合的最短距離，保存到dis中 if(dis(i)<m) m=dis(i); next=i;%記錄下

38、最小的那個點，作為下一個計算的點。 end end end C=C+m;%加權值 visit(next)=1;%標記進集合的點 RESULT(k,next)=1;%整合每次標記endfor t=1:79; R(2,t)=find(RESULT(t,:)=1);%按順序輸出節點表示連接過程endR %結果矩陣輸出，第一行表示連接順序，第二行表示表示依次連接節點數C %相應情況下的最省鋪設費用程序二：A=xlsread('date.xls'); %權值矩陣（節點之間的費用表=距離*單位費用）n1=1342661503270368146667;n2=51303845831596048

39、12684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117472171044157645;m4=542256;%輸入六個節點分類矩陣x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;L1=length(n1);L2=length(n2);L3=length(n3);L4=length(m1);L5=l

40、ength(m2);L6=length(m3);L7=length(m4);%分別求其長度和兩兩組合長度t=1; for i=1:L1; for j=1:L2; R(t,:)=n1(i) n2(j) A(n1(i),n2(j) t=t+1; end end for i=1:L1; for k=1:L3; R(t,:)=n1(i) n3(k) A(n1(i),n3(k); t=t+1; end end for j=1:L2; for k=1:L3; R(t,:)=n2(j) n3(k) A(n2(j),n3(k); t=t+1; end end for i=1:L1; for p=1:L5+L6

41、+L7; R(t,:)=n1(i) x1(p) A(n1(i),x1(p); t=t+1; end end for j=1:L2; for q=1:L4+L6+L7; R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+1; end end for k=1:L3; for r=1:L4+L5+L7; R(t,:)=n3(k) x3(r) A(n3(k),x3(r); t=t+1; end end R1=sortrows(R(1:192,:),3); Result(1,:)=R1(1,:); R2=sortrows(R(193:360,:),3); Result(2,:)

42、=R2(1,:); R3=sortrows(R(361:584,:),3); Result(3,:)=R3(1,:); R4=sortrows(R(585:1101,:),3); Result(4,:)=R4(1,:); R5=sortrows(R(1102:1997,:),3); Result(5,:)=R5(1,:); R6=sortrows(R(1998:2893,:),3);Result(6,:)=R6(1,:);%逐個計算最省費用Result%輸出分類比較下的最省費用及相應連接節點序號程序三：A=xlsread('date.xls'); %權值矩陣（節點之間的費用表=

43、距離*單位費用）n1=1342661503270368146667;n2=5130384583159604812684665334173;n3=772366457757111747217104415;m1=134266150327036814666762476922919492857835208024;m2=5130384583159604812684665334173182152439165525;m3=7723664577571117472171044157645;m4=542256;x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;L1=length(n1);L2=

44、length(n2);L3=length(n3);L4=length(m1);L5=length(m2);L6=length(m3);L7=length(m4); %分別求其長度和兩兩組合長度t=1; for i=1:L1; for j=1:L2; R(t,:)=n1(i) n2(j) A(n1(i),n2(j); t=t+1; end end for i=1:L1; for k=1:L3; R(t,:)=n1(i) n3(k) A(n1(i),n3(k); t=t+1; end end for j=1:L2; for k=1:L3; R(t,:)=n2(j) n3(k) A(n2(j),n3

45、(k); t=t+1; end end for i=1:L1; for p=1:L5+L6+L7; R(t,:)=n1(i) x1(p) A(n1(i),x1(p); t=t+1; end end for j=1:L2; for q=1:L4+L6+L7; R(t,:)=n2(j) x2(q) A(n2(j),x2(q); t=t+1; end end for k=1:L3; for r=1:L4+L5+L7; R(t,:)=n3(k) x3(r) A(n3(k),x3(r); t=t+1; end end %分別求其長度和兩兩組合長度 R1=sortrows(R(1:192,:),3); R

46、esult(1,:)=R1(1,:); R2=sortrows(R(193:360,:),3); Result(2,:)=R2(1,:); R3=sortrows(R(361:584,:),3); Result(3,:)=R3(1,:); R4=sortrows(R(585:1100,:),3); Result(4,:)=R4(1,:); R5=sortrows(R(1101:1996,:),3); Result(5,:)=R5(1,:); R6=sortrows(R(1997:2562,:),3); Result(6,:)=R6(1,:); Result %輸出分類比較下的最省費用及相應連接

47、節點序號 附錄四A=xlsread('date.xls'); %權值矩陣（節點之間的費用表=距離*單位費用）n1=263415032;n2=666736814;n3=79634020248039;n4=28491929;m1=65337341;m2=3159604838458;m3=6645775;m4=17104415;x1=m2 m3 m4;x2=m1 m3 m4;x3=m1 m2 m4;L1=length(n1);L2=length(n2);L3=length(n3);L4=length(n4);L5=length(m1);L6=length(m2);L7=length(

48、m3);L8=length(m4);%求矩陣長度t=1 for i1=1:L1; for j1=1:L5; R(t,:)=n1(i1) m1(j1) A(n1(i1),m1(j1); t=t+1; end end for i1=1:L1; for j1=1:L6; R(t,:)=n1(i1) m2(j1) A(n1(i1),m2(j1); t=t+1; end end for i1=1:L1; for j1=1:L7; R(t,:)=n1(i1) m3(j1) A(n1(i1),m3(j1); t=t+1; end end for i1=1:L1; for j1=1:L8; R(t,:)=n1(i1) m4(j1) A(n1(i1),m4(j1)