梁昭陽, 藍(lán)茂俊, 陳正銘

(韶關(guān)學(xué)院 信息科學(xué)與工程學(xué)院, 韶關(guān) 512005)

A*算法是一種優(yōu)秀的啟發(fā)式搜索算法, 它整合了Greedy Best-First-Search算法、Dijkstra算法和一些距離計(jì)算公式的算法思想, 并利用了估值函數(shù)或評估函數(shù)作為啟發(fā)方法, 從而可以高效動(dòng)態(tài)地求得一條可能最優(yōu)的最短路徑, 因而A*算法一直被游戲開發(fā)行業(yè)和GIS系統(tǒng)開發(fā)等領(lǐng)域所廣泛采用[1]. 但目前的A*算法研究大多數(shù)都是基于任意圖而不是基于網(wǎng)格圖的游戲設(shè)計(jì)的, 本文將從多角度對A*算法在智能尋路中的搜索效率進(jìn)行改進(jìn).

1 傳統(tǒng)A*算法的簡介與分析

A*算法是一種尋找最短路徑的有效方法, 它常用于現(xiàn)代游戲的非玩家游戲(NPC)設(shè)計(jì)以及地理信息系統(tǒng)(GIS)開發(fā)等中. A*算法像很多求解最短路徑的算法一樣, 都可以找到地圖上兩點(diǎn)間的最短路徑. 在簡單圖上, 它跟Greedy Best-First-Search (貪心最佳路徑搜索算法)的效率基本上是相同的, 同樣可以利用啟發(fā)式進(jìn)行最短路徑的搜索. 啟發(fā)式(Heuristic Function)搜索是指在整個(gè)將要搜索的地圖中, 先對每一個(gè)將要訪問的節(jié)點(diǎn)進(jìn)行一個(gè)代價(jià)評估, 然后選擇最好的節(jié)點(diǎn), 再不斷迭代更新搜索, 直至尋找到目標(biāo)節(jié)點(diǎn).

啟發(fā)式搜索A*算法公式表示為:

G(n)表示從初始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)T, 在其搜索路徑的過程中, 到達(dá)期間某一節(jié)點(diǎn)n所花費(fèi)的代價(jià).H(n)表示從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)T的最優(yōu)路徑中將要花費(fèi)的估計(jì)代價(jià), 即最短路(Shortest-Path). 簡而言之, G(n)是實(shí)際代價(jià), H(n)是估計(jì)代價(jià), F(n)則表示節(jié)點(diǎn)n的估價(jià)函數(shù). 在保證存在最短路徑的條件下, A*算法的效率高低在于H(n)的選取, 假設(shè)R(n)表示n到目標(biāo)節(jié)點(diǎn)的距離的實(shí)際數(shù)值, 如果H(n)＞R(n), 則將要訪問的節(jié)點(diǎn)數(shù)目越少, 搜索的范圍越窄, 效率越高, 但不能保證得到最優(yōu)路徑. 如果H(n)≤R(n), 則將要訪問的節(jié)點(diǎn)數(shù)目越多, 搜索的范圍越廣, 效率越低, 但肯定能得到最優(yōu)路徑[2].

在A*算法的實(shí)現(xiàn)上, 使用OPEN列表和CLOSED列表來存放節(jié)點(diǎn). 將起始點(diǎn)放入OPEN列表中, 對OPEN列表中的節(jié)點(diǎn)按照啟發(fā)函數(shù)值進(jìn)行升序排序,CLOSED列表則用來存放計(jì)算后得出的OPEN列表的適合要求的節(jié)點(diǎn). 取出OPEN列表中第一個(gè)節(jié)點(diǎn), 如果是目標(biāo)節(jié)點(diǎn)就直接輸出最短路徑. 否則就計(jì)算下一個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)值, 將最優(yōu)的下一個(gè)節(jié)點(diǎn)放進(jìn)OPEN列表中, 同時(shí)將當(dāng)前節(jié)點(diǎn)從OPEN列表移到CLOSE列表中, 直至找到最短路徑[3].

A*算法效率高的主要原因是增加了估價(jià)函數(shù), 通過估價(jià)函數(shù)F(n), 合適地選取下一個(gè)代價(jià)最小的節(jié)點(diǎn),以此類推, 直到找到最終節(jié)點(diǎn), 相比傳統(tǒng)的無啟發(fā)函數(shù)的其他最短路徑算法, 其在效率上得到了明顯的提升.但是A*算法的啟發(fā)式函數(shù)是一種由經(jīng)驗(yàn)確定的函數(shù),估計(jì)函數(shù)往往決定了A*的路徑規(guī)劃, 節(jié)點(diǎn)的選擇也充滿了不確定性, 很難保證每次選擇的節(jié)點(diǎn)都是最優(yōu)解的, 具有一定幾率上在最優(yōu)節(jié)點(diǎn)的選擇出現(xiàn)錯(cuò)誤, 從而導(dǎo)致節(jié)點(diǎn)的意外刪除或者多余的節(jié)點(diǎn)選擇, 導(dǎo)致最后計(jì)算的路徑為非最優(yōu)路徑. 另外在計(jì)算過程中還可能出現(xiàn)“死循環(huán)”的現(xiàn)象, 形成“回環(huán)”等的無用搜索, 而無法獲取到最優(yōu)路徑. 因此, 如何優(yōu)化啟發(fā)式函數(shù)成為A*算法效率高低的主要因素.

