蓋 森，吳從暉，馬雷雷，朱 江

(1.陸軍指揮學(xué)院，江蘇 南京 210045;2.中國(guó)人民解放軍95291部隊(duì)，湖南 衡陽(yáng) 421000)

在陸戰(zhàn)場(chǎng)各種作戰(zhàn)行動(dòng)中，機(jī)動(dòng)是構(gòu)成作戰(zhàn)基本過(guò)程的一種典型作戰(zhàn)行動(dòng)［1］。因此，構(gòu)建合理的機(jī)動(dòng)路徑規(guī)劃仿真模型，是作戰(zhàn)仿真實(shí)驗(yàn)系統(tǒng)建設(shè)的基礎(chǔ)。

在仿真實(shí)驗(yàn)系統(tǒng)中，現(xiàn)有的路徑規(guī)劃模型，通常只指定機(jī)動(dòng)所經(jīng)過(guò)的地點(diǎn)，然后用若干個(gè)首尾相接的直線段所構(gòu)成的折線表示機(jī)動(dòng)路線。當(dāng)遇到湖泊、河流、雷場(chǎng)等障礙因素時(shí)，通常采取兩種處理方式:強(qiáng)行通過(guò)或停止機(jī)動(dòng)，顯然缺乏合理性。在實(shí)際行動(dòng)中，機(jī)動(dòng)單元會(huì)根據(jù)實(shí)際情況，靈活選擇機(jī)動(dòng)路線(曲線)繞開(kāi)障礙因素。

針對(duì)該問(wèn)題，結(jié)合路徑規(guī)劃相關(guān)技術(shù)與方法，探索適應(yīng)陸戰(zhàn)場(chǎng)環(huán)境下機(jī)動(dòng)單元路徑規(guī)劃仿真模型的研究就顯得極為迫切，不僅有助于提高作戰(zhàn)仿真實(shí)驗(yàn)系統(tǒng)中機(jī)動(dòng)模型的有效性和合理性，還能為機(jī)動(dòng)單元選擇機(jī)動(dòng)路線提供優(yōu)選方案。

1 機(jī)動(dòng)路徑規(guī)劃與最優(yōu)路徑問(wèn)題

在陸戰(zhàn)場(chǎng)，坡度、土質(zhì)、植被、障礙(包括雷場(chǎng)、鐵絲網(wǎng)等)都會(huì)對(duì)機(jī)動(dòng)產(chǎn)生影響，機(jī)動(dòng)單元要通過(guò)某個(gè)區(qū)域必須要付出一定的時(shí)間代價(jià)。因此，選擇機(jī)動(dòng)路線的一般原則是從出發(fā)點(diǎn)到目標(biāo)點(diǎn)進(jìn)行機(jī)動(dòng)所用的時(shí)間最少。

在作戰(zhàn)仿真實(shí)驗(yàn)系統(tǒng)中，作戰(zhàn)行動(dòng)是以一定的時(shí)間步長(zhǎng)進(jìn)行推進(jìn)的［2］，因此，機(jī)動(dòng)時(shí)間同樣以仿真步長(zhǎng)為基本衡量單位，如圖1所示。當(dāng)機(jī)動(dòng)單元的機(jī)動(dòng)性能和地形環(huán)境確定后，根據(jù)計(jì)算模型［3］，單位步長(zhǎng)的機(jī)動(dòng)時(shí)間也將確定。

同時(shí)，作戰(zhàn)仿真實(shí)驗(yàn)系統(tǒng)中陸戰(zhàn)場(chǎng)環(huán)境模型主要是按規(guī)則格網(wǎng)法來(lái)記錄空間數(shù)據(jù)及其相應(yīng)屬性的［4］，如果將機(jī)動(dòng)時(shí)間作為空間數(shù)據(jù)中相鄰格網(wǎng)單元相連構(gòu)成邊的權(quán)值，機(jī)動(dòng)路徑規(guī)劃問(wèn)題就可以轉(zhuǎn)化為最優(yōu)路徑問(wèn)題。相對(duì)于矢量地圖難于進(jìn)行越野機(jī)動(dòng)規(guī)劃［5］，且道路機(jī)動(dòng)規(guī)劃需對(duì)路網(wǎng)數(shù)據(jù)進(jìn)行拓?fù)鋱D構(gòu)造［6］而言，格網(wǎng)模型具有表示簡(jiǎn)單、容易編程實(shí)現(xiàn)的優(yōu)點(diǎn)。

