孫 騫，許 睿，萬 航

（1.桂林市環(huán)境監(jiān)測中心站, 廣西 桂林 541002；2.桂林電子科技大學(xué), 廣西 桂林 541004）

路徑通達(dá)性預(yù)測方法是人工智能領(lǐng)域中的一個研究熱點問題，并且已經(jīng)在交通旅游、城市規(guī)劃、電子導(dǎo)航等領(lǐng)域得到了廣泛的應(yīng)用。求解路徑可達(dá)性的預(yù)測算法很多，如Floyd算法、Dijkstra算法等[1]。這些算法在進(jìn)行最佳路徑的規(guī)劃時，往往依賴于現(xiàn)存的交通路網(wǎng)，大多依賴于固定的路網(wǎng)節(jié)點，以路網(wǎng)固定節(jié)點間的路徑距離為因素建立權(quán)矩陣，然后通過分析計算，求解路網(wǎng)中任意兩點的最佳路徑；而對于沒有固定路網(wǎng)、地質(zhì)起伏、障礙繁多的野外復(fù)雜空間環(huán)境，整個空間區(qū)域節(jié)點數(shù)目不確定，通達(dá)性計算方法復(fù)雜、工作量大，傳統(tǒng)的導(dǎo)航尋路方法已經(jīng)很難滿足復(fù)雜空間環(huán)境中目的點最佳路徑的規(guī)劃要求，這就需要對現(xiàn)有的尋路方法進(jìn)行改進(jìn)研究，以滿足無路網(wǎng)空間環(huán)境中最佳路徑的選取和規(guī)劃。

A*算法是一種啟發(fā)式算法，它能夠在有限步內(nèi)終止，并找到最優(yōu)解，通過改進(jìn)A*算法能夠?qū)崿F(xiàn)野外復(fù)雜環(huán)境中目的點最佳路徑的搜索[2-4]。

1 野外復(fù)雜環(huán)境空間數(shù)據(jù)的處理

1.1 研究方法

根據(jù)通達(dá)性預(yù)測方法，選取特定地形影響因子數(shù)據(jù)，通過對各影響因子權(quán)重關(guān)系的分析，確定算法的估價函數(shù)。最終，結(jié)合高精DEM數(shù)據(jù)、NDVI植被數(shù)據(jù)以及Landsat影像數(shù)據(jù)，實現(xiàn)對野外復(fù)雜環(huán)境空間通達(dá)性的預(yù)測分析，為以后的路徑選取工作提供決策支持。具體研究步驟如圖1所示。

1.2 影響因子分析

通過DEM數(shù)據(jù)，預(yù)測空間的通達(dá)性狀況，實際上就是通過DEM高程數(shù)據(jù)，結(jié)合路徑搜索算法，實現(xiàn)空間起點和目的點最佳路徑的搜索。在對起點和目的點最佳路徑的分析計算之前，必須對影響路徑搜索的數(shù)值因子進(jìn)行分析計算，它們包括：數(shù)字高程值Dk，用來描述當(dāng)前點位置的數(shù)字高程信息；格網(wǎng)相鄰個數(shù)N，描述格網(wǎng)間的空間距離；坡度值P，描述空間點位置地形的起伏狀況；坡度容忍度T，坡度值在（-T，T）里格網(wǎng)才可達(dá)；格網(wǎng)地貌值GE（k），用來表示不同的地貌狀況，如山地、平原、河流等[5]； NDVI植被指數(shù)Z，用于檢測空間點位置植被覆蓋情況，取值在[-1,1]之間，負(fù)值表示地面覆蓋為冰、雨、雪等，對可見光反射，0表示地面為裸土巖石，數(shù)值越大，表示地面植被覆蓋度越高，通達(dá)性越差。

1.3 區(qū)域可達(dá)模型建立

