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

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

?

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

1．3 單元格的通行代價(jià)計(jì)算

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

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

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

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

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

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

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

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

計(jì)算公式如下：

其中，（X1，Y1）和（X2，Y2）分別為同一直角坐標(biāo)系中2個(gè)點(diǎn)的坐標(biāo)，θ為兩點(diǎn)與坐標(biāo)原點(diǎn)間連線的夾角．

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

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

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

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

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

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

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

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

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

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

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

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

public class BestPath｛

oriList／／初始列表

openList／／開啟列表

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

startNode／／起始節(jié)點(diǎn)

endNode／／目標(biāo)節(jié)點(diǎn)

currentNode／／當(dāng)前節(jié)點(diǎn)

public BestPath（）｛

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

currentNode＝startNode；

do｛

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

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

currentNode＝searchNode（currentNode）／／搜索當(dāng)前節(jié)點(diǎn)的相鄰節(jié)點(diǎn)

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

｝

private Node search FminNode（Node goalNode）｛

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

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

｛

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

calc F（node）／／計(jì)算節(jié)點(diǎn)的F值

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

｝

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

｝

private Node searchNodes（Node goalNode）｛

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

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

｛

／／什么也不做

｝

｛

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

node．preNode＝goalNode／／設(shè)置節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)

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

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

｛

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

if（node．NewG＜node．G）／／若新值低于原值，因?yàn)樾碌穆窂绞歉玫倪x擇

｛

node．preNode＝goalNode／／設(shè)置節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)

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

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

｝

｝

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

｝

｝

3 實(shí)例與效率分析

為驗(yàn)證模型和算法的有效性，采用江蘇省某地區(qū)220kV輸電線路規(guī)劃對(duì)模型和算法進(jìn)行實(shí)例驗(yàn)證．在輸電線路規(guī)劃中，影響線路設(shè)計(jì)的主要因素有居民區(qū)、自然保護(hù)區(qū)、水源保護(hù)區(qū)、森林公園、風(fēng)景名勝區(qū)等環(huán)境敏感區(qū)，以及空間距離、高程、坡度等地形影響因素［10］．環(huán)境敏感區(qū)是禁止通行的區(qū)域，因此將其作為障礙因素，地形影響因素需計(jì)算其通行代價(jià)．根據(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

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

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

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

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

4 結(jié) 語

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

參考文獻(xiàn)（References）：

［1］ 張萬緒，張向蘭，李瑩．基于改進(jìn)粒子群算法的智能機(jī)器人路徑規(guī)劃［J］．計(jì)算機(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］ 趙開新，魏勇，王東署．改進(jìn)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究［J］．計(jì)算機(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］ 簡毅，張?jiān)拢苿?dòng)機(jī)器人全局覆蓋路徑規(guī)劃算法研究進(jìn)展與展望［J］．計(jì)算機(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］ 康冰，王曦輝，劉富．基于改進(jìn)蟻群算法的搜索機(jī)器人路徑規(guī)劃［J］．吉林大學(xué)學(xué)報(bào)：工學(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］．計(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é)報(bào)：信息科學(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án)瑞，龍毅，鄭玥，等．顧及地形起伏的步行最優(yōu)路徑分析算法［J］．武漢大學(xué)學(xué)報(bào)：信息科學(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é)姣．計(jì)及線路路徑優(yōu)化的空間電網(wǎng)規(guī)劃［J］．中國電機(jī)工程學(xué)報(bào)，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)用研究．

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

收稿日期：2015－05－05．

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

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1008－9497（2016）01－051－06