A＊算法在Shortest-Path方面的優(yōu)化研究①

梁昭陽, 藍茂俊, 陳正銘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

偽代碼如下:

4 實驗和對比分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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