通過水雷障礙群的最短路徑尋徑問題研究*

龍 鵬 林 平 張年春

1 引言

已知水域中水雷位置和危險半徑,但是任務(wù)緊迫,來不及清掃水雷,或者水雷障礙群為我方所布不能清掃,而且由于水雷障礙群過于龐大或者可能處于水道中無法繞行,此時水面艦艇編隊需掃雷艦緊急引導(dǎo)航渡通過水雷障礙群。為保證水面艦艇編隊安全迅速通過從而及時完成作戰(zhàn)任務(wù)或到達(dá)指定海域,我們需要在水雷障礙群中尋找一條最短通行路徑以達(dá)到快速通過的目的。戰(zhàn)斗部隊面對這一問題時目前基本上都是憑經(jīng)驗尋徑通過。當(dāng)水雷障礙群水雷數(shù)較多,種類繁雜的時候,我們可以利用計算機(jī)運(yùn)算速度快的特點尋找一種使用計算機(jī)快速解算通過水雷障礙群所需最短路徑的方法。利用這種方法得到的路徑可以輔助指揮員參考決策,大大減輕指揮員的負(fù)擔(dān),因此具有重大的戰(zhàn)術(shù)意義。

2 水雷障礙群的量化建模方法

2.1 柵格量化模型

2.1.1 柵格及柵格連接性的概念

將水雷障礙群如圖1所示劃分成等大小的柵格,再對這些柵格如圖2所示進(jìn)行預(yù)先初始化使其變?yōu)闁鸥窆?jié)點和具有連接各相鄰節(jié)點的具有路長的邊,然后再在此基礎(chǔ)上對其進(jìn)行最短尋徑計算即可。

水雷障礙群柵格量化模型中的每一個柵格節(jié)點只與其鄰近的節(jié)點連接,因此必須確定每個節(jié)點與鄰近節(jié)點的是否連接和連接路徑的路長,如在圖2中黑點所在柵格表示為((8bits)01101111),每1bit表示從此柵格節(jié)點出發(fā)向相應(yīng)數(shù)字所在方向是否可通過。

2.1.2 柵格的構(gòu)造方法

1)柵格大小的選取

柵格尺寸大小的選取需折衷考慮算法搜索空間的大小、運(yùn)算時間的長短以及解算得到最短路徑的精度等問題。一般來說,柵格取的越小,相應(yīng)的路徑精度及可接受性就越高,但是運(yùn)算的時間、空間代價也會相應(yīng)的增加不少,此外還需綜合考慮艦艇導(dǎo)航精度誤差及一般水雷的爆炸威力半徑,因此在這里推薦取1鏈作為柵格長寬的大小。

2)柵格連接性的判斷方法

在圖2中,任意兩個柵格之間是否連通主要從兩個方面來討論:

(1)連線平行或垂直于航線方向上的兩個柵格節(jié)點:如圖3中的G、H柵格節(jié)點連線(設(shè)航線方向為從下至上)垂直于航線方向,在其鄰近區(qū)域各取一半柵格作為這兩個柵格的連接區(qū)域(如圖中陰影所示),我們可以將這個連接區(qū)域看作是無數(shù)條與這兩個柵格節(jié)點連線垂直的連接線段組成,如果這兩個柵格所構(gòu)成的連結(jié)區(qū)域中的任一一條連接線段完全包含于某水雷威脅圓中,則判定這兩個柵格無法連接,如圖3中的C、D柵格在D柵格中有一條連接線段(虛線所示)完全包含于水雷威脅圓Y中,因此我們判斷C、D柵格無法連通;

(2)節(jié)點連線與航線斜交的兩個柵格,如果有兩顆相切或者相交的水雷的連線與這兩個柵格節(jié)點的連線相交則判斷這兩個柵格之間無法連通;如果這兩個柵格節(jié)點都包含在某水雷威脅圓中,也判斷其無法連通。在圖3中的A、B柵格節(jié)點,雖然XY兩個水雷威脅圓沒有相交,但是因為這兩個節(jié)點被完全包含于Y中,因此也判斷其為無法連接。

水雷威脅圓半徑的取值應(yīng)該保證兩個威脅圓如果即使相切,水面艦艇亦可在兩個水雷之間通過,因此水雷威脅半徑可取值為

圖3 柵格節(jié)點連接判斷

從圖1可以看出柵格量化模型中判斷兩個柵格之間是否連通的精確度的大小,獲得路徑的可行性的高低主要依賴于柵格的大小,柵格越小,則判斷精度越準(zhǔn)確,但是相應(yīng)計算量也將增加。

2.2 包可視圖量化模型

2.2.1 包可視圖的概念

