基于A＊的雙向預(yù)處理改進(jìn)搜索算法①

秦 鋒，吳 健，張學(xué)鋒，趙晶麗

1(安徽工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，馬鞍山 243032)

2(滁州職業(yè)技術(shù)學(xué)院 信息工程系，滁州 239000)

引言

導(dǎo)航系統(tǒng)中的一項重要技術(shù)路徑規(guī)劃算法現(xiàn)已成為被廣泛運用的核心，屬于智能出行研究的熱點問題.大批學(xué)者圍繞Dijkstra 算法提出了很多改進(jìn)措施，例如最常見的A*算法.除了經(jīng)典算法之外，還有遺傳算法、蟻群算法、粒子群優(yōu)化算法等等.文獻(xiàn)[1]對Dijkstra 經(jīng)典算法做了研究工作，算法采用傳統(tǒng)遍歷模式搜索全局地圖網(wǎng)格上的節(jié)點，當(dāng)網(wǎng)格中存在大量節(jié)點時，由于算法的盲目搜索會造成大量冗余節(jié)點被遍歷，此時的算法效率非常低下[2].以傳統(tǒng)Dijkstra 算法作基礎(chǔ)，A*算法于1980年被Nilsson 首先提出[3]，該算法是一種利用啟發(fā)式信息函數(shù)作支撐的全局路徑規(guī)劃算法，算法明顯優(yōu)勢在于擴展當(dāng)前節(jié)點之前已經(jīng)引入了全局路網(wǎng)信息作為啟發(fā)信息，用來權(quán)衡下一個最優(yōu)路徑節(jié)點的位置.在擴展過程中需要不斷的迭代計算所有候選節(jié)點距離目標(biāo)節(jié)點的估價成本，估價成本越接近實際耗費成本則該條路徑越準(zhǔn)確.在文獻(xiàn)[4]中引入用類橢圓型作為限制區(qū)域，但計算復(fù)雜度大幅度提高.文獻(xiàn)[5]中又進(jìn)一步修改限制區(qū)域類型為矩形，降低了運行時間.在遍歷結(jié)構(gòu)確定的情況下，采用空間換時間的優(yōu)化策略.王士同等人[6]紅色首先提出了啟發(fā)式雙向搜索路徑規(guī)劃算法，并通過實驗論證了該算法的可行性.李清權(quán)等人[7]紅色在傳統(tǒng)算法上進(jìn)行改進(jìn)，改進(jìn)出一種立足于節(jié)點搜索的雙向A*啟發(fā)式路徑規(guī)劃算法.本質(zhì)上A*算法屬于最佳優(yōu)先算法范疇[8]，但該算法也存在明顯的缺點，當(dāng)存在多個最小值時或者路網(wǎng)中道路疏密程度不均時A*算法并不能保證搜索的路徑為最優(yōu)，會出現(xiàn)文獻(xiàn)[9]所論述的停滯不前的無限循環(huán).并且傳統(tǒng)A*算法在提高搜索精度的同時需要柵格地圖被分割的更小，為此帶來的另一大缺點即搜索時間會成指數(shù)級別的增長，因此本文在后續(xù)的改進(jìn)措施中引入了二叉堆進(jìn)行優(yōu)化.同樣估價函數(shù)的合理性也成為A*算法的一大缺點，會直接影響搜索效率.本文作者在研究過程中發(fā)現(xiàn)大部分的全局靜態(tài)路網(wǎng)規(guī)劃中障礙物節(jié)點信息總是保持不變，因此在規(guī)劃路徑之前系統(tǒng)即可提前預(yù)處理地圖信息將障礙物的鄰節(jié)點信息存入內(nèi)存，以便在同樣環(huán)境地圖規(guī)劃中直接通過鍵值對索引相應(yīng)的鄰節(jié)點信息，避免了重復(fù)遍歷地圖的繁瑣程序.針對傳統(tǒng)A*算法存在的缺點，本文對A*算法提出了改進(jìn)措施意圖提高算法效率和精度.引入預(yù)處理模式以及對遍歷結(jié)構(gòu)進(jìn)行優(yōu)化，其次對啟發(fā)函數(shù)式進(jìn)行歸一化操作消除不同量綱之間產(chǎn)生的影響.同時在前文提及的雙向搜索基礎(chǔ)上引入堆結(jié)構(gòu)作為效率較高的優(yōu)先級序列進(jìn)一步為路徑規(guī)劃提速.實驗結(jié)果表明了改進(jìn)算法的可行性與合理性.