利用GIS技術(shù)結(jié)合高精度DEM，通過分析和計算，確定區(qū)域鄰接格網(wǎng)的穿行代價。最終，根據(jù)空間穿行代價函數(shù)，建立野外復(fù)雜環(huán)境區(qū)域可達(dá)模型。

圖1 研究步驟

首先，結(jié)合DEM，通過移動窗口數(shù)據(jù)優(yōu)化方法，判別點位置8方向DEM網(wǎng)格的可達(dá)性，確定區(qū)域可達(dá)網(wǎng)格集，實現(xiàn)DEM高程數(shù)據(jù)的優(yōu)化[6-8]。然后，結(jié)合GIS的空間分析和圖像渲染技術(shù)，根據(jù)DEM高程圖和NDVI植被覆蓋圖，提取區(qū)域內(nèi)空間環(huán)境的坡度和植被覆蓋情況。最終，通過改進(jìn)A*算法，實現(xiàn)起始點和目的點最佳路徑的搜索。

坡度分析實現(xiàn)步驟：

1）加載DEM數(shù)字?jǐn)?shù)據(jù)。

2）利用空間分析工具，實現(xiàn)對研究區(qū)DEM高程圖的裁剪。

3）根據(jù)DEM數(shù)字高程圖，計算區(qū)域坡度信息，選擇坡度表示方法，生成區(qū)域坡度渲染圖，如圖2所示。

圖2 坡度變化圖

NDVI植被指數(shù)分析步驟：

1）加載ENVI植被數(shù)據(jù)。

2）實現(xiàn)研究區(qū)NDVI植被圖的裁剪獲取。

3）通過計算，分析區(qū)域植被覆蓋情況，計算公式如下：

式中，NIR為近紅外波段；R為紅光波段。

4）進(jìn)行輻射定標(biāo)與大氣校正。

5）輸出NDVI植被覆蓋圖，植被覆蓋情況如圖3所示。

2 算法分析

2.1 A*算法估價函數(shù)選取

A*算法像Dijkstra算法一樣，能夠?qū)崿F(xiàn)起始點到目的點最佳路徑的搜索[9-11]。區(qū)別在于A*算法具有啟發(fā)性，它能夠在啟發(fā)函數(shù)的引導(dǎo)下進(jìn)行有目的的路徑搜索。A*算法的核心是估價函數(shù)f（n），算法如下：

圖3 植被覆蓋圖

式中，g（n）為出發(fā)網(wǎng)格到第n個網(wǎng)格的實際代價，因為DEM格網(wǎng)是規(guī)則等分網(wǎng)格，所以相鄰距離都是一定的。同時根據(jù)野外地形的實際情況，結(jié)合實地區(qū)域的距離、植被、坡度和地貌信息，定義A*的實際估價函數(shù)：

h（n）體現(xiàn)了算法的啟發(fā)性，它能夠估算當(dāng)前節(jié)點到目標(biāo)節(jié)點的代價值，引導(dǎo)算法快速、高效地獲取到達(dá)目的點的最短路徑。地理信息系統(tǒng)中的最短路徑搜索問題，大多數(shù)都是給定起始點，經(jīng)過一定的中間節(jié)點，搜索最佳路徑。對于啟發(fā)式搜索方法來說，如果中間節(jié)點到目的點的方向與起始點到目的點的方向一致，那么最短路徑經(jīng)過這個點的可能性就更大[12]。在用二維數(shù)組表示的DEM網(wǎng)格中，與起始點到目的點方向一致的中間節(jié)點往往就是中間點到目的點距離最短的點，所以定義啟發(fā)函數(shù)為：

式中，X（n）、Y（n）分別為節(jié)點在二維數(shù)組中的x，y下標(biāo)。

2.2 算法優(yōu)化

采用上述方法已經(jīng)能夠?qū)崿F(xiàn)野外環(huán)境空間通達(dá)性的預(yù)測，但算法的實現(xiàn)效率和準(zhǔn)確度仍不是很高，需要對算法進(jìn)一步優(yōu)化。

