李宏彪，張永亮

（華北計(jì)算技術(shù)研究所北京100083）

潛艇的航線規(guī)劃是指在已有地形數(shù)據(jù)的基礎(chǔ)之上，根據(jù)潛艇的潛水深度范圍以及可作戰(zhàn)需求，進(jìn)行三維空間分析規(guī)劃出一條合理且路程較近的航線。多數(shù)情況下，是基于Dem數(shù)據(jù)進(jìn)行分析規(guī)劃的，但往往某些海域并無詳細(xì)可靠的Dem數(shù)據(jù)，而只有比較粗糙的水深底質(zhì)或等深線數(shù)據(jù)，所以本文結(jié)合參考文獻(xiàn)5的分治算法構(gòu)造不規(guī)則三角網(wǎng)的方法，設(shè)計(jì)了一種通過水深底質(zhì)或等深線數(shù)據(jù)快速計(jì)算Dem數(shù)據(jù)用來作為三維空間分析規(guī)劃的基礎(chǔ)。此方法效率較高，完全達(dá)到了實(shí)時(shí)航線規(guī)劃的要求。

如此密集的網(wǎng)格利用地杰斯特拉算法進(jìn)行航線規(guī)劃復(fù)雜度太高，而A星雖然效率高，但在柵格數(shù)據(jù)下會(huì)走太多的彎路，所以目前解決這類航線規(guī)劃的方法主要是智能優(yōu)化算法，例如蟻群算法、遺傳算法等方法在全局范圍內(nèi)搜索較優(yōu)航線，但大多數(shù)方法效率還是達(dá)不到實(shí)時(shí)航線規(guī)劃的效果。本文設(shè)計(jì)了一種A星加模擬退火算法的方式來進(jìn)行分析規(guī)劃航線，這樣A星的作用是保證效率，模擬退火的作用是保跳出局部最優(yōu)在全局范圍內(nèi)搜索，將二者優(yōu)勢(shì)相互結(jié)合，通過實(shí)驗(yàn)得到了比較理想的效果[1-11]。

1 基于不規(guī)則三角網(wǎng)的Dem插值

首先根據(jù)水深底質(zhì)離散點(diǎn)構(gòu)造三角網(wǎng)（圖1），然后遍歷三角網(wǎng)中的每一個(gè)三角形對(duì)三角形內(nèi)Dem值未知的網(wǎng)格點(diǎn)根據(jù)公式（1）進(jìn)行插值（圖2），由于潛艇本身具有一定的寬度和長度，所以在通過Dem柵格塊時(shí)要保證其直行或轉(zhuǎn)彎時(shí)可以通過，為此我們選取的網(wǎng)格寬度為大于等于潛艇長度的兩倍。在三角形ABC中O為待插值網(wǎng)格點(diǎn)其坐標(biāo)為（x，y），三角形 ABC 的三點(diǎn)坐標(biāo)分別為，高程值分別為

圖1 構(gòu)造三角網(wǎng)

圖2 三角形內(nèi)網(wǎng)格點(diǎn)的插值

設(shè)O到A的距離為LOA，O到B的距離為LOB，O到C的距離為LOC。根據(jù)距離對(duì)點(diǎn)O的Dem值DEMO成反比的假設(shè)，可得對(duì)O點(diǎn)的Dem插值公式為：

算法步驟[5]：

1）根據(jù)所需要的Dem密度構(gòu)建網(wǎng)格。

2）根據(jù)高程離散點(diǎn)利用分治算法構(gòu)造Delaunay三角網(wǎng)。

3）遍歷三角網(wǎng)中的每一個(gè)三角形，對(duì)內(nèi)Dem值未知的網(wǎng)格點(diǎn)，根據(jù)公式（1）進(jìn)行插值計(jì)算。

2 構(gòu)造Delaunay三角網(wǎng)的具體步驟

2.1 局部最優(yōu)化處理

