基于A*算法的最短路徑搜索的優化與研究

余博文 華北電力大學

1 引言

目前，有很多搜索圖的最短路徑，包括：迪克斯特拉算法、廣度優先搜索、深度優先搜索、回溯法等方法。在這些算法中，迪克斯特拉算法可以找到最短的路徑，但其搜索單源最短路徑的效率為O（n2）；廣度優先搜索可以找到到達終點的最短步數，不一定為最短的路徑；深度優先搜索為遞歸求解算法的非遞歸改進；而回溯法方法和深度優先搜索在短時間之內是無法實現的。

上述算法可歸為盲目搜索和啟發式搜索。啟發式搜索一般要優于盲目搜索，但不可過于追求更多的甚至完整的啟發信息。此次設計所采用的啟發式搜索，其啟發信息基于廣度優先搜索，恰到好處，搜索在迪克斯特拉算法的基礎上進行剪枝。

本文的意義在于完善一些關于基于矩陣（二維數組）存儲的圖類型的數據結構，進行最短路徑的搜索，使得針對于該圖類型數據結構的算法在構造、遍歷、修改等方面的操作實現達到了高時間效率和高空間效率，這是跟傳統圖類型數據結構相比較而言最大的區別。針對于無向圖最短路徑的搜索，突破了“在遞歸搜索、深度優先搜索、廣度優先搜索時對整個圖各個結點之間的邊要保持長度相同”的限制，比起在傳統的迪克斯特拉算法上，運用A*算法搜索圖的最短路徑，找到了最佳的啟發函數，進而找到了最佳的評估函數，并結合迪克斯特拉算法，實現了對迪克斯特拉算法時間效率上的優化。

例如，在電腦鼠迷宮搜索的位置過程中，最好的方法就是要用A*算法去搜索圖的最短路徑。因此，又快又能正確的找到最短路徑則是本次設計的關鍵。

通過本文所提供的啟發函數，展示最短路徑的準確搜索，即利用A*算法探究最短路徑過程的一個生動實例。本文與其他版本的最主要的區別，就是在電腦鼠移動到期望的位置之時，所走的路徑不是其他版本的只有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個方向的走法，而且還包括了向左上移）、向右上移）、向左下移）和向右下移（）四個方向。

但是，在進行迷宮搜索的過程中，還需考慮以下情況。

(1)當上（↑）、下（↓）、左（←）、右（→）四個相鄰的格子位置可以到達時，電腦鼠可直接移動到此時的目標位置，否則電腦鼠不可到達相應的目標位置。）、向左下移和向右下移）四個方向〕時，如果斜方向的左右

圖1 .1 相鄰四格子可達

圖1 .2 目標位置不可達

圖1 .3 斜方向可達，左右方向均可達

圖1 .4 斜方向可達，左右有一方不可達

(3)左右均不可達，則電腦鼠需繞道移動，不可穿過兩個不可達位置而移動。

圖1 .5 斜方向可達，左右方向均不可達，需繞道移動

2 A*算法與啟發式的設計

2.1 啟發式搜索

在搜索最短路徑時，如果把當前地圖的每一個格子及起點和終點都作為一個結點，把通道作為邊，則該地圖可以由一個有向圖來表示。那么，搜索最短路徑其實就是從該有向圖的初始結點（起點）出發，尋找目標結點（終點）的問題。抽象地來看，上述問題都是在某個有向圖中尋找目標或路徑的問題。通常，把這種描述問題的有向圖稱為狀態空間圖（簡稱狀態圖），用圖的概念來描述狀態空間。

狀態圖中的結點代表問題中的一種格局，稱問題中的一個狀態。邊表示結點之間的某種聯系。在狀態圖中，從初始結點到目標結點的一條路徑，或者所找的目標結點，就是相應問題的一個解。根據解題需要，路徑解可以表示為邊的序列或結點的序列。搜索最短路徑的解就是結點序列。

狀態空間可用有向圖來描述，圖的結點表示問題的狀態，圖的弧表示狀態之間的關系有向圖就是求解問題的步驟。初始狀態對應于實際問題的已知信息，是圖中的根結點。圖還可以定義目標條件，目標可以描述成一種狀態。在問題的狀態空間描述中，尋找從一種狀態轉換為另一種狀態的某個操作序列就等價于在一個圖中尋找某一路徑。各種操作的執行費用是不同的。