A*算法的優(yōu)化主要分為2個方面：①對Open表的優(yōu)化，加快Open表的存儲訪問速度；②對估價函數(shù)f（n）的優(yōu)化，改變估價函數(shù)的權(quán)值，實現(xiàn)搜索速度和準(zhǔn)確率的提高。

從A*搜索原理來看，隨著搜索范圍的擴大，Open表中的節(jié)點數(shù)量會呈幾何倍數(shù)增長。對于越來越多的節(jié)點數(shù)量，算法根據(jù)啟發(fā)性原理，往往希望向最有可能達(dá)到目的點的方向進(jìn)行搜索，這就需要在Open表中取出具有最小估價總值的節(jié)點。因此，有必要對Open表中的節(jié)點進(jìn)行估價值計算，并按照估價值大小進(jìn)行遞增排序，這樣每次進(jìn)行算法運算時，只需取出第一個節(jié)點即可，可以降低算法的時間復(fù)雜度，提高路徑搜索的效率[13]。

對于估價函數(shù)，g（n）是源點到節(jié)點n的路徑代價，而啟發(fā)函數(shù)h（n）是節(jié)點n到目的點最短路徑的估價值，它決定了算法的搜索效率。理論上h（n）不能大于當(dāng)前節(jié)點n到目的點的實際最短距離，最理想的情況是啟發(fā)函數(shù)的估計值與實際值相等，但在實際應(yīng)用中估計值的大小只能盡可能地接近實際值。同時為保證算法的完備性和高效性，需要引入加權(quán)模型來平衡估價函數(shù)中各影響因子的權(quán)重。本文針對高精度DEM數(shù)據(jù)，引入加權(quán)因子，定義如下：

隨著n的增大，減小k2的取值，使啟發(fā)函數(shù)的值接近實際值，以此提高搜索的精度和效率。

2.3 實現(xiàn)步驟

根據(jù)分析結(jié)果，確定算法流程（圖4）：

1）DEM格網(wǎng)的初始化。

2）創(chuàng)建Open表，加載源點信息。

3）判斷Open表是否為空，若為空則尋路失敗。

圖4 算法流程

4）取出Open表中估價值最小的節(jié)點V，并放入Close表中。

5）如果節(jié)點V為終點，則尋路成功，轉(zhuǎn)向7）。

6）如果V不是終點，則對相鄰的8個方向節(jié)點進(jìn)行判斷：①如果節(jié)點在Close表中，則返回6）繼續(xù)；②如果該節(jié)點不在Open表中，則將節(jié)點添加到Open表中，計算估價值，并按照大小順序進(jìn)行遞增排序；③如果節(jié)點在Open表中，則計算節(jié)點的估價值，并與舊值進(jìn)行比較，選擇較小值，更新Open表；④如果8個方向檢查完畢，則轉(zhuǎn)向3），否則，轉(zhuǎn)向6）。

7）輸出路徑。

3 實驗結(jié)果與驗證

根據(jù)實驗需求，選取比例尺為1∶10 000，格網(wǎng)間距為5 m的高分辨率DEM數(shù)字高程圖，結(jié)合算法，在圖層范圍內(nèi)任意選取2點作為算法的起始點和目的點，通過仿真，建立空間通達(dá)性預(yù)測模型，實現(xiàn)源點和目的點最佳路徑的規(guī)劃。路徑輸出渲染結(jié)果如圖5所示。

圖5 路徑輸出圖

根據(jù)數(shù)值高程圖，選取左上角A點作為方法的起點，B點作為方法的目的點。結(jié)合改進(jìn)A*算法，方法能夠根據(jù)DEM和NDVI數(shù)據(jù)信息，實現(xiàn)空間最短路徑的準(zhǔn)確、快速搜索。路徑表現(xiàn)為一條細(xì)長曲折的運動軌跡線。實驗結(jié)果表明，野外環(huán)境中建立空間可達(dá)性模型，能夠在野外行軍、森林救火、雪崩救援、抗洪救災(zāi)等方面得到應(yīng)用。