按步長(zhǎng)對(duì)作戰(zhàn)行動(dòng)的推進(jìn)以及按格網(wǎng)對(duì)戰(zhàn)場(chǎng)環(huán)境的劃分，分別從時(shí)間和空間角度為仿真單元機(jī)動(dòng)的離散化模擬提供了基礎(chǔ)，并統(tǒng)一了不同環(huán)境因素影響下的時(shí)間計(jì)算方式，進(jìn)而可以利用圖論中的最優(yōu)路徑算法對(duì)機(jī)動(dòng)路徑規(guī)劃問(wèn)題進(jìn)行分析解決。機(jī)動(dòng)單元路徑的規(guī)劃先于機(jī)動(dòng)行動(dòng)實(shí)施，本文在路徑規(guī)劃中采用地圖格網(wǎng)單元的大小作為途徑點(diǎn)的探索步長(zhǎng)，以避免仿真步長(zhǎng)的大小對(duì)規(guī)劃算法準(zhǔn)確性的影響。

2 最優(yōu)路徑算法分析

對(duì)最優(yōu)路徑問(wèn)題的研究已經(jīng)有多年歷史，形成的最優(yōu)路徑算法也層出不窮，且已應(yīng)用到各個(gè)領(lǐng)域。每種算法具有不同的特點(diǎn)，并沒(méi)有哪一種算法能夠在任何情況下都保持優(yōu)勢(shì)［7］。因此，針對(duì)陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元的路徑規(guī)劃問(wèn)題，首先要對(duì)陸戰(zhàn)場(chǎng)機(jī)動(dòng)的網(wǎng)絡(luò)特性進(jìn)行分析，并結(jié)合常見(jiàn)最優(yōu)路徑算法的特點(diǎn)，對(duì)其進(jìn)行篩選分析，最后對(duì)這些算法進(jìn)行實(shí)驗(yàn)對(duì)比，確定最優(yōu)算法。

2.1 最優(yōu)路徑問(wèn)題的網(wǎng)絡(luò)特性

最優(yōu)路徑問(wèn)題根據(jù)不同的網(wǎng)絡(luò)特性可以進(jìn)行不同的分類(lèi)［8］，如圖2所示。

圖2 最優(yōu)路徑問(wèn)題分類(lèi)

首先，戰(zhàn)場(chǎng)態(tài)勢(shì)是瞬息萬(wàn)變的，機(jī)動(dòng)單元受戰(zhàn)場(chǎng)環(huán)境和態(tài)勢(shì)的影響，其機(jī)動(dòng)性能也將隨之變化，因此，作戰(zhàn)機(jī)動(dòng)的路徑規(guī)劃屬于動(dòng)態(tài)最優(yōu)路徑問(wèn)題。

其次，整個(gè)機(jī)動(dòng)任務(wù)看作由相鄰點(diǎn)構(gòu)成的多次機(jī)動(dòng)子任務(wù)。因此，作戰(zhàn)機(jī)動(dòng)的路徑規(guī)劃屬于單源單目標(biāo)最優(yōu)路徑問(wèn)題。

再次，戰(zhàn)場(chǎng)環(huán)境的空間數(shù)據(jù)模型、戰(zhàn)場(chǎng)態(tài)勢(shì)、作戰(zhàn)單元機(jī)動(dòng)性能以及機(jī)動(dòng)速度的計(jì)算模型一旦確定，就可以通過(guò)最優(yōu)路徑算法求得機(jī)動(dòng)路徑規(guī)劃的最優(yōu)方案。因此，陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元的路徑規(guī)劃屬于確定型最優(yōu)路徑問(wèn)題。

最后，在格網(wǎng)化的戰(zhàn)場(chǎng)環(huán)境空間數(shù)據(jù)中，仿真實(shí)體在任意格網(wǎng)點(diǎn)的機(jī)動(dòng)，只可能與其相鄰八個(gè)方向的格網(wǎng)點(diǎn)具有鄰接關(guān)系，如圖3所示。因此，作戰(zhàn)機(jī)動(dòng)的路徑規(guī)劃屬于稀疏型最優(yōu)路徑問(wèn)題。

