基于大數(shù)據(jù)技術的軍事比武路徑優(yōu)選方法研究

姚俊萍　李新社　李曉軍

摘 要 數(shù)據(jù)已經(jīng)成為信息化時代的關鍵生產(chǎn)要素，將大數(shù)據(jù)技術應用于軍事領域具有重要的意義。本文首先利用百度地圖中的大數(shù)據(jù)，計算出軍事比武中待經(jīng)過點之間的距離，然后設計算法變換距離數(shù)據(jù)表使得零個數(shù)達到最多，最終得出軍事比武距離中的最短路徑，從而節(jié)省了時間，提高了部隊戰(zhàn)斗力。

關鍵詞 大數(shù)據(jù) 優(yōu)化 最短路徑

中圖分類號：TP274 文獻標識碼：A DOI：10.16400/j.cnki.kjdkz.2018.10.035

Abstract Data has become a key production factor in the information age； applying big data technology to the military field is of great significance. We calculate the distance between points in military contest based on big data in Baidu Maps， design algorithms to transform the distance data table to maximize the number of zeros， and find the shortest path in the military distance in this paper. It improves the combat effectiveness of the troops effectively.

Keywords big data； optimization； shortest path

大數(shù)據(jù)常用的分析方法有統(tǒng)計、數(shù)據(jù)挖掘、預報、文本挖掘和優(yōu)化。優(yōu)化方法從前一直被忽視，但發(fā)展前景不可小視。比如軍事比武路徑優(yōu)選、安全警勤巡查路線優(yōu)選、武器快速配發(fā)、快件快速投遞，將優(yōu)化方法應用在這幾個領域，可以節(jié)約資源、節(jié)省時間，尤其是在軍事斗爭領域可以提高戰(zhàn)斗力。這里以軍事比武路徑優(yōu)選為例，每個參與比武的選手必須在某個區(qū)域內的所規(guī)定位置必須巡視一次，也只需一次，然后回到出發(fā)點。至于如何規(guī)劃行走路線可以八仙過海，各顯神通。再假設比武工具為摩托車，幾乎不受交通影響，且各道路行走難易程度一樣。

如何規(guī)劃行走路線使得耗費最低？對一個選手來說，固有技能已經(jīng)確定，關鍵是選擇行走路線，顯然行走路線最短的一條應為首選。巡視點位確定后，任意兩個巡視點的距離可以通過百度地圖計算出來。一個可以但比較壞的想法是通過排列組合進行窮舉比較選擇，該種想法只有在巡視點很少情況下才可以，否則計算量很大，難以實現(xiàn)。

1 研究基礎及其依據(jù)

假設巡視點為A、B、C、D、E、F，通過百度地圖計算各巡視點的距離如表1所示。

當不等于時為百度地圖計算出的值，等于時為∞。

定義 矩陣代表各點之間的計算距離，為求解結果，于是行走路線問題轉化為如下求解最小值的數(shù)學模型問題。

其中，的每行每列都只有1個1，其余為零，說明每個點只能從其他一個點到達。通過這個解可以形成一個路線，該路線經(jīng)過所有點，除回到出發(fā)點外，每點只經(jīng)過一次，關鍵是路線距離最短。

數(shù)據(jù)表中的一行（列）各元素減去該行列的最小元素，得到新的表格數(shù)據(jù)。原、新兩個表格數(shù)據(jù)求解結果相同，這是因為到某點距離同時增大或縮小相同值與選擇合適路徑無關，猶如在五個數(shù)中選出最小的那一個，所有數(shù)據(jù)同時增加或減小相同值不改變選擇的對象。

若能通過數(shù)據(jù)表變換，在數(shù)據(jù)表中找出個獨立的0元素，然后令中對應這個獨立的0元素取值為1，其它元素取0，也就得到了原問題的最優(yōu)解。因為這樣就可使 達到最小，且實現(xiàn)了選擇最短路線的目的。

2 算法構建

我們的方法是通過數(shù)據(jù)表的行（列）變換，尋找個獨立的0。下面是變換的方法步驟。

第一步，利用行（列）減其最小值，使得變換所得系數(shù)矩陣中含有很多0元素。

第二步，計算覆蓋所有0元素的行和列數(shù)，確定該數(shù)據(jù)表中能找到最多的獨立0元素個數(shù)。