4 結(jié) 語

構(gòu)建了一種基于GIS的野外復(fù)雜環(huán)境空間通達(dá)性預(yù)測方法。通過改進(jìn)A*算法，該方法能夠?qū)崿F(xiàn)野外環(huán)境中最佳路徑的搜索，可在野外無拓?fù)涞缆返牡匦苇h(huán)境中得以應(yīng)用，具有一定的合理性和實用性。但在現(xiàn)實應(yīng)用中，模型仍存在著一些不足之處，主要包括DEM格網(wǎng)的采集精度、Landsat影像數(shù)據(jù)和NDVI植被覆蓋數(shù)據(jù)的分辨率、NDVI大氣影響校正指數(shù)、坡度提取的準(zhǔn)確度等，這都需要進(jìn)一步研究和探討。目前，本系統(tǒng)僅能對單一精度的遙感影像數(shù)據(jù)進(jìn)行最佳路徑的規(guī)劃分析，而對不同精度、不同需求的影像數(shù)據(jù)的分析計算，系統(tǒng)仍需優(yōu)化完善。后續(xù)可采用分層和并行計算的思想來完善系統(tǒng)，提高方法的運行速度與計算效率。

[1]Felner A, Stern R, Ben-Yair A, et al.PHA*:Finding the Shortest Path with A* in an Unknown PhysicaL Environment[J].Journal of Artif icial Intelligence Research, 2004(21): 631-670

[2]張和平, 張前哨.A*算法在游戲地圖尋徑中的應(yīng)用與實現(xiàn)[J].計算機應(yīng)用與軟件, 2005 (12): 198-200

[3]劉浩.A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J].計算機仿真, 2008, 25(4): 253-257

[4]Goldberg A, Kaplan H, Werneck R.Reach for A*: Efficient Point–to-Point Shortest Path Algorithms[C].Philadelphia,United States: Workshop on Algorithm Engineering and Experiments, Miami Society for Industrial and Applied Mathematics Publications, 2006

[5]胡偉, 盧小平, 盧遙, 等.基于移動窗口法的DEM數(shù)據(jù)優(yōu)化方法研究[J].測繪通報, 2011(5): 45-47

[6]原江波, 母攀良, 史樂,等.大場景中虛擬車輛自動尋路的高效算法[J].計算機工程與設(shè)計, 2008, 29(10): 2 622-2 625

[7]陳易, 王晶.帶通行限制的加權(quán)A*算法及其數(shù)據(jù)庫實現(xiàn)[J].北京化工大學(xué)學(xué)報, 2009, 36(5): 107-111

[8]李建元, 師軍, 曹菡, 等.一種分層尋路算法中的域值放棄策略[J].計算機應(yīng)用, 2007, 27(2): 473-478

[9]于曉艷, 馬勁松, 劉艷, 等.城市通達(dá)性面狀分布模型研究[J].水電能源科學(xué), 2010, 28(6): 56-58

[10]林篤斌, 李欣.基于DEM格網(wǎng)的改進(jìn)型A*路徑搜索算法[J].計算機工程與設(shè)計, 2011, 32(10): 3 414-3 418

[11]劉學(xué)軍, 卞璐, 盧華興.顧及DEM誤差自相關(guān)的坡度計算模型精度分析[J].測繪學(xué)報, 2008, 37(2): 200-206

[12]曹強, 張明智, 李志強, 等.CTI中車輛實時最佳路徑搜索算法設(shè)計與實現(xiàn)[J].系統(tǒng)仿真學(xué)報, 2009, 21(21):6 777-6 780

[13]嚴(yán)寒冰, 劉迎春.基于GIS的城市道路網(wǎng)最短路徑算法探討[J].計算機學(xué)報, 2000, 23(2): 210-215