圖3 機(jī)動(dòng)路線方向

2.2 常用最優(yōu)路徑算法分析

常用的最優(yōu)路徑算法，主要包括Dijkstra算法［9］、Bellman-Ford算法［10］、Floyd-Warshall算法、動(dòng)態(tài)規(guī)劃算法、A* 算法［11］、SPFA算法［12］等。需要指出的是，蟻群算法、遺傳算法、模擬退火算法等適用場(chǎng)景主要用于TSP(Traviling Salesman Problem，旅行商問(wèn)題)且具有搜索時(shí)間長(zhǎng)、易陷入局部最優(yōu)的缺點(diǎn)［13］，因此這些算法不屬于本文討論的范疇。

本文從圖的角度對(duì)常用最優(yōu)路徑算法進(jìn)行分析，如表1所示。其中V代表圖的頂點(diǎn)數(shù)，E代表圖的邊數(shù)。

表1 常用最優(yōu)路徑算法

其中，動(dòng)態(tài)規(guī)劃算法具有階段劃分及無(wú)后效性的適用條件，決定了其不適用于具有回路的格網(wǎng)圖;Johnson算法在于使Dijkstra算法支持負(fù)權(quán)邊，但對(duì)于陸戰(zhàn)場(chǎng)格網(wǎng)圖，本身就不存在負(fù)權(quán)邊。

因此，理論上適用于陸戰(zhàn)場(chǎng)格網(wǎng)圖的最優(yōu)路徑算法包括Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法、SPFA算法以及A* 算法。其中，Dijkstra算法與A* 算法在計(jì)算時(shí)只需獲取當(dāng)前點(diǎn)的后繼即可，理論上支持的陸戰(zhàn)場(chǎng)格網(wǎng)圖可以無(wú)限大;其他三種算法可以計(jì)算當(dāng)前點(diǎn)與其他所有點(diǎn)之間的最優(yōu)路徑，尤其是Floyd-Warshall算法可以提前計(jì)算所有點(diǎn)之間的最優(yōu)路徑，實(shí)現(xiàn)“一勞永逸”的效果。除此之外，要將算法應(yīng)用到機(jī)動(dòng)單元的路徑規(guī)劃模型中，還要對(duì)陸戰(zhàn)場(chǎng)各種環(huán)境因素對(duì)機(jī)動(dòng)的影響、尋路的區(qū)域與方向等進(jìn)行分析。

3 陸戰(zhàn)場(chǎng)機(jī)動(dòng)路徑規(guī)劃分析

3.1 機(jī)動(dòng)速度

雖然機(jī)動(dòng)過(guò)程會(huì)帶來(lái)一定的油耗和損傷代價(jià)，但機(jī)動(dòng)速度依然是量化作戰(zhàn)單位機(jī)動(dòng)時(shí)最主要的效率指標(biāo)［1］。機(jī)動(dòng)速度取決于機(jī)動(dòng)單元的機(jī)動(dòng)性能與環(huán)境因素，其中機(jī)動(dòng)性能決定了機(jī)動(dòng)單元的標(biāo)準(zhǔn)速度(或平均速度)，環(huán)境因素對(duì)機(jī)動(dòng)速度的影響通常都采用速度修正系數(shù)D(0 ≤D ≤1)來(lái)體現(xiàn)。環(huán)境因素越不利于機(jī)動(dòng)，則D的值越小，反之則越大。因此，機(jī)動(dòng)速度為多種環(huán)境因素綜合影響下的修正速度:

其中vs為當(dāng)前機(jī)動(dòng)單元下的標(biāo)準(zhǔn)速度，Di為修正系數(shù)，vr為隨機(jī)因子。

3.2 環(huán)境因素

影響機(jī)動(dòng)的環(huán)境因素錯(cuò)綜復(fù)雜，要面面俱到顯然是不現(xiàn)實(shí)的，必須要結(jié)合陸戰(zhàn)場(chǎng)環(huán)境模型對(duì)現(xiàn)實(shí)世界的抽象模型與結(jié)構(gòu)化的描述方式，才能使路徑規(guī)劃模型具有實(shí)現(xiàn)的可行性。本文以軍內(nèi)“＊＊戰(zhàn)場(chǎng)地理環(huán)境模型標(biāo)準(zhǔn)”為基礎(chǔ)，對(duì)機(jī)動(dòng)影響因素的分類(lèi)如表2所示。