1 路徑規(guī)劃問題概述

1.1 路徑規(guī)劃的分類

路徑規(guī)劃按照環(huán)境情況可分為全局路徑規(guī)劃和局部路徑規(guī)劃.全局路徑規(guī)劃代表地圖環(huán)境信息全部已知的情況，而局部路徑規(guī)劃則為環(huán)境部分未知或者完全未知需要自身感知力進(jìn)行實時獲取.另外環(huán)境情況又可分為靜態(tài)和動態(tài)，至此路徑規(guī)劃最終細(xì)分為如下四類，分別為全局靜態(tài)路徑規(guī)劃、全局動態(tài)路徑規(guī)劃、局部動態(tài)路徑規(guī)劃、局部靜態(tài)路徑規(guī)劃.全局靜態(tài)路徑規(guī)劃主要包含構(gòu)型空間法、自由空間法、柵格法.局部靜態(tài)路徑規(guī)劃主要包含人工勢場法、模糊邏輯算法.本文選用的是基于柵格法的全局靜態(tài)路徑規(guī)劃.

1.2 路徑規(guī)劃的步驟

路徑規(guī)劃的整體結(jié)構(gòu)基于算法具體功能實現(xiàn)，按照“整體感知-地圖建模-最優(yōu)路徑規(guī)劃-算法執(zhí)行操作”的過程依次執(zhí)行[10].首先對整體環(huán)境信息執(zhí)行初始化操作，依據(jù)節(jié)點和障礙物特性選擇合適的地圖.其次對整張地圖進(jìn)行建模操作，建模核心是需要與路徑規(guī)劃操作相適應(yīng)，地圖必須能夠高效的存儲、提取、更新節(jié)點信息.本文將物體的移動軌跡細(xì)分化變?yōu)閱蝹€方向上的路徑信息，將其離散化后路徑信息便被保存在了柵格地圖中.選用柵格地圖的原因在于相對于別的地圖建模其更具位置唯一性，因此在每個柵格節(jié)點中忽略物體的在任意方向上的微小偏移，只參考節(jié)點四周4 鄰域或者8 鄰域的方向信息便于操作[11-13]，圖1所示.地圖利用矩陣模式存儲節(jié)點，查找任意節(jié)點的行列數(shù)即可得知該節(jié)點具體信息.建立柵格模型后，需要對地圖模型整體進(jìn)行完整編碼標(biāo)記信息，常見的用0 或1 代表當(dāng)前節(jié)點有無障礙，編碼標(biāo)記完成之后還需要對地圖環(huán)境做幾個既定的準(zhǔn)則，如限定障礙物的位置和大小不變，柵格必須保證統(tǒng)一尺寸大小等.建模完成后配合改進(jìn)過后的算法對整張地圖進(jìn)行路線規(guī)劃，最后回溯拼接之前遍歷過的節(jié)點即得到一條規(guī)劃完成的路徑.

圖1 節(jié)點運動方向

1.3 Dijkstra 算法

Dijkstra 算法目的為找出從圖中的某個頂點出發(fā)到達(dá)另一個頂點所經(jīng)過邊的權(quán)重之和最小的那一條路徑.算法采用貪心策略模式使用廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑.主要思想如下，首先引入一個向量M，它的的每個分量M[i]代表從起始頂點V開始到其他各個頂點V[i]的距離.若V到V[i]有弧則將M[i]設(shè)為弧上的權(quán)值.顯然M[j]=Min{M|Vi∈V}即從起始頂點出發(fā)到頂點Vj距離最短的一條路徑，此時路徑為(V,Vj).接著定義一個存放從起始點V出發(fā)的最短路徑的頂點集合S.則下一條距離最優(yōu)的路徑必然為M[j]=Min{M[i]|Vi∈V-S}，M[i]為弧(V,Vi)上的權(quán)值或者為M[k](Vk∈S)和弧(Vk,Vi)權(quán)值總和(k為S中的一個頂點).直到遍歷完整張地圖網(wǎng)絡(luò)之后，算法根據(jù)局部最優(yōu)準(zhǔn)則選出一條最優(yōu)路徑，但是缺點在于整個搜索過程屬于盲目搜索只關(guān)注實際耗價值沒有考慮到待選節(jié)點對目標(biāo)節(jié)點所造成的影響，因此規(guī)劃過程將耗費大量的時間.

