基于變分辨率柵格模型的啟發式有向搜索最優路徑算法

華劍鋒，張 豐，杜震洪＊，劉仁義，李榮亞（1．浙江大學浙江省資源與環境信息系統重點實驗室，浙江杭州310028；2．浙江大學地理信息科學研究所，浙江杭州310027）

?

基于變分辨率柵格模型的啟發式有向搜索最優路徑算法

華劍鋒1，2，張 豐1，2，杜震洪1，2＊，劉仁義1，2，李榮亞1，2
（1．浙江大學浙江省資源與環境信息系統重點實驗室，浙江杭州310028；2．浙江大學地理信息科學研究所，浙江杭州310027）

摘 要：針對連續空間中無法直接采用圖論方法進行路徑分析的問題，提出了基于四叉樹思想構建的變分辨柵格模型．該模型不僅兼顧了地形表達精度與數據冗余度，而且避免了地物“邊緣效應”的影響．在該模型基礎上，設計了一種啟發式有向搜索算法，該算法在搜索節點時，首先對相鄰節點進行方向性選擇，減少搜索空間，提高了算法的效率．實驗結果表明，提出的模型及算法不僅能夠求得連續空間中的最優路徑，而且具有較高的計算效率．

關 鍵 詞：最優路徑；連續空間；變分辨率；柵格模型；有向搜索方法

0 引 言

路徑分析一直是各個學科研究的熱點，也是GIS網絡分析的基本問題，其核心是對最優路徑的求解．由于GIS矢量數據表達的是一種離散空間，存在預定的節點及軌跡，因此可以很方便地將其抽象為具有節點和連線的網絡，繼而將問題轉換為在圖論意義下利用最短路徑算法求解最優路徑的問題．然而，GIS柵格數據表達的是一種連續空間，不存在預定的節點和軌跡，因而用于求解矢量數據最優路徑的策略和算法并不適用于柵格數據．實際中也往往遇到此類問題，例如航空線路規劃、輸電線路選址、道路工程設計、森林火災蔓延等．目前為止，國內外專家學者對基于矢量數據求解最優路徑的研究較多，但對柵格數據求解最優路徑策略和算法的相關研究較少，且多見于人工智能領域對移動機器人行走路徑的求解［1－4］，而在GIS領域鮮有文獻報道．基于GIS柵格數據求解最優路徑的關鍵在于柵格數據模型的構建策略，以及最優路徑算法的設計與優化．

在柵格數據模型構建方面，文獻［5］引入地表障礙距離構建了網格模型，該模型綜合考慮地理空間高程、坡度、障礙物等因素的影響，易于實現路徑的尋優計算．文獻［6］利用網格劃分柵格數據，結合點、邊、屬性等約束條件，以圖或網絡的方式描述柵格數據，最后在網絡模型中求解最優路徑．文獻［7］將離散的矢量網絡作為輔助，在連續的柵格表面描述道路網絡，以此來求解柵格表面考慮地形要素的最優車輛出行線路．這些文獻都對柵格數據進行了模型構建，也考慮了障礙物等因素的影響，但所構建的柵格模型均屬于單分辨率模型，這種模型在解決實際問題時存在2個問題：（1）不能兼顧地形表達精度與數據冗余度．當分辨率過低時，不能精確表達地形復雜度，從而影響路徑尋優計算的準確性；當分辨率過高時，雖能精確表達地形復雜度，但會造成數據的大量冗余，增加路徑尋優的計算成本．（2）在路徑規劃時往往會遇到如圖1所示的問題，圖1中，PS為起點，PE為終點，A、B為路徑規劃區域內的面狀地物（如居民區、自然保護區等），理想的路徑應該為L1，但計算機在自動選線時往往會繞道而行選擇類似L2的路徑，這是由于地物雖然只覆蓋了單元格的一部分，但單元格因為擁有了地物信息，導致計算機選線時繞道而行，這種現象稱為地物的“邊緣效應”．

圖1　地物“邊緣效應”Fig．1 Edge effect