A*算法在實(shí)際運(yùn)用時(shí)還可能會(huì)出現(xiàn)一個(gè)問題, 當(dāng)實(shí)際的地圖并不是一整塊的二維網(wǎng)格, 它是被很多障礙物給劃分成眾多個(gè)形狀不規(guī)則的地圖塊甚至是地圖點(diǎn), 并且每一個(gè)塊和點(diǎn)的密集程度都不可能一樣. 直接運(yùn)用A*算法對整張地圖尋找最短路徑會(huì)導(dǎo)致搜索效率低下.

2 A*算法的優(yōu)化方案

根據(jù)傳統(tǒng)的A*算法可能出現(xiàn)的一系列問題, 將從以下三個(gè)方面去考慮優(yōu)化和改良新的A*算法.

2.1 對可能出現(xiàn)“死循環(huán)”的優(yōu)化

可以利用“分治”的思想去解決在現(xiàn)實(shí)地圖中可能出現(xiàn)的“死循環(huán)”(Dead Loop)問題. 對現(xiàn)實(shí)中的地圖進(jìn)行具體地劃分成若干個(gè)塊, 然后再在這些塊中進(jìn)行最短路徑搜索, 用來解決“死循環(huán)”的問題. 例如在游戲常見的二維地圖上, 地圖被河流或者道路劃分成若干個(gè)不等的小塊, 每一個(gè)小塊都可以作為一個(gè)獨(dú)立的小地圖, 小地圖又由復(fù)雜的網(wǎng)絡(luò)節(jié)點(diǎn)所構(gòu)成, 如果形成的結(jié)構(gòu)還比較稠密, 則再劃分成一塊塊的獨(dú)立的小地圖, 這樣就可以把這些獨(dú)立的小地圖看成是一塊稀疏圖[4]. 可以先在稀疏圖中進(jìn)行最短路徑的搜索, 然后繼續(xù)在上一層的稠密圖中搜索最短路徑. 這種搜索策略可以用來克服“死循環(huán)”的問題, 而且對地圖進(jìn)行“分治”搜索到的路徑也是最優(yōu)最短的.

2.2 加入方向因子的優(yōu)化

啟發(fā)式函數(shù)(Heuristic Function)直接或者間接地決定著傳統(tǒng)的A*算法的搜索效率, 因此對于啟發(fā)函數(shù)的優(yōu)化處理是主要研究方向之一. 在傳統(tǒng)方法的基礎(chǔ)中引入方向這個(gè)因素, 用來提供更多的啟發(fā)信息[5]. 在尋路過程中把與目標(biāo)方向相反的節(jié)點(diǎn)給剪枝掉, 減少多余的計(jì)算量. 傳統(tǒng)的A*算法的啟發(fā)式函數(shù)H(n)是以距離信息為計(jì)算機(jī)引導(dǎo)方向的. 常用的有曼哈頓距離(Manhattan Distance), 歐幾里德距(Euclidean Distance), 對角線距離(Diagonal Distance), 切比雪夫距離(Chebyshev Distance)等, 而傳統(tǒng)的A*算法以歐幾里德距離作為啟發(fā)函數(shù)[6]. 地點(diǎn)A到地點(diǎn)B的歐幾里德距離(Euclidean Distance)為:

但是用歐幾里德距離成為啟發(fā)式函數(shù)有著很明顯的漏洞, 因?yàn)閷?shí)際代價(jià)G(n)可能會(huì)與啟發(fā)式函數(shù)H(n)發(fā)生相斥, 而且其開平方根會(huì)使計(jì)算機(jī)的計(jì)算開銷更大. 所以, 可以使用Octile距離來進(jìn)行優(yōu)化, Octile距離的主要思想就是假設(shè)只能進(jìn)行45°轉(zhuǎn)彎.

上式中max表示取最大值, min表示取最小值. 另外, 在選擇最優(yōu)節(jié)點(diǎn)路徑時(shí)還受到了方向(Direction)因素的影響, 如果只用距離來作為約束條件, 那么它就可能不是最優(yōu)的約束條件. 考慮從一個(gè)位置移動(dòng)到下一個(gè)位置的最小代價(jià)為D, 并加入方向因子(Direction Factor)θ來提高算法的效率與準(zhǔn)確性[7].

其中a作為權(quán)重比例系數(shù), 它取決了方向在A*算法中的關(guān)鍵性, 對于不同的情況, 這個(gè)權(quán)重比例系數(shù)要按照算法經(jīng)驗(yàn)進(jìn)行調(diào)整, 權(quán)重比例系數(shù)的大小和目標(biāo)的重要性以及策略的選擇有關(guān). θ則表示起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)構(gòu)成的矢量, 當(dāng)前節(jié)點(diǎn)與下一個(gè)最優(yōu)節(jié)點(diǎn)形成的矢量, 兩個(gè)矢量之間的夾角[8].

