軍事通訊網絡的最短路徑研究分析

戴涵竹　詹清欽　季堂煜

摘要：應軍事斗爭戰(zhàn)備要求，本文需要設計構建包含139個大中型城市作為節(jié)點的有線通信網絡，在每個城市內設置一架專用網絡連接設備，在確保全連通的情況下球的最短的通信線路的總長度。首先，本文使用Kruskal算法并對計算出的所有兩點間距離進行排序，通過使用遞歸調用函數，遍歷循環(huán)所有的節(jié)點，通過不斷比較，在生成完139個數據的連線后，結束遍歷獲得最短路徑，并通過調用百度地圖API來模擬最小生成樹進行顯示，增加了可讀性。

關鍵詞：Kruskal算法 最短路徑 路線圖

前言

在信息化高度發(fā)展的當代，信息化戰(zhàn)爭是現代化戰(zhàn)爭的新模式，因而我國需要加強信息化戰(zhàn)隊建設。由此來看構建兼顧連通性和經濟性的通信網絡變得極其重要。當面對部分網絡遭到破壞時，能夠及時準確做出最優(yōu)修復方案來解決問題也是我國需要重點投入研究的方向。

1模型建立與求解

1.1最小生成樹的路線優(yōu)化模型

本部分建立了城市間通信網絡互通最短路徑選擇模型，主要研究經過所有城市基站且路徑總和最短的數學模型與算法。使用最小生成樹優(yōu)化算法找出連接139座城市的最短總路線，在滿足基本連通性能的基礎上盡可能降低經濟成本。

1.2不同目標點經緯度的無向賦權圖

引用圖論相關知識，可以將題目所給每座城市的經緯度條件繪制成無向賦權圖。G（V，E，w），G中每個頂點為每個城市基站連接點（即為城市的中心經緯度點），V表示圖中頂點頂點總數為E個，W表示圖的權值，如w：表示v→V.的權值（不分方向，（i，j）∈E）。以經度為X軸緯度為Y軸建立二維坐標軸，將頂點放置于二維坐標圖中，每個頂點可表示為v，（X，，Y，）。

1.3計算權值

頂點v，均可與任意其它節(jié)點形成互通連線，且基于假設，城市間的連接方式均采用最短距離連接。任意兩座城市間的通信連接G→G可表示為：

1.4確定最短路徑

本題使用最小生成樹Kruskal優(yōu)化算法，將所有權值進行從小到大的排序，從最小權值開始取，若取此權值支路作為最小路徑則支路兩端的Ⅵ，vj視為連通;將下一個最小權值作為目標支路，若目標支路兩端節(jié)點均已連通且此支路的加人會使連通集合形成閉合回路則此支路不取為最短總路徑的支路（不包括在最短路徑中）;直至取到（139-1=） 138條支路，與此同時所有節(jié)點均已連通，則此138條支路構成的通路為最短路徑。

Step2：利用經緯度數據計算節(jié)點間權值;

Step3：編寫程序，生成最短路徑;

Step4：將生成路徑呈現于百度地圖API上;

Step5：根據百度地圖的顯示，我們將某些能夠更加優(yōu)化的線路進行再次的探討和優(yōu)化。然后將優(yōu)化完的數據再次通過百度地圖進行顯示。

法二，最小生成樹的Prim 算法

Stepl：建立無向賦權圖;

Step2：利用經緯度計算節(jié)點權值;

Step3：任意設定一個節(jié)點Vi作為起始點，取與之相連接的最小權值連線計人最短路徑，此連線兩端的端點計為連通點，將所有相互連通的節(jié)點（連通點）作為一個新的集合，再取與新集合相外接（除集合內節(jié)點以外與其他節(jié)點的連線）的最短連線計人最短路徑，端點視為連通點，所有連通端點再次組成新的集合，依次推進，直至所有點連通找出138條連線組成最短路徑按照以上Prim算法思路編寫程序，生成最短路徑

Step4：將生成路徑呈現于百度地圖API上。

方案選擇

以上兩個方案均可實現最小生成樹的構建，由于本題已給出每個城市的具體經緯度數據，能構建通信網絡連接圖，并且能夠計算出每一權值大小。因此進行大小排序比較能夠更直觀有效得到答案。本組選擇了法一進行求解。

2模型分析

優(yōu)點：

（1）最短路徑尋找算法使用得當，使用Kruskal算法優(yōu)化了路徑求解。

（2）使用百度地圖API方式呈現城市節(jié)點間的連線易于觀察且美觀。

缺點：

關于本題的討論，本文僅僅將路徑最短作為唯一約束條件，未考慮可行性和構建成本問題。例如：大連和煙臺進行跨海連接。

參考文獻

[1]李琳，劉雅奇.通信網節(jié)點重要性的多指標評價方法[J].海軍工程大學學報，2010，22（5）：69-73.

[2]司守奎，孫兆亮.數學建模算法與應用，北京：國防工業(yè)出版社，2017.