摘要：應(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來模擬最小生成樹進(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è)。由此來看構(gòu)建兼顧連通性和經(jīng)濟(jì)性的通信網(wǎng)絡(luò)變得極其重要。當(dāng)面對(duì)部分網(wǎng)絡(luò)遭到破壞時(shí)，能夠及時(shí)準(zhǔn)確做出最優(yōu)修復(fù)方案來解決問題也是我國(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)緯度的無向賦權(quán)圖

　　引用圖論相關(guān)知識(shí)，可以將題目所給每座城市的經(jīng)緯度條件繪制成無向賦權(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：建立無向賦權(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.

　　推薦閱讀：《軍事運(yùn)籌與系統(tǒng)工程》(季刊)創(chuàng)刊于1987年，由軍事科學(xué)院軍事運(yùn)籌分析研究所主辦。是總參謀部、總政治部首批建設(shè)的軍事學(xué)術(shù)重點(diǎn)學(xué)術(shù)期刊之一。是軍事科學(xué)院系列刊物之一，也是軍事系統(tǒng)工程專業(yè)委員會(huì)會(huì)刊。