理論上為了構(gòu)造Delaunay三角網(wǎng)，Lawson提出的局部優(yōu)化過程LOP（Local Optimization Procedure），一般三角網(wǎng)經(jīng)過LOP處理，即可確保成為Delaunay三角網(wǎng)，其基本做法如下所示[7]：

1）將兩個(gè)具有共同邊的三角形合成一個(gè)多邊形。

2）以最大空?qǐng)A準(zhǔn)則作檢查，看其第4個(gè)頂點(diǎn)是否在三角形的外接圓之內(nèi)。

3）如果在，修正對(duì)角線即將對(duì)角線對(duì)調(diào)，即完成局部優(yōu)化過程的處理。

LOP處理過程如圖3所示。

2.2 Delaunay三角網(wǎng)的構(gòu)造算法大體步驟

1）構(gòu)造一個(gè)超級(jí)三角形，包含所有散點(diǎn)，放入三角形鏈表。

圖3 LOP處理過程

2）將點(diǎn)集中的散點(diǎn)依次插入，在三角形鏈表中找出其外接圓包含插入點(diǎn)的三角形（稱為該點(diǎn)的影響三角形），刪除影響三角形的公共邊，將插入點(diǎn)同影響三角形的全部頂點(diǎn)連接起來，從而完成一個(gè)點(diǎn)在Delaunay三角形鏈表中的插入。

3）根據(jù)優(yōu)化準(zhǔn)則對(duì)局部新形成的三角形進(jìn)行優(yōu)化。將形成的三角形放入Delaunay三角形鏈表。

4）循環(huán)執(zhí)行上述第2）步，直到所有散點(diǎn)插入完畢[7]。

這一算法的關(guān)鍵的第2）步如圖4所示。

圖4 第2）步的操作過程示意圖

為提高效率本文在構(gòu)造三角網(wǎng)時(shí)采用的是參考文獻(xiàn)[5]的分治算法，實(shí)驗(yàn)證明效率可大大提高[5]。

3 利用A星算法求出起點(diǎn)到終點(diǎn)的一條合理路徑

在潛艇的潛水深度確定的情況下，一條合理路徑就是找到一條可以由起點(diǎn)到末點(diǎn)的路徑保證潛艇由此路徑通過時(shí)不會(huì)觸礁且此路徑規(guī)避敵方打擊區(qū)域。

在已通過插值計(jì)算出的Dem數(shù)據(jù)中，可以很快計(jì)算出哪些Dem柵格可以通過，哪些不可通過，即潛艇的可行區(qū)域。在此可行區(qū)域上可以利用A星算法求出一條合理路徑。A星算法的基本思想與具體步驟如下。

每當(dāng)主角走一步，就在身邊的8個(gè)方向插上節(jié)點(diǎn)編輯，然后使用探路器，探路器會(huì)告訴主角，插的哪個(gè)節(jié)點(diǎn)標(biāo)記距離目標(biāo)的路徑比較短，然后下一步就走向那里，走到之后，準(zhǔn)備又插，發(fā)現(xiàn)，有的地方已經(jīng)插過了，或者旁邊有障礙物，不能插，就替換插過的節(jié)點(diǎn)的父節(jié)點(diǎn)，比較，是不是比當(dāng)前的短，如果是，就讓當(dāng)前的父節(jié)點(diǎn)等于，被替換的父節(jié)點(diǎn)。

從A星算法的基本思想可以看到A星算法結(jié)果唯一，這樣其實(shí)它就是一個(gè)帶有方向指導(dǎo)的廣度尋路算法，所以其不具備隨機(jī)性，所以它只可能繞開障礙物，找到一個(gè)較優(yōu)的代價(jià)路線，對(duì)于智能地放棄當(dāng)前最優(yōu)進(jìn)而尋找另一條更加優(yōu)越的代價(jià)路線做不到，通俗地說它只顧當(dāng)下而不考慮全局。尤其在此種密集的網(wǎng)格數(shù)據(jù)中A星算法的弊端更是明顯，當(dāng)遇到障礙物時(shí)它在不斷地試探靠近目標(biāo)時(shí)走了太多的彎路，所以A星算法只可以找到一條合理繞開障礙物的較優(yōu)的代價(jià)路線，但所以為實(shí)現(xiàn)在全局范圍內(nèi)搜索一條較優(yōu)的代價(jià)路線必須引入帶有隨即性質(zhì)可以跳出局部最優(yōu)的優(yōu)化算法。下一小節(jié)設(shè)將計(jì)一種A星+模擬退火算法尋找一條實(shí)用的規(guī)劃路徑。