表2 機(jī)動(dòng)影響因素

各種環(huán)境因素對(duì)速度的影響，同樣通過(guò)修正系數(shù)進(jìn)行調(diào)整，以徒步機(jī)動(dòng)為例，坡度對(duì)速度的修正系數(shù)如表3所示。

表3 坡度對(duì)徒步機(jī)動(dòng)的速度修正系數(shù)

3.3 區(qū)域限制

陸戰(zhàn)場(chǎng)作戰(zhàn)單元的行動(dòng)區(qū)域是有限的，因此，機(jī)動(dòng)路徑規(guī)劃分析必須限制在一定區(qū)域，即根據(jù)出發(fā)點(diǎn)和目標(biāo)點(diǎn)限定最優(yōu)路徑的尋路范圍。區(qū)域限制的目的在于:1)是可以避免對(duì)不必要的區(qū)域進(jìn)行尋路，減少可能路徑數(shù)目急劇增加甚至出現(xiàn)指數(shù)級(jí)爆炸增長(zhǎng)帶來(lái)的影響，進(jìn)而節(jié)約時(shí)間提高效率;2)是避免出現(xiàn)理論上可行而無(wú)現(xiàn)實(shí)意義的繞行方案，例如當(dāng)部隊(duì)遇到無(wú)法通過(guò)的河流時(shí)，可以通過(guò)尋路制定繞路方案，當(dāng)繞路距離太大導(dǎo)致機(jī)動(dòng)時(shí)間超出通過(guò)工程部隊(duì)架設(shè)浮橋通行的代價(jià)時(shí)，該繞路方案便偏離了最初目的，或者繞路太遠(yuǎn)超出了作戰(zhàn)區(qū)域也便失去意義。

在作戰(zhàn)實(shí)驗(yàn)仿真系統(tǒng)中，通常采用三種方式對(duì)機(jī)動(dòng)路徑規(guī)劃的區(qū)域進(jìn)行限制:1)是數(shù)據(jù)限制，即當(dāng)仿真系統(tǒng)只載入了當(dāng)前作戰(zhàn)行動(dòng)的數(shù)字地圖數(shù)據(jù)時(shí)，以數(shù)據(jù)的圖幅范圍進(jìn)行限制即可;2)是自動(dòng)限制，即根據(jù)出發(fā)點(diǎn)和目標(biāo)點(diǎn)的坐標(biāo)范圍，系統(tǒng)自動(dòng)計(jì)算并確定具有一定緩沖距離的外接矩形作為限制區(qū)域;3)是人工限制，即用戶根據(jù)具體的行動(dòng)需求，通過(guò)人機(jī)交互指定一定的區(qū)域范圍進(jìn)行限制，指定方式包括圓形、矩形和多邊形區(qū)域等。

需要強(qiáng)調(diào)的是，區(qū)域限制的方式要根據(jù)實(shí)際情況進(jìn)行選擇，其中人工限制的方式只是提供一種區(qū)域限制的靈活處理方式，對(duì)于大范圍道路稀疏區(qū)，人工限制可能會(huì)導(dǎo)致算法失效，此時(shí)，可采用降低戰(zhàn)場(chǎng)環(huán)境模型格網(wǎng)分辨率的方式(即增大格網(wǎng)大小)的方式進(jìn)行解決。

3.4 尋路方向

陸戰(zhàn)場(chǎng)格網(wǎng)數(shù)據(jù)模型決定了機(jī)動(dòng)單元路徑規(guī)劃，可采用四方向和八方向兩種方式進(jìn)行尋路。雖然，根據(jù)下一個(gè)途徑點(diǎn)結(jié)合行進(jìn)速度和仿真步長(zhǎng)，可以準(zhǔn)確計(jì)算出一個(gè)步長(zhǎng)后機(jī)動(dòng)單元所抵達(dá)的位置，但無(wú)論這個(gè)步長(zhǎng)多小，總會(huì)存在一個(gè)步長(zhǎng)跨越多個(gè)格網(wǎng)的可能性，因此，會(huì)造成機(jī)動(dòng)路線跨越河流等障礙因素的不合理現(xiàn)象。同時(shí)，客觀而言，機(jī)動(dòng)單元不應(yīng)該從當(dāng)前點(diǎn)跳過(guò)相鄰點(diǎn)進(jìn)行機(jī)動(dòng)。這也是本文采用格網(wǎng)單元大小作為探索步長(zhǎng)的原因。因此，對(duì)尋路方向研究的目的在于提高模型的準(zhǔn)確性、合理性。

