基于A*算法的路徑規(guī)劃仿真平臺的設(shè)計與實現(xiàn)

楊陽

（湖北職業(yè)技術(shù)學(xué)院 湖北省孝感市 432100）

1 引言

最短路徑算法廣泛應(yīng)用于機器人路徑規(guī)劃、大型游戲?qū)ぢ贰⒄系K物規(guī)避、無人機航跡規(guī)劃及網(wǎng)絡(luò)應(yīng)用中，在實際生活生產(chǎn)中具有重要的作用。針對不同領(lǐng)域、不同條件下該問題的算法研究及設(shè)計改進也具有十分重要的理論價值和現(xiàn)實意義。最短路徑問題包含幾種形式:第一種是某兩個點之間，即確定好起點終點，求起點到終點之間的最短路徑；第二種是一張圖中，求任意兩個點、即所有兩點之間的最短距離；第三種是求某個指定點，到所有其余任意一點之間的最短距離。對于這幾種問題，目前國內(nèi)外有各種特定的的算法研究。

對于單源最短路徑問題，即求出某個指定點到所有點之間的最短距離，1959年Dijkstra[1]在論文中提出相應(yīng)的問題及解決算法。1962年Floyd[2]在提出了采用動態(tài)規(guī)劃的方法求多源點之間，即圖中任意兩個點之間最短路徑的算法。鑒于Dijkstra 算法在帶有負權(quán)邊的圖中不適用，Bellman-Ford 算法（Richard Bellman[3]和Lester Ford 分別提出）則能夠更普遍地解決單源最短路徑問題。這些算法都有不同的優(yōu)勢、算法復(fù)雜度與適用場景，在特定情況下，可以綜合各自的優(yōu)勢，實現(xiàn)目標算法效率的提升。

2 基礎(chǔ)路徑規(guī)劃算法

2.1 Floyd算法

Floyd（弗洛伊德）算法也稱為插點法，它采用動態(tài)規(guī)劃的方法尋找多源點之間最短路徑的解法。對于一張加權(quán)圖，每條邊上的權(quán)重可以是負值（避免負權(quán)回路），通過Floyd 算法可以計算出任意兩個點之間的最短路徑。Floyd 算法采用公式（1）[4]所示：

在上式中，G 為頂點之間的距離矩陣，s 為起點，g 為終點，i表示中間點，n 為頂點的個數(shù)。該表達式的含義是，計算出頂點s、i 之間的距離G[s][i]與頂點i、g 之間的距離G[i][g]，如果它們的和小于G[s][g]，則更新G[s][g]的值。按該方法循環(huán)遍歷所有i 的取值，發(fā)現(xiàn)其中G[s][g]的最小值，從而找到起點s 與終點g 之間的最短距離。為了描述該算法思想[5]，首先建立路徑規(guī)劃問題中各頂點距離值所對應(yīng)的初始鄰接矩陣A，并定義G(0)=A。

G(1)表示若只以頂點v1 為中間點所生成的距離矩陣更新值，G(2)表示若只以頂點v1、v2 為中間點所生成的距離矩陣更新值……以此類推，G(k)表示若只以頂點v1、v2、……vk 為中間點所生成的距離矩陣更新值。當k=n 時，便可求出G(n)的值，即可插入頂點v1、v2、……vn 作為中間點生成最終的距離矩陣更新值，從而求出任意兩個頂點之間的最短距離。

Floyd 算法的偽代碼可以表示為：

容易看出，F(xiàn)loyd 算法時間復(fù)雜度是O(N3)，空間復(fù)雜度是O(N2)，存在復(fù)雜度較高、路徑規(guī)劃時間較長的問題。

2.2 Dijkstra算法

Dijkstra(迪杰斯特拉)算法是基于貪心算法[6]的設(shè)計思想，是一種典型的單源最短路徑算法，既可以計算一個點到剩余所有點之間的最短距離，也可以用來獲得某兩個點之間的最短路徑。在該算法中，首先將某個頂點V0 作為根節(jié)點，然后將整個頂點集合分成兩個部分，即已計算出到V0 的最短距離的頂點的集合V（初始時只有V0）和剩余點集U，U 中每個頂點都保存著與V0 的最短距離值。在每次迭代中，在U 中尋找離V0 距離最短的頂點加入到V 中，并更新U 中剩余頂點距離V0 的最短距離值（因為V 中加入了新的頂點）。直到U 集合為空。Dijkstra 算法的偽代碼可以表示為：

在一般實現(xiàn)下，Dijkstra 算法時間復(fù)雜度是O(N2)，在優(yōu)化實現(xiàn)的情況下，算法時間復(fù)雜度可達到O(ElogV)，其中，E 為邊的條數(shù)，V 為頂點的個數(shù)。

2.3 Bellman-Ford算法

圖1：A*算法結(jié)果圖

Bellman-Ford(貝爾曼-福特)算法是一種求解單源最短路徑的算法，相比于Dijkstra 算法，它的優(yōu)點在于能夠處理負權(quán)邊的情況。該算法最多進行|V-1|次“松弛”[7]操作，從而得到從源點到|V-1|個頂點的最短路徑。在每次松弛操作中，根據(jù)每條邊的權(quán)值更新源點到頂點的距離值（源點到各頂點的初始化距離是∞）。在所有指定松弛操作結(jié)束后，如果增加一次遍歷還能產(chǎn)生更新值，則說明存在負權(quán)環(huán)。該算法的時間復(fù)雜度是O(VE)，其中，V 代表頂點數(shù)，E 代表邊數(shù)，該算法存在改進優(yōu)化的空間。