1.4 跳點算法

近年來研究人員推出了一種高效尋路算法Jump Point Search，也就是所謂的跳點算法.其本質(zhì)針對有序序列查找跳點與二分法類似，主要思想就是大范圍跳躍式搜索柵格網(wǎng)絡(luò)中對稱的路徑，只把其中的跳躍點當(dāng)作待搜索的柵格節(jié)點.其明顯優(yōu)勢在于大幅度減少openlist中的待選節(jié)點得益于在固定間隔的跳躍搜索過程中已經(jīng)剔除了網(wǎng)格地圖中大量無用節(jié)點.具體的實現(xiàn)大致涉及到兩個方面，第一步先遍歷openlist 表篩選出一個最優(yōu)節(jié)點，然后從幾個既定好的方向展開搜索，將每個方向獲得的跳點加入到openlist 表中.第二步在之前得到的各個方向上的跳點中篩選出代價最小的跳點作為新的起始點，從該點開始繼續(xù)向既定方向展開搜索.重復(fù)以上兩步操作，直到終點被存入到openlist 表中，尋路結(jié)束.但該算法仍然存在一些不可避免的限制因素，首先對地圖要求條件較高必須是規(guī)則的柵格型地圖，不支持復(fù)雜地形，網(wǎng)格節(jié)點不能帶權(quán)重，但相比傳統(tǒng)A*算法，其算法效率已經(jīng)提高了一倍左右.

1.5 傳統(tǒng)A＊算法

A*算法引入啟發(fā)函數(shù)h(n)對全局信息進(jìn)行估價，算法主要表達(dá)式:f(n)=g(n)+h(n)，其中f(n)為初始狀態(tài)經(jīng)過狀態(tài)n到達(dá)目標(biāo)狀態(tài)的代價估計，g(n)為初始狀態(tài)到達(dá)狀態(tài)n的移動耗費，h(n)為狀態(tài)n到達(dá)目標(biāo)狀態(tài)的將此估價作為最佳路徑可能性的量度.算法中關(guān)鍵的是兩個list 列表，用于存儲已經(jīng)遍歷和未遍歷的柵格節(jié)點，同時配合啟發(fā)函數(shù)對地圖上任意柵格節(jié)點距目標(biāo)節(jié)點的距離進(jìn)行有效估價，估價值越接近實際耗費，在四鄰域或八鄰域的情況下則會更好的尋找搜索方向.最低估計代價.A*算法步驟如下描述:

Step 1.將起始點加入openlist，并初始化openlist 和closedlist.

Step 2.openlist 若為空，結(jié)束算法.若不為空，計算最小的點，將該節(jié)點添加到最優(yōu)路徑上.

Step 3.對當(dāng)前處理的節(jié)點，以4 方向或者8 方向計算鄰節(jié)點，遍歷closedlist 和openlist，若均不包含鄰節(jié)點，則將其加入openlist.

Step 4.循環(huán)執(zhí)行Step 2 和Step 3 到算法結(jié)束，回溯遍歷之前拓展選中的路徑，則路徑規(guī)劃完成.

其中一般選用曼哈頓距離、歐式距離或者切比雪夫距離(當(dāng)h(n)=0時，A*算法將變?yōu)镈ijkstra 算法)，

2 改進(jìn)雙向預(yù)處理A*算法概述