在柵格數據最優路徑算法方面，文獻［8］在柵格數據環境下，采用Dijkstra算法，通過維護OPEN 和CLOSED表來進行節點的搜索，并構建了索引數組來判斷待搜索的節點是在OPEN表還是在CLOSED表中，由此提高了算法的效率．但Dijkstra算法的優點在于能夠計算起始節點到其他所有節點的最優路徑，是一種發散式的搜索，并不適合給定起點和終點的最優路徑問題．文獻［9］采用A＊算法計算最優的步行路徑．A＊算法是一種關注起點到終點的最優路徑算法，同時也是一種人工智能算法，更適合在柵格數據中進行求解，但文獻［9］并未對A＊算法做任何改進，使得算法的效率較低．

為了解決上述模型和算法上的問題，本文提出變分辨率柵格數據模型，采用四叉樹的思想將地形復雜區域或地物邊緣進行不斷細分，直至細分后的單元格具有唯一性質，而對地形平坦區域則保留初始的分辨率，從而，在兼顧地形表達的精度與數據冗余度的同時避免了地物“邊緣效應”的影響．進而，在模型的基礎上，設計啟發式有向搜索算法，通過引入有向搜索方法，建立適當的篩選條件，避免對不必要節點的搜索，在節點搜索過程中進行方向性選擇，縮小搜索范圍，提高算法效率．

1 變分辨柵格數據模型

變分辨率柵格數據模型不同于單分辨率柵格數據模型，由相互鄰接、分辨率不同的單元格構成，因而其實現原理、單元格的領域模式、單元格通行代價的計算方式也有所不同．

1．1 實現原理

變分辨率柵格數據模型基于四叉樹的思想構建，它不斷地將具有多重性質的單元格四分為大小相同的子單元格，直到所有的單元格都具有唯一的性質，從而使具有多重性質的單元格得到精細表達．而單一性質的單元格由于無須細分減少了數據存儲量．圖2是一個二值8＊8的柵格模型及其對應的四叉樹結構，首先將其細分為4個子域（NW、NE、SE、SW），然后繼續細分子域直到每個子域都具有唯一值．

圖2　柵格數據的四叉樹結構Fig．2 The quad tree structure of raster data

在連續空間中進行最優路徑分析需要考慮多種影響因素（如居民區、自然保護區、名勝古跡等），這些影響因素在最優路徑分析中被作為障礙物．將連續空間以規則鑲嵌的方式柵格化后，某些影響因素不會完全覆蓋某些單元格，這種情況多發生于地形復雜的區域或地物的邊緣，此時，就采用四叉樹的方式對其進行細分，地形復雜區域或地物邊緣由于被劃分得更為細致，從而得到精細化的表達，同時也避免了地物的“邊緣效應”．而對于地形平坦的區域或障礙物較少的區域，則不進行細分，這樣的好處是減少了數據的存儲總量，使得數據整體的冗余度較低．

1．2 單元格的領域模式

如同圖3搜索中需要給定圖的節點和連線，變分辨率柵格數據模型也需要指定單元格的領域模式．單分辨率柵格數據模型的領域模式通常有4，8，16，32等，而變分辨率柵格數據模型的領域模式則更為復雜，這是因為其指定單元格的相鄰單元格個數是不確定的．本文采用判斷單元格是否相鄰的方法來確定指定單元格的領域模式，具體方法為將指定單元格的中心作為節點，搜索與它相鄰的所有單元格，并將這些單元格作為指定單元格的領域模式，相鄰單元格的節點稱為相鄰節點，指定節點與相鄰節點之間的連線稱為通行路徑．

1．3 單元格的通行代價計算

在進行實際最優路徑分析時，受地形地貌或者居民區、自然保護區等因素的影響，通過每一個單元格的代價都是不同的，因此，需對單元格的通行代價進行具體計算．本文依據單元格是否覆蓋障礙物將其劃分為障礙物單元格和可通行單元格，障礙物單元格不允許線路通過，而可通行單元格計算通行的代價通常考慮地形、坡度、距離等因素，各個因素的影響權值可以不同，單元格通行代價值Cost由式（1）計算得到．

