軍事通訊網(wǎng)絡(luò)的最短路徑研究分析

戴涵竹　詹清欽　季堂煜

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

關(guān)鍵詞：Kruskal算法 最短路徑 路線圖

前言

在信息化高度發(fā)展的當(dāng)代，信息化戰(zhàn)爭(zhēng)是現(xiàn)代化戰(zhàn)爭(zhēng)的新模式，因而我國(guó)需要加強(qiáng)信息化戰(zhàn)隊(duì)建設(shè)。由此來(lái)看構(gòu)建兼顧連通性和經(jīng)濟(jì)性的通信網(wǎng)絡(luò)變得極其重要。當(dāng)面對(duì)部分網(wǎng)絡(luò)遭到破壞時(shí)，能夠及時(shí)準(zhǔn)確做出最優(yōu)修復(fù)方案來(lái)解決問題也是我國(guó)需要重點(diǎn)投入研究的方向。

1模型建立與求解

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

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

1.2不同目標(biāo)點(diǎn)經(jīng)緯度的無(wú)向賦權(quán)圖

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

1.3計(jì)算權(quán)值

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

1.4確定最短路徑

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

Step2：利用經(jīng)緯度數(shù)據(jù)計(jì)算節(jié)點(diǎn)間權(quán)值;

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

Step4：將生成路徑呈現(xiàn)于百度地圖API上;

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

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

Stepl：建立無(wú)向賦權(quán)圖;

Step2：利用經(jīng)緯度計(jì)算節(jié)點(diǎn)權(quán)值;

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

Step4：將生成路徑呈現(xiàn)于百度地圖API上。

方案選擇

以上兩個(gè)方案均可實(shí)現(xiàn)最小生成樹的構(gòu)建，由于本題已給出每個(gè)城市的具體經(jīng)緯度數(shù)據(jù)，能構(gòu)建通信網(wǎng)絡(luò)連接圖，并且能夠計(jì)算出每一權(quán)值大小。因此進(jìn)行大小排序比較能夠更直觀有效得到答案。本組選擇了法一進(jìn)行求解。

2模型分析

優(yōu)點(diǎn)：

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

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

缺點(diǎn)：

關(guān)于本題的討論，本文僅僅將路徑最短作為唯一約束條件，未考慮可行性和構(gòu)建成本問題。例如：大連和煙臺(tái)進(jìn)行跨海連接。

參考文獻(xiàn)

[1]李琳，劉雅奇.通信網(wǎng)節(jié)點(diǎn)重要性的多指標(biāo)評(píng)價(jià)方法[J].海軍工程大學(xué)學(xué)報(bào)，2010，22（5）：69-73.

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