直觀而言，采用八方向?qū)ぢ犯臃蠈?shí)際情況，可避免四方向?qū)ぢ烦霈F(xiàn)的鋸齒線問(wèn)題。但這種情況并不是絕對(duì)的，例如當(dāng)采用八方向?qū)ぢ窌r(shí)同樣可能出現(xiàn)跨河機(jī)動(dòng)的不合理現(xiàn)象:陸戰(zhàn)場(chǎng)格網(wǎng)數(shù)據(jù)主要是由矢量數(shù)據(jù)轉(zhuǎn)換而成的，河流作為線狀要素，主要通過(guò)線的柵格化轉(zhuǎn)換為格網(wǎng)數(shù)據(jù)，常用的直線段柵格化算法包括DDA法和Bresenham法［14］，這些算法一個(gè)共同的特點(diǎn)是轉(zhuǎn)換后的柵格是八向連通的，如圖4所示。

圖4 八向連通柵格化

此時(shí)，當(dāng)從A出發(fā)點(diǎn)機(jī)動(dòng)到B目標(biāo)點(diǎn)時(shí)，如果采用八方向?qū)ぢ肪蜁?huì)跨過(guò)河流，而采用四方向?qū)ぢ穭t不會(huì)出現(xiàn)此問(wèn)題;同理，當(dāng)圖中直線代表橋梁時(shí)，如果采用四方向?qū)ぢ酚謺?huì)出現(xiàn)無(wú)法通行的問(wèn)題，必須要采用八方向?qū)ぢ?。因此，采用何種尋路方式，要根據(jù)具體的戰(zhàn)場(chǎng)環(huán)境數(shù)據(jù)模型并結(jié)合不同要素對(duì)機(jī)動(dòng)的影響特性綜合確定。此外，如果將矢量數(shù)據(jù)的直線段柵格化算法進(jìn)行改進(jìn)，使其具有四向連通性，則可以采用八方向?qū)ぢ罚鐖D5所示。

圖5 四向連通柵格化

本文對(duì)Bresenham算法進(jìn)行了改進(jìn)，實(shí)現(xiàn)了圖5中矢量數(shù)據(jù)柵格化時(shí)具有四向連通性。即在遞推步進(jìn)過(guò)程中，當(dāng)斜率大于0小于1時(shí)，若當(dāng)前點(diǎn)為(x0，y0)，直線與x=x0+1的交點(diǎn)為y0+Δy，則下一個(gè)推進(jìn)點(diǎn)不是選擇距離最近的單個(gè)像素點(diǎn)，而是根據(jù)Δy選擇單個(gè)或兩個(gè)像素點(diǎn):當(dāng)Δy ＜1時(shí)，推進(jìn)點(diǎn)為(x0+1，y0)，當(dāng)前點(diǎn)更新為該推進(jìn)點(diǎn);當(dāng)Δy≥1，推進(jìn)點(diǎn)為(x0+1，y0)和(x0+1，y0+1)，當(dāng)前點(diǎn)更新為(x0+1，y0+1)。與Bresenham算法相同，當(dāng)斜率大于1時(shí)將縱坐標(biāo)作為推進(jìn)方向，小于0時(shí)，進(jìn)行對(duì)稱(chēng)變換。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證常用最優(yōu)路徑算法對(duì)陸戰(zhàn)場(chǎng)格網(wǎng)數(shù)據(jù)的適用情況，本文使用某地區(qū)1 ∶50 000地圖數(shù)據(jù)進(jìn)行了路徑規(guī)劃實(shí)驗(yàn)，并開(kāi)發(fā)了相應(yīng)的測(cè)試工具。

4.1 實(shí)驗(yàn)環(huán)境

硬件環(huán)境為2.6 GHz Intel Core i7-5600U處理器，16 G內(nèi)存，500 G硬盤(pán);軟件環(huán)境為Win7 64位操作系統(tǒng)、軍內(nèi)某GIS平臺(tái)及Visual Studio 2010集成開(kāi)發(fā)環(huán)境;開(kāi)發(fā)編成語(yǔ)言使用C++和C#。

