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

?

基于變分辨率柵格模型的啟發(fā)式有向搜索最優(yōu)路徑算法

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

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

關(guān) 鍵 詞：最優(yōu)路徑；連續(xù)空間；變分辨率；柵格模型；有向搜索方法

0 引 言

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

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

圖1　地物“邊緣效應(yīng)”Fig．1 Edge effect

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

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

1 變分辨柵格數(shù)據(jù)模型

變分辨率柵格數(shù)據(jù)模型不同于單分辨率柵格數(shù)據(jù)模型，由相互鄰接、分辨率不同的單元格構(gòu)成，因而其實現(xiàn)原理、單元格的領(lǐng)域模式、單元格通行代價的計算方式也有所不同．

1．1 實現(xiàn)原理

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

圖2　柵格數(shù)據(jù)的四叉樹結(jié)構(gòu)Fig．2 The quad tree structure of raster data

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

1．2 單元格的領(lǐng)域模式

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

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

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

式中，i為影響因素編號，fi為編號為i的影響因素，wi為該影響因素的權(quán)值．

2 啟發(fā)式有向搜索算法及分析

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

2．1 啟發(fā)函數(shù)的建立

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

2．2 有向搜索方法對A＊算法的優(yōu)化

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

計算公式如下：

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

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

2．3 實現(xiàn)過程

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

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

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

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

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

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

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

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

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

算法的代碼及實現(xiàn)步驟如下：

public class BestPath｛

oriList／／初始列表

openList／／開啟列表

closedList／／關(guān)閉列表

startNode／／起始節(jié)點

endNode／／目標節(jié)點

currentNode／／當前節(jié)點

public BestPath（）｛

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

currentNode＝startNode；

do｛

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

closedNode．Add（currentNode） ／／將當前節(jié)點切換到關(guān)閉列表

currentNode＝searchNode（currentNode）／／搜索當前節(jié)點的相鄰節(jié)點

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

｝

private Node search FminNode（Node goalNode）｛

for each node／／遍歷所有相鄰的節(jié)點

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

｛

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

calc F（node）／／計算節(jié)點的F值

node．preNode＝goalNode／／設(shè)置節(jié)點的父節(jié)點為goalNode

｝

return FminNode／／返回至F值最小的節(jié)點

｝

private Node searchNodes（Node goalNode）｛

for each node／／遍歷所有相鄰的節(jié)點

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

｛

／／什么也不做

｝

｛

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

node．preNode＝goalNode／／設(shè)置節(jié)點的父節(jié)點為當前節(jié)點

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

if（node∈openList）／／節(jié)點已經(jīng)在開啟列表中

｛

node．NewG＝calcNewG（）／／計算經(jīng)過goalNode到該節(jié)點的新路徑的G值

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

｛

node．preNode＝goalNode／／設(shè)置節(jié)點的父節(jié)點為當前節(jié)點

closedNode．Add（goalNode）／／將當前節(jié)點切換到關(guān)閉列表

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

｝

｝

return FminNode／／返回F值最小的節(jié)點

｝

｝

3 實例與效率分析

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

圖4　規(guī)劃區(qū)域的變分辨率柵格數(shù)據(jù)模型Fig．4 Variable resolution raster data model of planning area

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

圖5　3種模型的線路規(guī)劃結(jié)果Fig．5 Route planning results of three kinds of models

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

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

4 結(jié) 語

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

參考文獻（References）：

［1］ 張萬緒，張向蘭，李瑩．基于改進粒子群算法的智能機器人路徑規(guī)劃［J］．計算機應(yīng)用，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］ 趙開新，魏勇，王東署．改進蟻群算法在移動機器人路徑規(guī)劃中的研究［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］ 簡毅，張月．移動機器人全局覆蓋路徑規(guī)劃算法研究進展與展望［J］．計算機應(yīng)用，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］ 康冰，王曦輝，劉富．基于改進蟻群算法的搜索機器人路徑規(guī)劃［J］．吉林大學(xué)學(xué)報：工學(xué)版，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］ 孫永，劉靖旭，宋留勇．復(fù)雜地理環(huán)境下基于障礙距離的最短路徑尋優(yōu)算法［J］．測繪科學(xué)，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īng)儉，羅曉霞．柵格數(shù)據(jù)模型中附有條件的最短路徑算法［J］．計算機應(yīng)用，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］ 魯敏，張金芳．柵格地形的最優(yōu)路徑分析［J］．武漢大學(xué)學(xué)報：信息科學(xué)版，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］ 嚴瑞，龍毅，鄭玥，等．顧及地形起伏的步行最優(yōu)路徑分析算法［J］．武漢大學(xué)學(xué)報：信息科學(xué)版，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］ 舒雋，韓冰，陳學(xué)姣．計及線路路徑優(yōu)化的空間電網(wǎng)規(guī)劃［J］．中國電機工程學(xué)報，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開發(fā)及其在水利、公共衛(wèi)生等領(lǐng)域的應(yīng)用研究．

基金項目：國家自然科學(xué)基金資助項目（41471313，41101356）；浙江省科技攻關(guān)計劃項目（2013C33051）；國家海洋公益性行業(yè)科研專項經(jīng)費資助項目（2015418003，201305012）；國家科技基礎(chǔ)性工作專項（2012FY112300）；中央高?；A(chǔ)科研業(yè)務(wù)費專項（2013QNA3023）．

收稿日期：2015－05－05．

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

中圖分類號：P208

文獻標志碼：A

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