搜索策略有兩種基本方式：盲目搜索和啟發式搜索。所謂盲目搜索是指在不具有對特定問題的任何有關信息的條件下，按固定的步驟進行的搜索。所謂啟發式搜索則是考慮特定問題領域可應用的知識，動態地確定操作步驟。優秀選取較合適的操作，盡量減少不必要的搜索，以求盡快地到達結束狀態，提高搜索效率。在盲目搜索中，由于沒有可參考的信息，因此只要能匹配的操作都需運用，這會搜索出更多的狀態，生成較大的狀態空間顯式圖；而啟發式搜索中，如具有較多甚至完整的啟發信息，雖然只需運用少量的操作，只生成較小的狀態空間顯式圖，能將搜索引向一個解答，但是，每使用一個操作便需做更多的計算與判斷。

A*啟發式搜索法的基本特點是，如何尋找并設計一個與問題有關的g(n)（從初始結點到n 結點的實際代價）、h(n)（從n 結點到目的結點的最佳路徑的估計代價）及構造出估價函數f(n)=g(n)＋h(n)，然后以f(n)的大小來排列待擴展狀態的次序，每次選擇f(n)值最小者進行擴展。算法中有一步是根據某些啟發信息來排列open 表，它既不同于寬度優先所使用的“隊列”，也不同于深度優先所使用的“堆棧”，而是一個按狀態的啟發估價函數值的大小排列的一個“表”。進入open 表的狀態不是簡單地排在隊尾（或隊首），而是根據其估價的大小插入到表中合適的位置，每次從表中優先取出啟發估價函數值最小的狀態加以擴展。如果將寬度優先（或深度優先）看作特殊的A*算法，則可視“隊列”（或“堆棧”）為特殊的優先隊列，其啟發信息比較函數返回為固定值（如果隊列為false，則棧為true；反之亦然）。由是觀之，open 表必須保證在啟發信息相同的情況下，保證表內元素的穩定性；啟發信息不同，則自小向大排列。例如，根據字符串長度，對數組中的字符串元素進行排序。字符串數組為：['London', 'Berlin', 'Paris', 'Washington', 'Tokyo', 'Peking', 'Detroit', 'Texas', 'Orleans', 'New York']。

關于排序的方法有很多種。但這里提及該例是通過將字符串放入一個優先隊列性質的集合中，然后依次取出優先隊列中的各元素，直到優先隊列為空。顯然，排序的關鍵碼是字符串的長度，不同于以往的按字典序列排序。則將該字符串的關鍵碼提取出來，則可以表示為：[6, 6, 5, 10, 5, 6, 7, 5, 6, 8]。通過該例是為了說明上文提到的排序的穩定性。如果根據字符串的長度排序，為了保證穩定性，則該字符串數組排序完的結果只有唯一的一種：Paris、Tokyo、Texas、Lond on、Berlin、Peking、Detroit、Orleans、New York、Washington。提取出其關鍵碼，則為：[5, 5, 5, 6, 6, 6, 7, 7, 8, 10]。同樣關鍵碼為5 的“Paris”和“Tokyo”，如果順序顛倒，結果便成 為：['Tokyo', 'Paris', 'Texas', 'London', ……]，則 所 得 的 排序結果有違排序的穩定性。

這里之所以強調排序的穩定性，是因為如果采用了基于不穩定排序的優先隊列進行數據的存儲，那么所搜索出來的路徑雖然可以保證步數最少，但是所經過的距離卻不一定最短，所行走的路徑出現了“毛刺”。即在該拐彎的地方卻沒有拐彎，而在不必拐彎的地方卻出現了拐彎。這一現象尤其在只用寬度優先搜索時體現得更加明顯。此外，選擇不當的啟發信息亦會出現“毛刺”。圖2.1、2.2 為(1, 0)到(1, 4)的步數演示：

圖2.1 正確的最短路徑

圖2.2 出現“毛刺”的路徑

本文實驗為了保證優先隊列的穩定性，因而采用了可插入元素和僅可以每次取出一個元素，而該元素位于二叉樹中序遍歷的第一個輸出的元素，而所有元素的順序是已經排好順序的二叉排序樹作為實現A*算法中的open 表。