綜合上述傳統(tǒng)算法的優(yōu)缺點，本文提出改進(jìn)策略提高算法效率.以經(jīng)典A*算法為基礎(chǔ)，先執(zhí)行雙向搜索策略從起點終點同時開始搜索，對算法中的角度和方向因子實現(xiàn)歸一化處理以消除不同量綱對節(jié)點參數(shù)所帶來的影響.同時提出改進(jìn)的算法結(jié)構(gòu)，將柵格地圖中的障礙物信息預(yù)處理存入內(nèi)存以減少資源消耗，并且對遍歷數(shù)組時的節(jié)點添加布爾類型的判定信息，初始化地圖后可直接依據(jù)此判定信息對節(jié)點是否在兩個列表中進(jìn)行判定而無須再做重復(fù)性的遍歷操作，進(jìn)一步提高算法效率.

2.1 并行化處理

引入并行化處理模式即實現(xiàn)雙向搜索算法，該模式將搜索過程分解為前向后向兩個獨立的搜索進(jìn)程，起點終點分別作為對方向的目標(biāo)節(jié)點.雙向搜索核心思路在于終止條件的判定，在理想狀態(tài)下兩條搜索路徑會在地圖路徑中心點相遇，此時兩個方向上的openlist中出現(xiàn)重復(fù)的節(jié)點即可判定規(guī)劃完成，這樣做可大大減少單向遍歷搜索所耗費的時間和空間資源.

2.2 矢量化和歸一化的改進(jìn)

A*算法在傳統(tǒng)估價函數(shù)的影響下，只會單一的進(jìn)行往返搜索生成大量的搜索節(jié)點.而在實際情況中當(dāng)前節(jié)點距離目標(biāo)節(jié)點的估價值一定不大于實際路徑耗費值，因此需要加快當(dāng)前節(jié)點向目標(biāo)節(jié)點的收斂速度即增大估價函數(shù)h(n)的權(quán)值.考慮到大部分的權(quán)值設(shè)定都視具體的地圖情況例如地圖大小，障礙物數(shù)量，地形因素而定因此具有片面性.并且當(dāng)前節(jié)點距離目標(biāo)節(jié)點的估價距離占實際距離的比重與當(dāng)前節(jié)點在地圖中的位置相關(guān).本文在前文基礎(chǔ)上，在當(dāng)前節(jié)點遠(yuǎn)離目標(biāo)點，此時估價值低于實際值，增大權(quán)重.相對應(yīng)的當(dāng)前節(jié)點靠近目標(biāo)點時，當(dāng)前估價值接近實際值，相對應(yīng)的降低權(quán)重.因此本文引入以指數(shù)衰減方式的權(quán)重因子，對傳統(tǒng)A*算法表達(dá)式做出如下修改.公式為:

式中的w1與w2分別為距離和角度的權(quán)重系數(shù)，其取值范圍分別為0.55-0.65 和0.35-0.45[15].L表示當(dāng)前節(jié)點距目標(biāo)點的距離值，α表示起點至當(dāng)前節(jié)點連線的線段與當(dāng)前節(jié)點至目標(biāo)節(jié)點連線線段的夾角值.根據(jù)地圖大小引入權(quán)重系數(shù)的優(yōu)勢在于，同時權(quán)衡距離信息與方向信息，加快搜索進(jìn)程.由于不同的評價標(biāo)準(zhǔn)具有不同的量綱，為了消除指標(biāo)之間量綱的影響，需要進(jìn)行數(shù)據(jù)歸一化標(biāo)準(zhǔn)處理，保留其本身所有特性，但是減少參數(shù)大小產(chǎn)生的影響，歸一化大大加快了梯度下降求最優(yōu)解的速度.針對本文的思路，對h(n)估價函數(shù)的距離和角度因子進(jìn)行歸一化處理，對遍歷進(jìn)行提速.本文對文獻(xiàn)[19]的估價函數(shù)提出改進(jìn)，采用Z-score 標(biāo)準(zhǔn)化方法對距離和角度消除量綱影響因素，標(biāo)準(zhǔn)化公式為:

其中，μ為所有樣本數(shù)據(jù)的均值，σ為所有樣本數(shù)據(jù)的標(biāo)準(zhǔn)差.將距離和角度因子代入(n代表鄰節(jié)點的數(shù)量)公式中:

此時h?(n)修改為

原算法f(n)改進(jìn)為

式(10)意義在于當(dāng)估價函數(shù)h?(n)數(shù)值較大時，權(quán)重因子增大同時g(n)占比重減小，當(dāng)前節(jié)點加速向目標(biāo)節(jié)點收斂.當(dāng)h?(n)較小時，權(quán)重因子也隨之減小反之g(n)占比重增大.當(dāng)權(quán)重因子逼近1時表明當(dāng)前節(jié)點已經(jīng)靠近目標(biāo)點.仿真實驗中表2的數(shù)據(jù)結(jié)果表明相比于文獻(xiàn)[19]的A*算法和跳點算法，搜索節(jié)點數(shù)和搜索時長有明顯降低，實時性有顯著提高.同時參照幾張運行效果截圖，表明在距離和角度這兩個權(quán)重系數(shù)的影響下，搜索深度明顯減少，搜索方向被顯著的約束在更趨向于目標(biāo)點的方向上證明了該公式的可行性.

2.3 基于堆結(jié)構(gòu)的完全排序

傳統(tǒng)A*算法中，計算機性能耗費關(guān)乎地圖大小和反復(fù)遍歷openlist中F值最小點這兩個因素，所以路徑規(guī)劃耗費的時長和所達(dá)到的精度取決于算法中存儲列表方式的設(shè)計.本文在傳統(tǒng)A*算法中引入二叉堆.二叉堆實則是以堆結(jié)構(gòu)存在的一種特殊的樹，可以保證數(shù)據(jù)結(jié)構(gòu)的有序性以提高搜索效率，是一種優(yōu)先級序列.它的優(yōu)點在于在堆結(jié)構(gòu)中子節(jié)點與父節(jié)點的鍵值總是以一種特定的有序關(guān)系相聯(lián)系，由此帶來的好處是在計算過程中并不需要直接得到完整的全局有序信息，而只需要全局節(jié)點的極值以避免造成不必要的資源浪費.本文中堆結(jié)構(gòu)被用于優(yōu)化從開啟列表移除節(jié)點數(shù)據(jù)，向關(guān)閉列表添加節(jié)點數(shù)據(jù)，可以保證兩個列表始終保持內(nèi)部數(shù)據(jù)有序.本文引入的二叉堆結(jié)構(gòu)主要涉及向open 列表添加新元素和在切換至close 列表后從堆頂刪除F 值最小的元素.添加元素操作主要步驟為，首先將起始節(jié)點添加至open 列表，同時計算新元素的G、H、F值并將新元素添加至開啟列表的底端，然后依次比較該元素和該元素的父節(jié)點直到該元素到達(dá)表中正確的位置.刪除操作主要步驟為在刪除某個元素之后將當(dāng)前的末元素移動至堆頂端，依次比較該元素和它兩個子節(jié)點元素的F值，如果該元素的F耗價值高于其兩個子節(jié)點則交換它與其中較低F值的節(jié)點，重復(fù)該過程直到該元素找到在堆中的相應(yīng)位置.

實現(xiàn)二叉堆主要偽代碼如下:

算法1.向堆中添加新元素獲取表最后一位下標(biāo)；last←open.length-1；while (last ＞ 1)half←last；與父節(jié)點比較F 值大小；If(open[last].F＞=open[half].F)THEN break；在表中與父節(jié)點調(diào)換位置；temporary←open[last]；open[last]←open[half]；open[half]←temporary；