在模仿人類的智能行為中,有一個更加復(fù)雜的地方,那就是電腦沒有視覺。人類只要瞟上幾眼,就可以從中獲得豐富的信息,但是對電腦來說就太困難了。針對這種情況我們可以使用包這個簡單而強(qiáng)大的將障礙包圍起來的幾何閉合圖形來對這種行為進(jìn)行仿真,包占用的內(nèi)存很小,而且效率很高,此外還具有一定的精確度。包幾乎在RTS游戲引擎中的每一種區(qū)域上都可以得到使用,它使得復(fù)雜的人工智能行為的創(chuàng)建更容易實現(xiàn),這是因為它們可以讓開發(fā)人員快速的得到一個區(qū)域的障礙情況。可視圖法是由麻省理工學(xué)院的Tomas Lozano.Perez和IBM研究院的MichaelA.Wesley于1979年提出的,如圖4所示,其最大特點是在表達(dá)障礙物的多邊形包中探尋出各個包上的包絡(luò)點之間的連接情況。圖4左側(cè)表示某一個水雷障礙群,右側(cè)是構(gòu)造出的對應(yīng)于左側(cè)水雷障礙群的包可視圖,并繪出了右下角包的包絡(luò)點的連接情況。

圖4 包可視圖概念及應(yīng)用

2.2.2 包可視圖的構(gòu)造方法

1)包的構(gòu)造方法

只給出了水雷障礙群中各個水雷的坐標(biāo)及威脅半徑,因此首先要在此基礎(chǔ)上構(gòu)造包。如圖5所示,首先將相切或相交的水雷連線成凝聚水雷群,各個凝聚水雷群將按照各個不同凝聚情況構(gòu)成相應(yīng)的包:

(1)單個水雷。依照順航線方向在水雷威脅圓上的前后左右分別定位四個包絡(luò)點,將這四個包絡(luò)點連接即可構(gòu)成單個水雷的包;

(2)兩個水雷構(gòu)成的凝聚水類群。將兩個水雷點的連線分別向兩側(cè)平移一個水雷威脅半徑(即與兩個水雷威脅圓相切)可得四個切點,將連線反向延長一個水雷威脅半徑又可得兩個包絡(luò)點(即與水雷威脅圓的交點),將這六個包絡(luò)點相連即可;

(3)不規(guī)則的凝聚水雷群。凝聚水雷群兩端及處于水雷連線夾角外側(cè)的包絡(luò)點按照(B)的方法定出,再將每一個折角的角平分線向兩側(cè)延長一個水雷威脅半徑即可得到相對應(yīng)的包絡(luò)點,將所有包絡(luò)點依次相連即可得到不規(guī)則凝聚群的包;

(4)構(gòu)成環(huán)的凝聚水雷群。如果凝聚水雷群線連接成環(huán),將每一個折角的角平分線向外側(cè)延長一個水雷威脅半徑即可得到相對應(yīng)的包絡(luò)點,再將每連線向外側(cè)平移與這兩個水雷威脅圓相切可得相應(yīng)切點,將這些包絡(luò)點依次連接即得到構(gòu)成環(huán)的凝聚水雷群構(gòu)成的包。

2)邊的構(gòu)造方法

所有的包構(gòu)造出來以后,我們已經(jīng)得到n個包m個包絡(luò)點,再將水雷障礙群的進(jìn)入邊界和駛出邊界虛構(gòu)成一個開始頂點和一個結(jié)束頂點即共m+2個包絡(luò)點,運(yùn)用包可視圖法我們還需要將所有的可用邊構(gòu)造出來,共分為三種情況:

圖5 包可視可圖與構(gòu)建方法

(1)包上連接每兩個相鄰包絡(luò)點的邊;

(2)如果有兩個不處在同一個包的包絡(luò)點的可以無障礙連接,則將連接這兩個包絡(luò)點的邊加入可視圖;

(3)如果包上的包絡(luò)點與任意一個虛構(gòu)的包絡(luò)點能夠無障礙垂直連接,即將這條連接邊加入可視圖中。

無障礙連接就是指兩個包絡(luò)點之間的連線沒有穿過任何一個包,如圖5中右下角包的所有邊,其判斷的方法是:將這兩個包絡(luò)點連接的邊與每一個包上不包含這兩個包絡(luò)點第(1)類邊進(jìn)行遍歷計算看是否有相交,如果沒有則這兩個包絡(luò)點可以無障礙連接。

3 通過水雷障礙群的最短路徑尋徑改良算法

上面已經(jīng)對水雷障礙群的量化建模方法進(jìn)行了描述。在量化建模的基礎(chǔ)上,我們可以利用許多的最短路徑尋徑算法如Dijkstra、Floyd和A*自啟發(fā)算法進(jìn)行最短路徑的求解。由于柵格量化模型類似于迷宮模型,因此我們可以結(jié)合Dijkstra算法和A*自啟發(fā)算法的優(yōu)點得到一個更高效的改良算法。對于包可視圖模型來說,利用這三種算法的任意一種都可以很好的運(yùn)算。