式中，i為影響因素編號，fi為編號為i的影響因素，wi為該影響因素的權值．

2 啟發式有向搜索算法及分析

變分辨率柵格數據模型是最優路徑分析的基礎，它為最優路徑分析提供了數據模型支持．同時，最優路徑分析也離不開算法的支持．本文對A＊算法進行改進，設計了啟發式有向搜索算法．

2．1 啟發函數的建立

A＊算法在搜索過程中使用啟發函數，對搜索的每一個節點進行代價評估，優先選擇代價最小的節點，再從這個節點繼續搜索，直到搜索到目標，從而省略了大量無謂的搜索路徑，增強了搜索的目標性，提升了效率．其核心算法函數為f（x）＝g（x）＋h（x），其中g（x）為起點到該節點的實際最小代價，h（x）為該節點到終點的估算代價，f（x）即為從起點到終點并經過了該節點的最小代價．

2．2 有向搜索方法對A＊算法的優化

為了進一步提高A＊算法的搜索效率，本算法在搜索節點時，首先計算2個夾角值θ1和θ2，以判斷待搜索的節點是否在當前節點和終點內．如圖3所示，建立以當前節點為原點0，以原點0到終點1的連線方向為x軸的直角坐標系．θ1為待搜索節點2、原點0和終點1構成的夾角，θ2為待搜索節點2、終點1和原點0構成的夾角．當θ1、θ2同時滿足小于等于90°時，才將其納入當前節點的可擴展節點集．此項工作相當于對變分辨率柵格數據模型中各個節點的相鄰節點進行數據預處理．

計算公式如下：

其中，（X1，Y1）和（X2，Y2）分別為同一直角坐標系中2個點的坐標，θ為兩點與坐標原點間連線的夾角．

圖3　有向搜索方法Fig．3 The method of directional algorithm

2．3 實現過程

設置節點的狀態為｛j，isObstacle，Cost，g（j），h（j），f（j），preNode｝，其中，j為當前節點標識；preNode為j的父節點，i為preNode的父節點標識；isObstacle為節點所在單元格的障礙標識，其取值為true或false，true值表示該單元格為障礙物單元格，false值表示該單元格為可通行狀態；Cost為該單元格的通行代價；g（j）為從起點沿著產生的路徑，移動到當前節點的實際代價，g（j）＝preNode．g（j）＋Cost；h（j）為當前節點移動到終點的估算代價，該值可以是曼哈頓距離、歐氏距離、切比雪夫距離，算法采用曼哈頓距離，即首先計算從當前節點移動到終點水平和垂直方向的各個分辨率的單元格的數量之和，再乘上單元格所代表的實際距離；f（j）＝g（j）＋h（j）．

建立3個鏈表ORIGINAL、OPEN和CLOSED，ORIGINAL為“初始列表”，存放了所有單元格節點；OPEN為“開啟列表”，用來存放所有待檢查的節點；CLOSED為“關閉列表”，用來存放所有已訪問過的節點，這些節點在后續的搜索中無須再次被檢查．OPEN和CLOSED表的初始狀態置為空．算法的具體步驟如下：

1）將所有節點的狀態設置為｛j，isObstacle，Cost，∞，h（j），∞，null｝放入到ORIGINAL表中，將初始節點（即起點PS）的狀態設置為｛j，false，0，0，0，0，null｝，放入到OPEN表中．

2）在ORIGINAL表中搜索所有與起點PS相鄰的節點，排除具有以下特征的節點：（1）θ1、θ2不滿足條件；（2）isObstacle狀態為true，這些節點無法通行；（3）CLOSED表中的節點，這些節點已被訪問．將排除后的所有節點放入OPEN表，計算它們的g（j）值和f（j）值，并設置它們的父節點為起點PS．

3）從OPEN表中刪除起點PS，并將其添加到CLOSED表．