（1）從只有一個0元素的行（列）開始，然后劃去所在列（行）的其他0元素，記作 ；

（2）重復執(zhí)行（1），若同行（列）的0元素至少有兩個，比較這行（列）各0元素所在列（行）中0元素的數(shù)目，選擇0元素少的那列的0元素，然后劃掉同行同列的其它0元素。可重復執(zhí)行，直到所有0元素都已圈出或劃掉。

（3）對沒有0元素的行打√，然后對已打√的行中所含元素 的列打√，再對打有√的列中含有0元素的行打√，直到得不出新的打√的行或列為止。

（4）計算沒有打√的行數(shù)和有打√的列數(shù)的和，就得到0元素獨立個數(shù)。若少于總點數(shù)，則需要重新變換數(shù)據(jù)表。

注意，從第二次開始執(zhí)行數(shù)據(jù)表變換時，選取打√行中所有元素的最小值（除 元），打√行各元素都減去這個最小值，而打√列各元素都加上這個最小值，得到新數(shù)據(jù)表。

3 實例驗證

（1）設巡視檢查的點位為A，B，C，D，E，F(xiàn)；通過百度地圖計算所得的任意兩點距離（自己到自己定義為∞），結果如表2。

（2）對表格按照算法步驟的第一步對數(shù)據(jù)表進行變換得表3。

（3）對表3按照算法步驟2打√，得表4。

（4）由表3知，沒有打√的行數(shù)和打√的列數(shù)之和為4，小于總點數(shù)，此時選取表3中打√行中所有元素最小值（除 元），打√行各元素都減去這個最小值，而打√列各元素都加上這個最小值，得新數(shù)據(jù)表5。

（5）對表4進行打√，得表6。

（6）由表6知，沒有打√的行數(shù)和打√的列數(shù)之和為5，小于總點數(shù)，此時選取表-6中打√行中所有元素的最小值（除 元），打√行各元素都減去這個最小值，而打√列各元素都加上這個最小值，得到新數(shù)據(jù)表7。

此時，此時發(fā)現(xiàn)列中元素出現(xiàn)負值，讓該列各元素加上最小值的絕對值，得數(shù)據(jù)表8。對表8進行打√，得表9。

（7）由表9知，沒有打√的行數(shù)和打√的列數(shù)之和為5，小于總點數(shù)，選取表8中打√行中所有元素的最小值（除 元），打√行各元素都減去這個最小值，而打√列各元素都加上這個最小值，得到新數(shù)據(jù)表10。

對表10按照算法第二步的（1）和（2）處理后，得到表11和表12，沒有可打√的，計算結果為6，0獨立元素個數(shù)為6。

（8）將表10和表11轉化為最優(yōu)解，即為表13，表14。

從表12和表13立刻可以得出最優(yōu)路線A——D——E——F——C——B，或A——B——C——F——E——D。

4 結論

整個算法基于數(shù)據(jù)表，利用的變換只有加減法，沒有復雜乘法、求逆等，計算量很小，可以通過編程有效實施完成。于是也就可以利用該算法快速解決武器快速配送分發(fā)、急行軍路線優(yōu)化選擇、重要安全場地巡視等問題。

參考文獻

[1] Martins E Q，Santos J L.A new shortest paths ranking algorithm[J].Investigacao Operacional，2000.20（1）：47.

[2] 于海璁，陸鋒.一種基于遺傳算法的多模式多標準路徑規(guī)劃方法[J].測繪學報，2014（1）：8.

[3] 宋曉宇，許鴻斐，孫煥良等.基于簽到數(shù)據(jù)的短時間體驗式路徑搜索[J].計算機學報，2013.36（8）：1693.

[4] 唐爐亮，常曉猛，李清泉.出租車經(jīng)驗知識建模與路徑規(guī)劃算法[J].測繪學報，2010（4）：404.

[5] 畢馬威中國大數(shù)據(jù)團隊.洞見數(shù)據(jù)價值大數(shù)據(jù)挖掘要案紀實.清華大學出版社，2018.

[6] 趙衛(wèi)東，董亮.數(shù)據(jù)挖掘實用案例分析.清華大學出版社，2018.2.

[7] James Evans.Business Analytics[M].New York：Person Education Limited，2017.

[8] 陳春寶，鐘飛等.大數(shù)據(jù)與機器學習實踐方法與行業(yè)案例[M].機械工業(yè)出版社，2017.