算法2.從堆中刪除元素將堆底端元素移至堆頂；open[1]←open[last]；重新獲得堆末位元素下標(biāo)last←open.length-1；head←1；先比較堆頂節(jié)點兩個子節(jié)點F 值大小，找出較小F 值的子節(jié)點；childMin←open[child1].F＜o(jì)pen[child2].F?child1:child2；比較父節(jié)點與較小子節(jié)點F 值大小；IF(open[head].F＜=open[childMin].F THEN break；若父節(jié)點F 值大于子節(jié)點F 值，則交換位置；temporary←open[head]；open[head]←open[childMin]；open[childMin]←temporary；交換父節(jié)點與較小子節(jié)點的位置；head=childMin；

2.4 實現(xiàn)預(yù)處理結(jié)構(gòu)

前面已經(jīng)提及采用并行二叉堆且加入矢量化因子已經(jīng)提高了計算性能，但優(yōu)化的實質(zhì)大多數(shù)是空間換時間，因為在全局靜態(tài)地圖中障礙物信息保持不變并且鄰域柵格的耗價值也是不變的，但如果每次尋路時都去計算鄰節(jié)點網(wǎng)格是否存在障礙物則會消耗大量時間.因此把算法中部分過程的計算先執(zhí)行預(yù)處理后存入內(nèi)存.本文首先對障礙物鄰節(jié)點進(jìn)行預(yù)計算，對當(dāng)前節(jié)點首先判斷該節(jié)點周圍是否存在障礙物并同時計算鄰域柵格的耗價值.具體步驟如下，首先為所有的節(jié)點添加一個新的代表鄰節(jié)點的數(shù)組AdjNodeArray，同時構(gòu)造新的鄰節(jié)點耗費值數(shù)組AdjNodeCost，這兩個數(shù)組是為了初始化時存入鄰域的節(jié)點信息.保證AdjNodeArray[i]與AdjNodeCost[i]兩個數(shù)組的映射關(guān)系以便于在查詢某個鄰域節(jié)點時可直接對應(yīng)查找其耗價值.其次在地圖初始化的過程中，先進(jìn)行預(yù)處理操作遍歷所有的地圖網(wǎng)格，找出地圖中節(jié)點標(biāo)記編號為0(柵格地圖中障礙物編號為1，非障礙物為0)的所有非障礙方格節(jié)點存入鄰節(jié)點AdjNodeArray，同時計算鄰節(jié)點耗費值映射存入AdjNodeCost.最后涉及到具體尋路過程需要判斷當(dāng)前節(jié)點附近鄰節(jié)點信息時，直接從鄰節(jié)點數(shù)組AdjNodeArray中讀取當(dāng)前節(jié)點的屬性值就能得知此節(jié)點周圍鄰節(jié)點的全部屬性值而無需再重復(fù)計算.例如在預(yù)處理地圖之后尋路過程中需判定二維坐標(biāo)號為(6，9)的當(dāng)前節(jié)點信息以及下一節(jié)點的選擇情況，只需要先在鄰節(jié)點數(shù)組找到當(dāng)前點判定是否為非障礙物節(jié)點，并根據(jù)映射關(guān)系就可直接得到該節(jié)點的鄰節(jié)點耗價值，接著相應(yīng)的通過估價函數(shù)選擇下一步行進(jìn)的路徑節(jié)點，重復(fù)以上操作直至找到終點.預(yù)處理大大縮減每次遍歷地圖計算計算節(jié)點信息的時間.另外算法結(jié)構(gòu)中每次搜索數(shù)組采用的常規(guī)遍歷操作indexof 實際占用了大量的運算時間，本文同樣對數(shù)組遍歷進(jìn)行優(yōu)化，對每個節(jié)點賦予布爾類型屬性isopen 和isclosed作為標(biāo)記信息，每次對當(dāng)前節(jié)點進(jìn)行push 操作時，在openlist中設(shè)置當(dāng)前節(jié)點的布爾屬性isopen 為true，當(dāng)下一步操作將該節(jié)點移出開啟列表后，同時更改isopen 值為false，這樣處理的優(yōu)勢在于，判斷當(dāng)前節(jié)點是否在openlist中，只需要對應(yīng)的獲取它的布爾值即可.同理可以判斷節(jié)點是否存在于closedlist中.

3 實驗結(jié)果對比分析

為了驗證改進(jìn)A*算法的實際效果，本文設(shè)置不同的對照組在柵格地圖中進(jìn)行大量的數(shù)據(jù)測試.實驗環(huán)境為Intel Core i5，Win10，8 GB 內(nèi)存，采用Matlab 2012a 編譯.

3.1 實驗過程

本文建立一個20×30的柵格地圖，將起始點與終點設(shè)定在柵格地圖的(2，2)，(20，30)坐標(biāo)處.如圖2所示.

應(yīng)用本文改進(jìn)A*算法對圖2所示地圖模型進(jìn)行計算，選取權(quán)重系數(shù)w為0.59 首先進(jìn)行第一次預(yù)處理將地圖信息存入內(nèi)存，預(yù)處理完成后進(jìn)行第二次路徑規(guī)劃，運行結(jié)果如表1所示.

其次保持地圖環(huán)境不變，選用其它傳統(tǒng)算法同樣對該地圖進(jìn)行仿真計算，得出多組結(jié)果如表2所示.其中，M和E分別代表選用曼哈頓距離或歐式距離，Dijkstra 與跳點算法不區(qū)分鄰域數(shù)及選用的距離函數(shù).部分程序運行截圖如圖3所示.

圖2 柵格地圖

圖3中圖(a)、(b)、(c)、(d)依次是改進(jìn)A*算法分別計算8 鄰域歐式距離，4 鄰域曼哈頓距離，4 鄰域歐式距離運行效果截圖，圖中黑色實心圓點為起點與終點，粗體黑色實線為規(guī)劃路線，斜向黑色實線表示本次規(guī)劃所遍歷的節(jié)點方格.以及Dijkstra 算法運行效果截圖.

表1 預(yù)處理前后運行效率對比

表2 不同算法運行效率對比

圖3 幾種規(guī)劃算法運行效果截圖

3.2 計算效率對比

從表2 可以看出，在相同的地圖環(huán)境下，本文改進(jìn)的A*算法所仿真得到的路徑相比于文獻(xiàn)[19]的A*算法和跳點算法，雖然路徑長度有一定程度的增加，但因為其歸一化的方向和角度因子，以及對數(shù)組遍歷的優(yōu)化，使得遍歷節(jié)點數(shù)比例降低，尤其在4 鄰域的條件下節(jié)點數(shù)下降趨勢更為明顯，數(shù)據(jù)表明在8 鄰域標(biāo)準(zhǔn)下，本文改進(jìn)過后的算法相比于Dijkstra，文獻(xiàn)[19]的A*，跳點算法節(jié)點數(shù)分別下降48.93%，9.01%，35.05%.在4 鄰域標(biāo)準(zhǔn)下分別下降35.21%，24.31%，17.60%.證明了改進(jìn)A*算法的矢量化與歸一化處理能夠有效的降低搜索節(jié)點數(shù).同時，搜索時長較A*算法與跳點算法都有不同程度的提升，8 鄰域條件下相比于文獻(xiàn)[19]A*與跳點算法，時長分別降低35% 和18.75%，4 鄰域條件下，時長分別降低65%和39.13%，由此可以證明引入堆結(jié)構(gòu)可大幅度降低遍歷時長.同樣表1 可以看出第一次預(yù)處理地圖信息之后的第二次遍歷時長在8 鄰域和4 鄰域的標(biāo)準(zhǔn)下分別下降27.78%與6.67%，表明對地圖節(jié)點的預(yù)處理操作提前處理節(jié)點附近的障礙物信息并且進(jìn)行內(nèi)存預(yù)存儲以及對數(shù)組添加布爾型標(biāo)記信息的優(yōu)化，都能有效降低后續(xù)遍歷時長.

4 結(jié)束語

如今以啟發(fā)式搜索為核心的A*算法在導(dǎo)航尋路規(guī)劃領(lǐng)域得到了廣泛的應(yīng)用.結(jié)合經(jīng)典A*算法與本文的雙向預(yù)處理改進(jìn)A*算法，本文算法在規(guī)劃時長方面更具優(yōu)勢，得益于改進(jìn)的預(yù)處理算法結(jié)構(gòu)以及權(quán)重系數(shù)對歸一化處理后的方向距離因子的收斂加速特性，運行實驗結(jié)果表明本文改進(jìn)算法規(guī)劃路徑的可行性.