姚俊萍　李新社　李曉軍

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

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

中圖分類(lèi)號(hào)：TP274 文獻(xiàn)標(biāo)識(shí)碼：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)計(jì)、數(shù)據(jù)挖掘、預(yù)報(bào)、文本挖掘和優(yōu)化。優(yōu)化方法從前一直被忽視，但發(fā)展前景不可小視。比如軍事比武路徑優(yōu)選、安全警勤巡查路線優(yōu)選、武器快速配發(fā)、快件快速投遞，將優(yōu)化方法應(yīng)用在這幾個(gè)領(lǐng)域，可以節(jié)約資源、節(jié)省時(shí)間，尤其是在軍事斗爭(zhēng)領(lǐng)域可以提高戰(zhàn)斗力。這里以軍事比武路徑優(yōu)選為例，每個(gè)參與比武的選手必須在某個(gè)區(qū)域內(nèi)的所規(guī)定位置必須巡視一次，也只需一次，然后回到出發(fā)點(diǎn)。至于如何規(guī)劃行走路線可以八仙過(guò)海，各顯神通。再假設(shè)比武工具為摩托車(chē)，幾乎不受交通影響，且各道路行走難易程度一樣。

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

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

假設(shè)巡視點(diǎn)為A、B、C、D、E、F，通過(guò)百度地圖計(jì)算各巡視點(diǎn)的距離如表1所示。

當(dāng)不等于時(shí)為百度地圖計(jì)算出的值，等于時(shí)為∞。

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

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

數(shù)據(jù)表中的一行（列）各元素減去該行列的最小元素，得到新的表格數(shù)據(jù)。原、新兩個(gè)表格數(shù)據(jù)求解結(jié)果相同，這是因?yàn)榈侥滁c(diǎn)距離同時(shí)增大或縮小相同值與選擇合適路徑無(wú)關(guān)，猶如在五個(gè)數(shù)中選出最小的那一個(gè)，所有數(shù)據(jù)同時(shí)增加或減小相同值不改變選擇的對(duì)象。

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

2 算法構(gòu)建

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

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

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

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

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

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

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

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

3 實(shí)例驗(yàn)證

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

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

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

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

（5）對(duì)表4進(jìn)行打√，得表6。

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

[2] 于海璁，陸鋒.一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J].測(cè)繪學(xué)報(bào)，2014（1）：8.

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

[4] 唐爐亮，常曉猛，李清泉.出租車(chē)經(jīng)驗(yàn)知識(shí)建模與路徑規(guī)劃算法[J].測(cè)繪學(xué)報(bào)，2010（4）：404.

[5] 畢馬威中國(guó)大數(shù)據(jù)團(tuán)隊(duì).洞見(jiàn)數(shù)據(jù)價(jià)值大數(shù)據(jù)挖掘要案紀(jì)實(shí).清華大學(xué)出版社，2018.

[6] 趙衛(wèi)東，董亮.數(shù)據(jù)挖掘?qū)嵱冒咐治?清華大學(xué)出版社，2018.2.

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

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