4）從OPEN表中找出f（j）值最小的節點，將其從OPEN表中移出，并添加到CLOSED表，同時將該節點設置為當前節點S．

5）在ORIGINAL表中搜索所有與當前節點S相鄰的節點，排除具有以下特征的節點：（1）θ1、θ2不滿足條件；（2）isObstacle狀態為true；（3）CLOSED表中的節點．將排除后的所有節點放入OPEN表，計算它們的g（j）和f（j）值：并設置它們的父節點為S．

6）遍歷步驟5）中搜索到并符合條件的節點，若節點不在OPEN表中，則將它添加進OPEN表，計算它的g（j）和f（j），并設置它的父節點為S，若節點已經在OPEN表中，計算新的路徑（即經過S到達該點的路徑）的g（j）值：若g（j）值高于原值，說明這不是一個明智的選擇，因為其耗費更高；若g（j）值低于原值，意味新的路徑是更好的選擇，首先將該節點的父節點更新為當前節點S，然后重新計算它的g（j）和f（j）值．在所有產生新路徑的節點中，選擇f（j）值最小的作為路徑的節點，將其父節點S從OPEN表移至CLOSED表，并更新該節點為當前節點S．轉到步驟5），直至OPEN表中出現終點PE，退出循環．

7）最后，從終點PE開始，沿每一節點的父節點回到起點PS，連接而成的路徑就是所要求解的最優路徑．

算法的代碼及實現步驟如下：

public class BestPath｛

oriList／／初始列表

openList／／開啟列表

closedList／／關閉列表

startNode／／起始節點

endNode／／目標節點

currentNode／／當前節點

public BestPath（）｛

openList．Add（startNode）／／將起始節點添加到開啟列表

currentNode＝startNode；

do｛

currentNode＝searchFminNode（currentNode）／／尋找開啟列表中F值最低的節點，并將其置為當前節點

closedNode．Add（currentNode） ／／將當前節點切換到關閉列表

currentNode＝searchNode（currentNode）／／搜索當前節點的相鄰節點

｝while（endNode∈openList）／／直到目標節點出現在開啟列表中，這時路徑被找到

｝

private Node search FminNode（Node goalNode）｛

for each node／／遍歷所有相鄰的節點

if（node－＞｛θ1＆θ2｝＆＆node．isObstacle＝＝false＆＆node?closedList）／／如果節點滿足條件

｛

openList．Add（node）／／將節點添加到開啟列表

calc F（node）／／計算節點的F值

node．preNode＝goalNode／／設置節點的父節點為goalNode

｝

return FminNode／／返回至F值最小的節點

｝

private Node searchNodes（Node goalNode）｛

for each node／／遍歷所有相鄰的節點

if（node！－＞｛θ1＆θ2｝＆＆node．isObstacle＝＝true＆＆node∈closedList） ／／如果節點不滿足夾角條件或不可通過或已經在關閉列表中

｛

／／什么也不做

｝

｛

openList．Add（node）／／將節點添加到開啟列表

node．preNode＝goalNode／／設置節點的父節點為當前節點

calc GF（）／／計算該節點的G值和F值 ｝

if（node∈openList）／／節點已經在開啟列表中

｛

node．NewG＝calcNewG（）／／計算經過goalNode到該節點的新路徑的G值

if（node．NewG＜node．G）／／若新值低于原值，因為新的路徑是更好的選擇

｛

node．preNode＝goalNode／／設置節點的父節點為當前節點

closedNode．Add（goalNode）／／將當前節點切換到關閉列表

reCalc GF（）／／重新計算該節點的G值和F值

｝

｝

return FminNode／／返回F值最小的節點

｝

｝

3 實例與效率分析