4 A星+模擬退火算法尋找較優(yōu)路徑

算法設(shè)計(jì)主要思想：由于A星算法的弊端，必須引入一種優(yōu)化算法從全局搜索的角度出發(fā)，來解決其走太多的彎路的問題。其主要思路就是以A星算法規(guī)劃出的路徑為基礎(chǔ)，設(shè)定一種地理環(huán)境的隨機(jī)改變與原始路徑的隨機(jī)取舍再利用A星算法求出一條合理的路徑，將此路徑與原路徑進(jìn)行代價(jià)比較，利用模擬退火的思想進(jìn)行取舍，經(jīng)過模擬退火的充分降溫，最后得到一條合理并且行程較短的實(shí)用路徑，這里目標(biāo)函數(shù)就是全路徑的路程長度。

5 試驗(yàn)結(jié)果與分析

試驗(yàn)平臺(tái)是Microsoft Windows XP操作系統(tǒng)，機(jī)器配置為主頻2.93 GHz，內(nèi)存為2.93 GB，采用VC++6.0實(shí)現(xiàn)，實(shí)驗(yàn)數(shù)據(jù)為某海域水深底質(zhì)數(shù)據(jù)，潛水深度為865米到700米。

構(gòu)造三角網(wǎng)效果如圖5所示。

利用A星算法求出起點(diǎn)到終點(diǎn)的一條合理路徑效果如下：

A星+模擬退火算法尋找較優(yōu)路徑效果如圖6所示。

實(shí)驗(yàn)各步驟性能（耗時(shí)）：

構(gòu)造三角網(wǎng)，耗時(shí)578 ms。

圖5 構(gòu)造三角網(wǎng)

圖6 A星+模擬退火算法尋找較優(yōu)路徑

Dem插值，耗時(shí)556 ms。

尋找較優(yōu)路徑效，843 ms。

共計(jì)1 977 ms，而原始的方法耗時(shí)6 788 ms，性能提高了70%。

實(shí)驗(yàn)結(jié)果表明：

1）基于水深底質(zhì)可以快速地生成Dem數(shù)據(jù)，根據(jù)潛艇的潛水深度可以快速計(jì)算出其可行區(qū)域，在此基礎(chǔ)上可以利用A星算法計(jì)算復(fù)雜度低的特性快速計(jì)算出一條合理的路線；

2）在柵格數(shù)據(jù)下A星算法計(jì)算出合理的路線彎路太多，在實(shí)際中無法作為一條潛艇的航行路線；

3）A星算法計(jì)算出合理的路線為基礎(chǔ)結(jié)合模擬退火算法的全局搜索，可以去除A星算法走太多的彎路的弊端；

4）實(shí)驗(yàn)結(jié)果表明A星算法的高效率加上模擬退火算法的全局搜索，可以快速地規(guī)劃處一條合理且較優(yōu)的水下航行路線。

6 結(jié)論