2.4 A*算法

A*算法是一種啟發(fā)式尋路算法。該算法在選擇最短路徑的下一個頂點時會計算起點到待檢測點的距離加上待檢測點到終點的估計距離之和作為判斷依據(jù)，用公式表示為F=G+H。其中，F(xiàn) 表示起始點到目標點的距離函數(shù)，G 表示起始點到待檢測點的真實代價值，H 是待檢測點到目標點的估計代價值。當H=0 時，該算法退化成Dijkstra 算法[8]。根據(jù)A*算法的核心原理，它在Dijkstra 算法的基礎(chǔ)上，增加了對待檢測點的啟發(fā)式評估，從而篩選了待檢測點，加快了生成最短路徑的效率。

3 A*算法的設(shè)計與實現(xiàn)

3.1 OPEN表和CLOSE表

和Dijkstra 算法類似，A*算法也把整個頂點集合分成兩個部分，已完成點集（CLOSE 表）和待檢測點集（OPEN 表）。從起點開始，將起點設(shè)置為當前點，不斷將周圍可達點加入到OPEN 表中。根據(jù)A*算法的基準公式F=G+H，選擇這些可達點中F 值最小的點作為新的當前點，舊的當前點被加入到CLOSE 表中。CLOSE 表中的頂點表示不再需要被關(guān)注的點。在算法運行過程當中，可達點加入到OPEN 表后，需要基于當前點更新其F 值，更新成功則設(shè)置當前點作為它的前驅(qū)頂點。算法在終點加入到OPEN 表時結(jié)束。最后，從終點沿著前驅(qū)回溯可以找到最短路徑。

表1：A*算法運行時間

圖2：A*算法運行時間圖

3.2 啟發(fā)式函數(shù)

A*算法中，每個頂點F 值的計算包括兩個部分：G 表示起點到待檢測點之間的距離，由于待檢測點是當前點的相鄰頂點或可達頂點，這個值可以直接計算出來；H 表示待檢測點到終點的估計值，也稱為啟發(fā)式函數(shù)，該值的計算需要考慮障礙物、移動方向（能否走對角線）、搜索區(qū)域的劃分等實際場景問題，以及距離計算公式的選擇。對于一個棋盤方格區(qū)域，距離計算公式可以采用曼哈頓距離，即將水平位移和垂直位移加和作為距離結(jié)果。同樣，也可以采用對角線距離、歐式距離等。

A*算法的優(yōu)化主要集中在OPEN 表的設(shè)計結(jié)構(gòu)和啟發(fā)式函數(shù)的選擇。一般情況下，可以使用順序查找表、優(yōu)先隊列等作為OPEN 表的數(shù)據(jù)結(jié)構(gòu)；啟發(fā)式函數(shù)則可以選擇曼哈頓距離、對角線距離、歐式距離等計算公式。

3.3 A*算法實現(xiàn)

如圖1 所示，在方陣地圖中，紅色方塊表示起點，紫色方塊表示終點，黑色方塊表示障礙物，綠色方塊表示路徑。在本A*算法路徑檢測中，會判斷周圍8 個位置是否可以通行，如果某位置沒有障礙物，將作為候選路徑選擇。障礙物采用隨機算法生成。

如果采用線性查找表作為OPEN 表結(jié)構(gòu)，A*算法每次都需要遍歷整個線性查找表，尋找其中F 值最小的頂點作為新的當前點，繼而將該當前點的有效相鄰頂點加入到OPEN 表中；并更新這些新加入頂點的F 值，以便下次搜索；

如果采用優(yōu)先隊列作為OPEN 表結(jié)構(gòu)，根據(jù)優(yōu)先隊列的性質(zhì)，具有最高優(yōu)先級的頂點先出隊列，這樣避免了線性查找表中全表搜素的時間消耗，加快了算法的運行速度。

圖1 展示了地圖大小分別為10*10 和20*20，OPEN 表結(jié)構(gòu)分別為線性查找表和優(yōu)先隊列情況下的運行效果圖。

分析圖2 關(guān)于A*算法在不同實現(xiàn)方式下運行時間的統(tǒng)計結(jié)果可得：隨著地圖規(guī)模的不斷增大，運行時間呈遞增趨勢；在同規(guī)模地圖大小的情況下，Open 表結(jié)構(gòu)采用優(yōu)先隊列的運行時間更短。如表1 所示。

4 結(jié)論（Conclusion）

路徑規(guī)劃算法是計算機應(yīng)用技術(shù)實踐于機器人尋徑和避障、大型游戲?qū)ぢ贰⒕W(wǎng)絡(luò)路由等場景中的重要算法。本文討論分析了Floyd 算法、Dijkstra 算法、Bellman-Ford 算法的基本定義、原理、算法復(fù)雜度，詳細介紹了A*算法的設(shè)計與實現(xiàn)，并構(gòu)建路徑規(guī)劃仿真平臺對A*算法進行驗證。實驗結(jié)果表明：算法運行時間同地圖規(guī)模及OPEN 表結(jié)構(gòu)相關(guān)。隨著地圖規(guī)模的不斷增大，運行時間呈遞增趨勢；在同規(guī)模地圖大小的情況下，OPEN 表結(jié)構(gòu)采用優(yōu)先隊列的運行速度更快。