為驗證模型和算法的有效性，采用江蘇省某地區220kV輸電線路規劃對模型和算法進行實例驗證．在輸電線路規劃中，影響線路設計的主要因素有居民區、自然保護區、水源保護區、森林公園、風景名勝區等環境敏感區，以及空間距離、高程、坡度等地形影響因素［10］．環境敏感區是禁止通行的區域，因此將其作為障礙因素，地形影響因素需計算其通行代價．根據已有柵格數據的分辨率以及線路規劃精度要求，構建多分辨率柵格數據模型，模型中的空間距離、高程、坡度的影響權重分別設定為0．7，0．2，0．1．圖4為構建的規劃區域的變分辨率柵格數據模型．

圖4　規劃區域的變分辨率柵格數據模型Fig．4 Variable resolution raster data model of planning area

首先對模型的有效性進行驗證．實驗結果如圖5所示，圖5（a）、（b）為單分辨率柵格數據模型，其中（a）的分辨率較低，（b）的分辨率較高，（c）為本文提出的變分辨率柵格數據模型．圖5（a）中的路徑受到地物“邊緣效應”的影響，為避開障礙物需繞道而行，（b）和（c）都成功避開了障礙物，并且得到了比（a）更短的最優路徑，但（b）中單元格的數量遠遠大于（c），造成數據冗余度較高，同時也增加了路徑尋優的計算成本，而（c）不僅正確地尋找最優路徑，而且極大地降低了數據冗余度及計算成本．

圖5　3種模型的線路規劃結果Fig．5 Route planning results of three kinds of models

然后對算法的有效性進行驗證．在變分辨率柵格數據模型中選取Dijkstra、A＊和本文提出的啟發式有向搜索算法求解最優路徑（見圖5（c）），結果如表1所示．從表1的實驗結果可知，Dijkstra算法由于在搜索節點時的盲目性，需要搜索的空間龐大，找到最優路徑的時間較長，而A＊算法由于增加了啟發式信息，大大減少了搜索節點數，找到最優路徑所需的時間遠短于Dijkstra算法．而本文提出的啟發式有向搜索算法對A＊算法做了改進，引入了有向搜索方法，使得搜索的節點數減少了近一半，從而提高了尋找最優路徑的時間效率．

表1　3種算法比較Table 1 Comparison of three algorithms

4 結 語

提出了變分辨率柵格數據模型，該模型克服了傳統單分辨率柵格數據模型在進行最優路徑分析時無法兼顧地形表達精度和數據冗余度的弊端，避免了地物“邊緣效應”的影響．同時，在模型的基礎上，對A＊算法進行了改進，通過引入啟發式有向搜索方法，減少了搜索空間，提高了算法的計算效率．本文雖然考慮了坡度等地形因素，但最后得到的最優路徑的空間距離為水平距離，如何計算實際距離有待進一步研究．總之，該方法能有效解決連續空間中最優路徑的求解問題，可應用于道路工程設計、輸電線路選址等領域．

參考文獻（References）：

［1］ 張萬緒，張向蘭，李瑩．基于改進粒子群算法的智能機器人路徑規劃［J］．計算機應用，2014（2）：510－513．ZHANG Wanxu，ZHANG Xianglan，LI Ying．Path planning for intelligent robots based on improved particle swarm optimization algorithm［J］．Journal of Computer Applications，2014（2）：510－513．

［2］ 趙開新，魏勇，王東署．改進蟻群算法在移動機器人路徑規劃中的研究［J］．計算機測量與控制，2014（11）：3725－3727．ZHAO Kaixin，WEI Yong，WANG Dongshu．Research of improved ant colony algorithm in mobile robot path planning［J］．Computer Measurement ＆Control，2014（11）：3725－3727．

［3］ 簡毅，張月．移動機器人全局覆蓋路徑規劃算法研究進展與展望［J］．計算機應用，2014（10）：2844－2849，2864．JIAN Yi，ZHANG Yue．Complete coverage path planning algorithm for mobile robot：Progress and prospect ［J］．Journal of Computer Applications，2014（10）：2844－2849，2864．

［4］ 康冰，王曦輝，劉富．基于改進蟻群算法的搜索機器人路徑規劃［J］．吉林大學學報：工學版，2014（4）：1062－1068．KANG Bing，WANG Xihui，LIU Fu．Path planning of searching robot based on improved ant colony algorithm［J］．Journal of Jilin University：Engineering and Technology Edition，2014（4）：1062－1068．