3.1 柵格模型最短路徑尋徑改良算法

因為所尋路徑都是從航線的起始邊界進(jìn)入到雷區(qū)然后從終止邊界駛出雷區(qū),所以將起始邊界和終止邊界虛擬為一個起始節(jié)點和終止節(jié)點,起始節(jié)點和終止節(jié)點分別到其相應(yīng)邊界柵格節(jié)點的距離為0,包可視圖法中包上各包絡(luò)點到邊界的垂直的邊即可以視為其連接起始節(jié)點或終止節(jié)點的邊。將一個多個起始節(jié)點和多個終止節(jié)點的問題轉(zhuǎn)化為單個起始節(jié)點到單個終止節(jié)點的最短路徑尋徑問題,這樣運(yùn)用最短路徑尋徑算法時一次計算即可得出結(jié)果,而不必進(jìn)行多次重復(fù)計算出每一對起始節(jié)點和終止節(jié)點的最短路徑以后再從這些最短路徑里選擇路長值最小的路徑。

Dijkstra算法的精要在于其每次尋找使路徑距離增加最小的柵格加入路徑,A*自啟發(fā)算法則主要體現(xiàn)了尋徑的方向性,即優(yōu)先將向終止節(jié)點接近最迅速的節(jié)點加入路徑。將兩者結(jié)合起來,即是新加入路徑的節(jié)點必須滿足三個條件:

1)方向性的要求使得應(yīng)優(yōu)先選擇向終止邊界靠近最快的節(jié)點,因為算法欲到達(dá)的終止節(jié)點位于水雷障礙群的終止邊界上;

2)所加入當(dāng)前路徑節(jié)點必須使所有路徑長的和增加最少;

3)新加入的節(jié)點必須也只可能是未使用節(jié)點,因為從當(dāng)前節(jié)點出發(fā)探尋到一個已經(jīng)標(biāo)記為使用的節(jié)點,那就說明在先前的操作中這個節(jié)點因為對總的路徑和最少的貢獻(xiàn)已經(jīng)加入了路徑,通過別的路徑到達(dá)這一節(jié)點的肯定已經(jīng)不是最短路徑到達(dá)。

3.2 柵格模型的改良最短路徑尋徑演示

1)如圖6所示,水面艦艇編隊從南往北航行時,結(jié)合Dijkstra和A*算法思想,對于每一個柵格節(jié)點,確定其優(yōu)先連接下一節(jié)點的次序為(B)所示。

圖6 柵格模型尋徑演示

2)然后用Dijkstra算法和(B)所示的優(yōu)先度計算出最短路徑如(A)中粗線所示,其他細(xì)線為計算時同時產(chǎn)生的備用路徑。

3.3 包可視圖模型的最短路徑尋徑演示(圖7)

4 結(jié)語

圖7 包可視圖模尋徑演示

從最后的尋徑演示來看,通過將水雷障礙群量化為離散柵格節(jié)點或包可視圖后利用改良的最短路徑尋徑算法能夠找到正確的路徑,因此水面艦艇依據(jù)這一算法利用計算機(jī)能夠快速得到所需路徑,從而為指揮員提供了額外的一種指引艦艇編隊迅速安全通過水雷障礙群順利到達(dá)指定海域或者完成作戰(zhàn)任務(wù)的方法。

[1]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,2003

[2]楊科選.人工智能尋路算法及其在游戲中的應(yīng)用研究[D].長沙:中南大學(xué)碩士學(xué)位論文,2009

[3]胡潔萍.最短路徑求解的教學(xué)問題[J].北京印刷學(xué)院學(xué)報,2004,12(1):54

[4]陳中標(biāo).最短路徑若干算法的程序?qū)崿F(xiàn)及比較分析[J].貴陽學(xué)院學(xué)報(自然科學(xué)版),2009,4(2):1

[5]鄧禮禮,孫強(qiáng).求圖中頂點之間所有最短路徑的一種算法[J].計算機(jī)應(yīng)用與軟件,2009,26(10):8

[6]張玉娟.空間里兩點之間最短路徑問題[J].經(jīng)濟(jì)技術(shù)協(xié)作信息,2007(924):81

[7]張曉玲.經(jīng)典Dijkstra算法及其改進(jìn)的分析比較[J].SCINCE&TECHNOLOGY INFORMATION,2009(27):170

[8]李政.基于存儲結(jié)構(gòu)的Dijkstra算法優(yōu)化[J].桂林示范高等專科學(xué)校學(xué)報,2007,21(2):129

[9]宋航,吳力合,呂明.Dijkstra算法在部隊快速行進(jìn)中的應(yīng)用[J].武警工程學(xué)院學(xué)報,2003,19(6):72

[10]何清林.Floyd算法的景區(qū)最短路徑查詢系統(tǒng)的設(shè)計與實現(xiàn)[J].電腦編程技巧與維護(hù),2010(1):35