4.2 實(shí)驗(yàn)方案

首先，利用面向?qū)ο蟮姆椒ㄔO(shè)計(jì)和開(kāi)發(fā)常用的最優(yōu)路徑算法庫(kù)，如圖6所示。其中，SPFA算法采用BFS(Breadth First Search，廣度優(yōu)先搜索)方式及其三種優(yōu)化策 略［15］:SLF(CSP-SPFA-SLF)、LLL(CSP-SPFALLL)及SLF與LLL的結(jié)合(CSP-SPFA-S-L)。

圖6 常用最優(yōu)路徑算法類(lèi)圖

其次，根據(jù)陸戰(zhàn)場(chǎng)環(huán)境因素對(duì)機(jī)動(dòng)的影響，設(shè)計(jì)并開(kāi)發(fā)機(jī)動(dòng)速度修正系數(shù)編輯工具，如圖7所示。其中，機(jī)動(dòng)方式取決于機(jī)動(dòng)單元的機(jī)動(dòng)平臺(tái)，可以根據(jù)實(shí)際情況進(jìn)行擴(kuò)展。

圖7 機(jī)動(dòng)速度修正系數(shù)編輯工具

最后，為了對(duì)比常用最優(yōu)路徑算法在陸戰(zhàn)場(chǎng)格網(wǎng)空間數(shù)據(jù)中的適用情況，本文開(kāi)發(fā)了陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元路徑規(guī)劃測(cè)試工具，如圖8所示為采用A* 算法進(jìn)行尋路的截圖，為了便于展示效果，工具將格網(wǎng)化后的道路信息和河流信息在數(shù)字地圖背景下，作為單獨(dú)的圖層進(jìn)行了突出顯示。其中，粉紅色格網(wǎng)點(diǎn)為道路，淺藍(lán)色為河流，A為出發(fā)點(diǎn)，D為目標(biāo)點(diǎn)，B、C為途徑點(diǎn)，黑色即為路徑規(guī)劃的機(jī)動(dòng)路線結(jié)果。

圖8 陸戰(zhàn)場(chǎng)機(jī)動(dòng)路徑規(guī)劃測(cè)試工具

實(shí)驗(yàn)抽取數(shù)字地圖數(shù)據(jù)中某方形區(qū)域作為限制區(qū)域，并在限制區(qū)域內(nèi)均勻選擇多個(gè)點(diǎn)相互作為出發(fā)地和目標(biāo)點(diǎn);然后，應(yīng)用常用最優(yōu)路徑算法對(duì)出發(fā)點(diǎn)和目標(biāo)點(diǎn)進(jìn)行路徑規(guī)劃計(jì)算，并進(jìn)行統(tǒng)計(jì)分析。

4.3 實(shí)驗(yàn)結(jié)果與分析

本文首先對(duì)多源多目標(biāo)算法Floyd-Warshall算法進(jìn)行了驗(yàn)證，其計(jì)算效率如表4所示(結(jié)果取3次平均值)。其中限制區(qū)域?qū)捴傅氖欠叫螀^(qū)域每行每列的格網(wǎng)數(shù)，時(shí)間T為所有節(jié)點(diǎn)間最優(yōu)路徑的計(jì)算時(shí)間。

表4 Floyd-Warshall算法時(shí)間統(tǒng)計(jì)

可以看到，F(xiàn)loyd-Warshall算法的時(shí)間復(fù)雜度基本符合O(V3)，根據(jù)實(shí)驗(yàn)數(shù)據(jù)，可推算出將限制區(qū)域擴(kuò)大到一幅1 ∶50 000地圖的計(jì)算時(shí)間:若以50米為格網(wǎng)寬度進(jìn)行劃分，一幅1 ∶50000地圖的范圍約27公里* 18公里，則節(jié)點(diǎn)數(shù)V約為540* 360=194 400個(gè)，根據(jù)時(shí)間復(fù)雜度得出Floyd-Warshall算法的計(jì)算時(shí)間約為88天!可以得出Floyd-Warshall算法不具有可行性的結(jié)論。