［5］ 孫永，劉靖旭，宋留勇．復雜地理環境下基于障礙距離的最短路徑尋優算法［J］．測繪科學，2014（2）：37－41，68．SUN Yong，LIU Jingxu，SONG Liuyong．Study of shortest paths optimization algorithm based on obstructed distance under complexity geographical environment［J］．Science of Surveying and Mapping，2014 （2）：37－41，68．

［6］ 厙向陽，史經儉，羅曉霞．柵格數據模型中附有條件的最短路徑算法［J］．計算機應用，2008（4）：856－859．SHE Xiangyang，SHI Jingjian，LUO Xiaoxia．Shortest path algorithm confined to conditions in grid data model［J］．Journal of Computer Applications，2008（4）：856－859．

［7］ CHOI Yosoon，UM Jeonggi，PARK Myongho．Finding least－cost paths across a continuous raster surface with discrete vector networks［J］．Cartography and Geographic Information Science，2014，41（1）：75－85．

［8］ 魯敏，張金芳．柵格地形的最優路徑分析［J］．武漢大學學報：信息科學版，2010（1）：59－63．LU Min，ZHANG Jinfang．Least－cost path analysis in raster terrains［J］．Geomatics and Information Science of Wuhan University，2010（1）：59－63．

［9］ 嚴瑞，龍毅，鄭玥，等．顧及地形起伏的步行最優路徑分析算法［J］．武漢大學學報：信息科學版，2012（5）：564－568，572．YAN Rui，LONG Yi，ZHENG Yue，et al．An optimal walking path algorithm considering terrain influence ［J］．Geomatics and Information Science of Wuhan University，2012（5）：564－568，572．

［10］ 舒雋，韓冰，陳學姣．計及線路路徑優化的空間電網規劃［J］．中國電機工程學報，2014（4）：570－577．SHU Jun，HAN Bing，CHEN Xuejiao．Spatial power network planning considering electric line route optimization［J］．Proceedings of the CSEE，2014（4）：570－577．

Heuristic directional search optimal path algorithm based on the variable raster model

HUA Jianfeng1，2，ZHANG Feng1，2，DU Zhenhong1，2，LIU Renyi1，2，LI Rongya1，2（1．Zhejiang Provincial Key Lab of GIS，Zhejiang University，Hangzhou310028，China；2．Department of Geographic Information Science，Zhejiang University，Hangzhou310027，China）

Journal of Zhejiang University（Science Edition），2016，43（1）：051－056

Abstract：For graph theory method cannot be directly used to approach the path analysis problems in continuous space，a variable resolution grid model based on quad－tree thought is figured out．This model not only takes into account the topographic expression accuracy and data redundancy，but also avoids the impact of the“edge effect”．On the basis of the model，a heuristic directional search algorithm is designed，in which a directional search method is introduced．The algorithm firstly selects nodes according to the direction when searching for adjacent node，thereby reducing the search space and improving the efficiency of the algorithm．Experimental results show that the model and the algorithm proposed can not only obtain the optimal path in continuous space，but also have high computational efficiency．

Key Words：optimal path；continuous space；variable resolution；raster model；directional search method

通信作者＊，E－mail：duzhenhong＠zju．edu．cn．

作者簡介：華劍鋒（1989－），男，碩士研究生，主要從事GIS開發及其在水利、公共衛生等領域的應用研究．

基金項目：國家自然科學基金資助項目（41471313，41101356）；浙江省科技攻關計劃項目（2013C33051）；國家海洋公益性行業科研專項經費資助項目（2015418003，201305012）；國家科技基礎性工作專項（2012FY112300）；中央高校基礎科研業務費專項（2013QNA3023）．

收稿日期：2015－05－05．

DOI：10．3785／j．issn．1008－9497．2016．01．009

中圖分類號：P208

文獻標志碼：A

文章編號：1008－9497（2016）01－051－06