2.3 對節(jié)點(diǎn)排序的優(yōu)化

在傳統(tǒng)A*算法中, 每次訪問OPEN表必然需要找到F(n)值最小的節(jié)點(diǎn), 如果對OPEN表進(jìn)行整體的搜索比較, 會(huì)導(dǎo)致耗費(fèi)大量的時(shí)間. 可以采取對OPEN表的節(jié)點(diǎn)進(jìn)行排序, 在查找F(n)值最小的節(jié)點(diǎn)時(shí)就會(huì)節(jié)省大量時(shí)間. 對一些極限數(shù)據(jù), 單一的排序效率并不高.因此, 可以根據(jù)不同的數(shù)量級(jí)和不同的情況去采取不同的排序. 當(dāng)數(shù)據(jù)量相對大時(shí)就采用快排(QuickSort),并分段遞歸排序. 當(dāng)分段后的數(shù)據(jù)量小于某個(gè)閥值, 就采用插入排序(InsertionSort). 如果遞歸過深, 就采用堆排序(HeapSort). 采取這種優(yōu)化過的排序方法可以更有效地對OPEN表進(jìn)行升序排列. 最后, 每次對OPEN表中加入新的節(jié)點(diǎn)的時(shí)候我們采用二分插入的方法, 使得OPEN表始終保持有序狀態(tài). 這樣比每次都盲目地搜索整個(gè)OPEN表的速度要快至少50%的時(shí)間.

3 優(yōu)化的A*算法的偽代碼

偽代碼如下:

4 實(shí)驗(yàn)和對比分析

對于傳統(tǒng)A*算法中的啟發(fā)函數(shù)的優(yōu)化處理[9], 加入方向因子θ, 剪枝, 劃分小地圖, 部分細(xì)節(jié)代碼優(yōu)化等優(yōu)化方案后的A*算法的效率對比.

實(shí)驗(yàn)一. 單獨(dú)對節(jié)點(diǎn)排序的優(yōu)化, 尋找最短路徑時(shí)訪問的節(jié)點(diǎn)數(shù).

從表1的數(shù)據(jù)可以看出, 在障礙物稠密程度相同的情況下, 隨著地圖網(wǎng)格數(shù)的增大, 在運(yùn)行時(shí)間和網(wǎng)格訪問的數(shù)量上, 優(yōu)化過的A*算法要比傳統(tǒng)的A*算法都要少一部分, 在效率上, 經(jīng)過排序優(yōu)化的A*算法更優(yōu).

表1 批量數(shù)據(jù)比較結(jié)果

實(shí)驗(yàn)二. 選取有障礙的二維網(wǎng)格地圖作比較.

從圖1和圖2可以看出, 在障礙物稠密程度相同的情況下, 對于相同大小的地圖, 在運(yùn)行時(shí)間效率和節(jié)點(diǎn)訪問數(shù)量上進(jìn)行對比, 對未進(jìn)行優(yōu)化的傳統(tǒng)A*算法,訪問過的網(wǎng)格為483個(gè). 但經(jīng)過加入方向因子優(yōu)化過的A*算法, 范圍過的網(wǎng)格僅為191個(gè).

圖1 傳統(tǒng)A*算法最短尋徑過程

實(shí)驗(yàn)三. 綜合各種因素的A*算法的優(yōu)化, 顯示尋找最短路徑時(shí)訪問的節(jié)點(diǎn)數(shù).

圖2 加入方向因子優(yōu)化的A*算法最短尋徑過程

從表2的數(shù)據(jù)可以看出, 在障礙物稠密程度相同的情況下, 隨著地圖網(wǎng)格數(shù)的增大, 在運(yùn)行時(shí)間和網(wǎng)格訪問的數(shù)量上, 優(yōu)化過的A*算法要比傳統(tǒng)的A*算法都要少很多, 隨著地圖的增大, 二者在運(yùn)行時(shí)間效率和網(wǎng)格訪問數(shù)量上的差距越來越明顯, 提升效率約為50%.

表2 批量數(shù)據(jù)比較結(jié)果

5 結(jié)論

在傳統(tǒng)A*算法搜索策略的基礎(chǔ)上, 通過加入方向因子, 以及有效的剪枝和回溯, 部分細(xì)節(jié)代碼優(yōu)化等優(yōu)化方案, 進(jìn)一步地改進(jìn)A*算法的啟發(fā)式搜索策略. 最后的A*算法的評估實(shí)驗(yàn)證明, 優(yōu)化方案是有效的, 優(yōu)化的A*算法比傳統(tǒng)的A*算法, 較大地減小了算法搜索的規(guī)模, 減少了網(wǎng)格訪問數(shù)量和運(yùn)行時(shí)間.