2.2 啟發式信息的設計

常見的獲取啟發信息的方法有計算“歐幾里得”距離、“曼哈頓”距離、“切比雪夫”距離。

“歐幾里得”(x1,y1)到(x2,y2)的距離計算公式：√(x1-y1)2＋(x2-y2)2；“曼哈頓”(x1,y1)到(x2,y2)的距離計算公式：|x1-x2|＋|y1-y2|；“切比雪夫”(x1,y1）到(x2,y2)的距離計算公式：max{|x1-x2|,|y1-y2|}；然而，本文使用的啟發信息，從(x1,y1)到(x2,y2)的距離 計 算 公 式 為：BFS((x1,y1),(x2,y2))；其 中，BFS((x1,y1),(x2,y2)) 表 示在圖中，(x1,y1)通過寬度優先搜索到(x2,y2)所經過的結點的最少個數，即從(x1,y1)到(x2,y2)的最少步數。

證明啟發式函數的精準度：以沒有任何障礙物的圖為例，假設從圖中的某一點進行遍歷，計算“歐幾里得”距離、“曼哈頓”距離、“切比雪夫”距離分別如圖2.3、圖2.4 和圖2.5。為了方便描述，可以將圖2.3簡記為矩陣M、將圖2.4 簡記為矩陣C、將圖2.5 簡記為矩陣E。

圖2.3 以“曼哈頓”距離為啟發信息（記“М”）

圖2.4 以“切比雪夫”距離為啟發信息（記“С”）

圖2.5 以“歐幾里得”距離為啟發信息（記“Е”）

比較各種啟發信息的準確度是根據以某一點為中心進行寬度優先搜索，各個結點記錄距出發點已走的步數。此時，將通過寬度優先遍歷所得到的矩陣記為В。所以，在八個方向的走法規則下，可以得到一個啟發信息如圖2.4 的矩陣С，則В-С=Ф，矩陣(В-Е)較矩陣(В-М)有更多取絕對值的元素接近于0。那么得出結論：精準度(В)≥精準度(С)＞精準度(Е)＞精準度(М)。

同理，如果是四個方向的走法，可以得到一個啟發信息如圖2.3的矩陣М，

則В-М=Ф。那么矩陣В 與其他矩陣做差，則矩陣(В-Е)較矩陣(В-С)有更多取絕對值的元素接近于0。那么得出結論：精準度(В)≥精準度(М)＞精準度(Е)＞精準度(С)。

不同的距離計算方法，適用于在不同的走法規則。假設只允許有向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個方向的走法，那么“曼哈頓”距離作為啟發信息的精準度將比“切比雪夫”距離和“歐幾里得”距離更完美；但如果走法規則如本作一樣允許八個方向的移動，那么“切比雪夫”距離作為啟發信息的精準度將比“曼哈頓”距離和“歐幾里得”距離更完美。

2.3 核心數據結構的設計

2.3.1 鄰接表的設計

此次采用的鄰接表，并非傳統意義上用鏈表實現，而是僅用一個字節就表示一個結點的鄰接結點。

圖2.6 比特位表示的鄰接表

該鄰接表的設計思想，是將每一個結點抽象為表示分支節點前進方向的各位字節。當某個結點的某一邊與其他結點連接時，則對應的位為1，否則該邊不與其他結點相連，則對應的位為0。這里，首先要定義一個方向列表，分別（例如）此順序存儲方向坐標{向右（0, 1）, 向 右 下（1,1）, 向 下（1,0）, 向 左 下（1,-1）, 向 左（0,-1）, 向 左 上（-1,-1）,向上（-1,0）, 向右上（-1,1）}。于是，字節的某一位（如第0 位）如果為1，則表示該結點右方向有結點；為0 則右方向無鄰接結點。如果所有結點均可達，且呈網格狀分布，則鄰接表（掩碼）如下：

圖2 .7 特殊的“鄰接表”(掩碼)

2.3.2 closed 表

這里所謂的closed 表指代關于某一結點在遍歷之時是否被訪問的標記，相對應于所有的結點，將是否被標記的屬性專門提取出來的布爾類型變量所構成的表稱為“closed”表。

在本文A*算法路徑規劃中，對于結點是否被訪問，每個結點有專門標記訪問情況的變量（屬性）。之所以這樣做，是因為通過標記結點是否被訪問的動作，來觀察整張圖的遍歷狀態，通過界面顯示結點是否被標記。

和一般得求最短路徑方法不同的是，這里的所有結點訪問標記先初始化為“true”。然后通過從某一結點開始進行寬度優先搜索，在記錄啟發信息的同時，也要把已經記錄啟發信息的結點訪問狀態改為“false”。寬度優先搜索在遇到目標結點之時則會停止遍歷，從而使一些啟發信息相同，但真正的最短路徑不需要經過的結點排除在外，達到“剪枝”的效果。這樣，在進行最短路徑搜索的時候，一些沒有經過寬度優先遍歷的結點便也會標記為“true”，以免不可能出現的狀態空間進入優先隊列，從而增加了搜索量。

圖2.8 從(1, 1)到(1, 2)的closed 表訪問情況 圖2.9 從(1, 1)到(0, 2)的closed 表訪問情況

假設求(1,1)到(1,2)，從右方向開始遍歷，則只有一個結點訪問，周圍七個均未訪問，表示只有(1,1)和(1,2)兩個結點需要進入優先隊列；從(1,1)到(0,2)，同樣從右方向開始遍歷，則周圍的八個結點均被訪問，那么，則需要讓(1,1)及其周圍的八個結點一并進入優先隊列。

3 A*搜尋最短路徑算法

3.1 A*搜尋算法

A*搜尋最短路徑算法流程圖如圖3.1。

圖2.10 A*搜尋最短路徑算法流程圖

A*搜尋算法的代碼如下：

算法1：A*搜尋算法

1.unsigned char search Path(int src X, int srcY, int d st X, int dstY) {

2.int i, curX, curY, surX, surY;

3. float surG;

4.BinarySortTree open; //優先隊列（Open 表）

5.Close *p;

6.bst_Initial(&open); //優先隊列初始化

7.closeInitial(dst X, dstY, src X, srcY); // 地 圖Close 表 初始化配置

8.close[dstX][dstY].visited = 1;

9.bst_Add Item(&open, close, dstX, dstY, 0); // 初 始 節 點入隊

10.while (!bst_IsEmpty(&open)) { //優先隊列為空？

11.p = bst_GetItem(&open); //取出估價函數最小節點

12.curX = p-＞currentNode-＞X;

13.curY = p-＞currentNode-＞Y;

14.if (p-＞H == 0) { //啟發信息為0？

15.bst_Destroy(&open);

16.return 1;

17.}

18.for (i = 0; i ＜ 8; i++) { //遍歷鄰接節點

19.if (! (p-＞currentNode-＞sur & (1 ＜＜ i))) continue;

20.surX = curX + direction[i].X;

21.surY = curY + direction[i].Y;

22.if (!close[sur X][sur Y].visited && close[surX][sur Y].H == close[curX][curY].H - 1) {

23.close[surX][surY].visited = 1;

24.close[surX][surY].from = p;

25.close[surX][surY].orientation = (i + 4) % 8;

26.sur G = p-＞G + (f loat)(i & 1 ? sqrt(2.0f) ： 1); // 記錄代價信息

27.bst_Add Item(&op en, close, surX, sur Y, sur G); // 將啟發信息比當前節點小的鄰接節點入隊

28.} // end if

29.} // end for

30.} // end while

31.bst_Destroy(&open);

32.return 0;33. }

特別的，第22步是根據啟發式信息特點，若當前啟發信息為n（≥1），則下一步的啟發信息必為n-1，這樣才做到對傳統的迪克斯特拉算法優化。這是與其他啟發信息相比，而所具有的不同之處。在找到是否存在最短路徑后，可以通過起始結點如鏈表索引般來搜索出整個路徑。

算法2：路徑索引

1. int symbolize Map(int src X, int src Y, int dst X, int dstY) {

2.Close *p;

3.int step = 0;

4.p = getPath(src X, srcY, dstX, dstY); // 獲取最短路徑的終止節點

5.if (p == NULL) return 0;

6.while (p-＞from != NULL) { //轉置路徑

7.w orld Terrain[p-＞current Nod e-＞X][p-＞current Nod e-＞Y].value =

8.S T E P + 1 + c l o s e[p-＞c u r r e n t N o d e-＞X][p-＞currentNode-＞Y].orientation;

9.p rin t f("（%d，%d） → ", p-＞cu r ren t Nod e-＞X, p-＞currentNode-＞Y);

10.p = p-＞from;

11.step++;

12.}

13.p r i n t f("（%d，%d） ", p-＞c u r r e n t N o d e-＞X, p-＞currentNode-＞Y);

14.world Terrain[srcX][srcY].value = SOURCE;

15. world Terrain[dst X][dstY].value = DESTINATION;

16.return step;17. }

例如，搜索在圖上從（0,0）點到（2,2）點上的最短路徑。圖為（1表示障礙物，0 表示可到達結點）：

圖2.11 搜索樹所用的地圖

圖2.12 以當前位置到達目標結點所需步數作為啟發信息的狀態空間示意圖

圖2.13 傳統的曼哈頓距離作為啟發信息的狀態空間示意圖

3.2 實驗比較

為了比較啟發信息對最終最短路徑搜索結果的影響，這里分別演示了以“曼哈頓”距離作為啟發信息，和基于寬度優先確立步數的啟發信息進行對比。其中，最短距離是以“迪克斯特拉”算法作為標準的。通過基于各種啟發信息搜索出來的路徑與迪克斯特拉算法計算出得到的最短距離進行比較，來判別出比較啟發信息的精準度（迪克斯特拉算法所得到的代價誤差小于10-6）。

例如，求(0,0)到(14,19)的最短路徑，如果以“曼哈頓”距離為啟發信息，則可以求得。而求從(14,19)到(0,0)的最短路徑，“曼哈頓”距離所用的最短步數為22 步。實驗結果的詳細記錄如表3.1。

圖3.1 以寬度優先為啟發式求出的從（0,0）到（14,19）點最短路徑

圖3.2 以寬度優先為啟發式求出的從（14,19）到（0,0）點最短路徑

表3 .1 路徑結果比較

由于該圖為無向圖，所以從起點到終點的最短路徑長度與從終點到起點的最短路徑長度是相同的。但最短路徑可以不同。而實際上，最少步數可以通過寬度優先求得，此時應為21步。最短路徑不一定唯一，但最短路徑的最少步數和最短路徑長度一定是唯一的。如果一條路徑的最少步數與正確路徑的所用最少步數不同，則該路徑所經過的最短路徑長度必為錯誤的。

而使用本文以寬度優先確立步數的啟發信息進行最短路徑搜索，則不會出現像“曼哈頓”距離那樣路徑的長度不相同的現象。這是由于：當圖的所有邊的權重均相同之時，可以利用寬度優先搜索求取兩個結點之間的最短路徑。這一原理廣泛地應用于四方向走法規則的情況，典型的例子就是迷宮求解。如果如本文允許八個方向的走法，向左上移（）、向右上移（）、向左下移和向右下移四個方向與向上移（↑）、向下移（↓）、向左移（←）、向右移（→）四個方向所花費的代價是不同的（前者為√2，后者為1）。

此外，有時候以“曼哈頓”距離為啟發信息根本搜索不到最短路徑，如表3.1 從(14,0)到(14,19)的結果。

如果想利用兩次以“曼哈頓”距離為啟發信息的搜索的結果取最小值長度的路徑作為最終結果返回，即將其起點與終點顛倒之后再進行搜索，以“曼哈頓”距離為啟發信息的搜索依然搜索不到最短路徑，如表3.1 從(14,19)到(14,0)的結果。

有時，即使以“曼哈頓”距離為啟發信息的路徑可以找到最少步數，但也不一定是最短距離，如表3.1 從(0,0)到(12,19)的結果。

4 結論

綜上所述，本文介紹的A*算法所求的啟發式信息方法其精準度要高于“曼哈頓”距離。但具體要使用哪種啟發式信息，還要看具體情況而定。如果圖的初始化過程比較簡單，則搜索的過程將會耗時較長；而圖的初始化過程，例如啟發信息的確立做的比較徹底的話，那么在搜索過程中，可以以接近于依次訪問最短路徑結點的效率搜索出正確結果。