在潛艇在水下的航線規(guī)劃中，A星算法雖然具有效率高的優(yōu)勢(shì)，但存在著規(guī)劃路徑復(fù)雜的缺陷，地杰斯特拉算法雖然具有規(guī)劃出最優(yōu)的路線但存在著算法復(fù)雜度高的缺陷。文中將水深底質(zhì)數(shù)據(jù)通過三角網(wǎng)Dem插值后，基于插值計(jì)算出的Dem數(shù)據(jù)，將A星算法與模擬退火算法綜合應(yīng)用，這樣可以既利用了A星算法效率高的優(yōu)勢(shì)，而且可以通過模擬退火算法進(jìn)行優(yōu)化使得A星算法規(guī)劃出的路徑復(fù)雜的問題解決，達(dá)到快速規(guī)劃出潛艇在水下的合理并且實(shí)用航線。實(shí)驗(yàn)表明，該方法在耗時(shí)時(shí)間與航線的合理程度上有比較實(shí)用的優(yōu)勢(shì)。但同時(shí)，在實(shí)際應(yīng)用中可以通過設(shè)置規(guī)避區(qū)域（敵方打擊區(qū)域、敵方可探測(cè)區(qū)域或山谷狹窄區(qū)域等）來得到不同的航線規(guī)劃，指揮員可以選擇符合作戰(zhàn)要求的航線。由于本文算法具有效率較高的優(yōu)勢(shì)，所以可以根據(jù)戰(zhàn)時(shí)突發(fā)情況實(shí)時(shí)規(guī)劃航線來及時(shí)更新當(dāng)下更符合要求的航線。另外，本文給出的是一條航線，在實(shí)際應(yīng)用中如果將該航線周圍一定范圍的可通過的柵格塊也納入其中，從而形成一個(gè)通路區(qū)域，效果會(huì)更加理想，有助于判斷該航線是否符合作戰(zhàn)要求。

[1]胡鵬，黃杏元，華一新.地理信息系統(tǒng)教程[M].武漢：武漢大學(xué)出版社，2002.

[2]張宏，溫永寧，劉愛利，等.地理信息系統(tǒng)算法基礎(chǔ)[M].北京:科學(xué)出版社，2006.

[3]馬少平，朱小燕.人工智能[M].北京:清華大學(xué)出版社，2004.

[4]張永亮，朱美正，李欣.模擬退火粒子群算法在矢量數(shù)據(jù)壓縮中的應(yīng)用[J].計(jì)算機(jī)工程與軟件，2005，37（9）:1303-1306.

[5]張永亮，朱美正，李欣，等.基于稠密與稀疏高程點(diǎn)的Dem插值[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（1）:167-174.

[6]史娟.基于地形分析的路徑搜索算法研究[D].武漢：華中科技大學(xué)，2005.

[7]武百超，吳捷，崔繼憲.一種三角網(wǎng)的快速生成算法[J].礦山測(cè)量，2010（1）：41-43.

[8]顧春雷，楊漾，朱志春.幾種建立DEM模型插值方法精度的交叉驗(yàn)證[J].測(cè)繪與空間地理信息，2011（5）：99-102.

[9]應(yīng)申，李霖，王明常，等.計(jì)算幾何在地圖綜合中的應(yīng)用[J].測(cè)繪科學(xué)，2005（3）:64-66.

[10]Cormen T H，Leiserson C E，Ronald L，等.算法導(dǎo)論[M].潘金貴，顧鐵成，李成法，等譯.2版.北京：機(jī)械工業(yè)出版社，2011.

[11]齊英劍，池娟，張彬.基于Zernike矩亞像素邊緣檢測(cè)的改進(jìn)算法[J].西安郵電學(xué)院學(xué)報(bào)，2010，15（5）：75-78.

[12]陳榮華，韓旭里，吳宗敏.某型擬插值的多項(xiàng)式再生性[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（1）：1-3.

[13]宋俊輝，馮巖.負(fù)載均衡的分布式系統(tǒng)任務(wù)調(diào)度優(yōu)化算法[J].吉林大學(xué)學(xué)報(bào)（理學(xué)版），2017（2）:383-387.

[14]丁西明，段漢根，范益政.四叉樹分解的圖像插值[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（20）：191-193.

[15]馬力，王大翊，汪永生.基于SOA的Web服務(wù)應(yīng)用構(gòu)建關(guān)鍵技術(shù)研究[J].物聯(lián)網(wǎng)技術(shù)，2014（8）:76-79.

[16]鮑蕊娜，李向新，麻明，等.基于凸殼技術(shù)的Delaunay三角網(wǎng)生成算法研究[J].科學(xué)技術(shù)與工程，2011（4）:764-767.