接下來(lái)，繼續(xù)擴(kuò)大限制區(qū)域?qū)ζ渌惴ㄟM(jìn)行實(shí)驗(yàn)，隨著區(qū)域?qū)挾鹊脑黾?，單?duì)出發(fā)點(diǎn)和目標(biāo)點(diǎn)的計(jì)算時(shí)間變化如圖9所示。

圖9 不同區(qū)域?qū)挼乃惴ㄐ蕦?duì)比

可以看出，Bellman-Ford算法的效率遠(yuǎn)低于其他算法，且其他算法的效率在小區(qū)域范圍難以分出伯仲。最后，本文將限制區(qū)域?qū)挾葦U(kuò)大到900，對(duì)Dijkstra算法、SPFA及其優(yōu)化算法、A* 算法進(jìn)行了效率對(duì)比實(shí)驗(yàn)，結(jié)果如圖10所示。需要強(qiáng)調(diào)的是，A* 算法的關(guān)鍵在于啟發(fā)式函數(shù)［16］，本文為了保證算法的一致性要求，將啟發(fā)式函數(shù)——機(jī)動(dòng)時(shí)間代價(jià)估計(jì)設(shè)為

其中dis(n，target)為當(dāng)前尋路節(jié)點(diǎn)n與目標(biāo)點(diǎn)的距離，四方向?qū)ぢ窞槁D距離，八方向?qū)ぢ窞闅W氏距離;vs為機(jī)動(dòng)單元在不受任何環(huán)境因素影響下的標(biāo)準(zhǔn)速度。

圖10 不同區(qū)域?qū)挼乃惴ㄐ蕦?duì)比

從圖中可以直觀地得出算法效率由高到低為:A*＞SPFA-SLF ＞SPFA ＞SPFA-LLL ≈SPFA-S-L ＞Dijkstra。

最后，通過(guò)以上實(shí)驗(yàn)可以得出:陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元路徑規(guī)劃，在作戰(zhàn)區(qū)域內(nèi)，當(dāng)出發(fā)點(diǎn)已知，在機(jī)動(dòng)命令下達(dá)前，可以采用SPFA的SLF優(yōu)化算法對(duì)機(jī)動(dòng)路徑進(jìn)行預(yù)規(guī)劃，機(jī)動(dòng)命令下達(dá)后可實(shí)時(shí)獲取最優(yōu)機(jī)動(dòng)路線;當(dāng)機(jī)動(dòng)單元已在機(jī)動(dòng)過(guò)程中，隨著戰(zhàn)場(chǎng)態(tài)勢(shì)的變化，遇到突發(fā)情況(密集火力打擊、遭遇布設(shè)雷區(qū)等)需要臨機(jī)調(diào)整路線時(shí)，可采用A* 算法對(duì)機(jī)動(dòng)路徑進(jìn)行重新規(guī)劃。

5 結(jié)束語(yǔ)

陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元路徑規(guī)劃模型，是陸軍作戰(zhàn)實(shí)驗(yàn)仿真系統(tǒng)中的基礎(chǔ)模型。本文針對(duì)現(xiàn)有機(jī)動(dòng)模型以直線作為機(jī)動(dòng)路徑帶來(lái)的不合理問(wèn)題，基于格網(wǎng)空間數(shù)據(jù)模型，從網(wǎng)絡(luò)特性和圖論角度，分析了通過(guò)最優(yōu)路徑規(guī)劃算法解決該問(wèn)題的可行性。從機(jī)動(dòng)速度、環(huán)境因素、區(qū)域限制和尋路方向四個(gè)方面，分析了陸戰(zhàn)場(chǎng)機(jī)動(dòng)路徑規(guī)劃需重點(diǎn)把握的關(guān)鍵環(huán)節(jié)。最后，本文開(kāi)發(fā)了算法庫(kù)和測(cè)試工具，通過(guò)實(shí)驗(yàn)，分析了常用最優(yōu)路徑規(guī)劃算法對(duì)陸戰(zhàn)場(chǎng)格網(wǎng)空間數(shù)據(jù)模型的適用情況，并進(jìn)行了效率對(duì)比，得出陸戰(zhàn)場(chǎng)機(jī)動(dòng)單元路徑規(guī)劃仿真模型最宜采用的兩種算法:SPFA-SLF算法與A* 算法，及二者具體的應(yīng)用場(chǎng)景。