戴涵竹　詹清欽　季堂煜

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

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

前言

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

1模型建立與求解

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

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

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

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

1.3計算權(quán)值

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

1.4確定最短路徑

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

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

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

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

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

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

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

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

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

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

方案選擇

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

2模型分析

優(yōu)點：

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

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

缺點：

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

參考文獻

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

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