A*算法的規(guī)模控制與代碼實現(xiàn)

蔣曉南

摘要：A*算法是一種在靜態(tài)路網(wǎng)中求解最短路徑的最有效的方法，它是啟發(fā)式搜索中最具代表性的一種，目前被廣泛應(yīng)用在機器人、自動控制、游戲等多個AI領(lǐng)域。然而A*算法會隨著搜索規(guī)模的擴大而迅速降低搜索效率，所以有效控制A*搜索的規(guī)模才能讓它適應(yīng)更多場合。

關(guān)鍵詞：A*算法；規(guī)?？刂?/p>

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）22-0187-03

1概述

A*算法是一種在靜態(tài)路網(wǎng)中求解最短路徑最有效的方法。公式表示為：f（n）=g（n）+h（n），其中f（n）是從起點經(jīng)由節(jié)點n到達(dá)終點的估價函數(shù)，g（n）是在狀態(tài)空間中從起始節(jié)點到n節(jié)點的實際代價，h（n）是從n節(jié)點到目標(biāo)節(jié)點的最佳路徑的估計代價。能否找到最短路徑的關(guān)鍵在于估價函數(shù)h（n）的選取，如果估價函數(shù)h（n）的值小于等于n到目標(biāo)節(jié)點的距離實際值，這種情況下，搜索的點數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解。如果估價函數(shù)h（11）的值大于n到目標(biāo)節(jié)點的距離實際值，這種情況下，搜索的點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。

通過上段對A*算法的描述，可知A*算法會隨著搜索規(guī)模的擴大而迅速降低搜索效率，只有有效控制A*搜索的規(guī)模才能讓它適應(yīng)更多場合。本文會首先介紹A*算法的基本思想，接著在討論如何控制A*算法的規(guī)模，最后通過JAVA進(jìn)行代碼實現(xiàn)。

2A*算法的基本思想

A*算法通常會將搜索區(qū)域分割成大小相同的網(wǎng)格，這是對搜索區(qū)域進(jìn)行的有效簡化。這樣搜索區(qū)域就可以用一個簡單的二維數(shù)組進(jìn)行表示，數(shù)組中的一個元素就代表方格網(wǎng)中的一個方格。另外每個方格都必須被定義一個通過可能性的閥值，表示這個方格能否通過。接著，需要做的就是搜索從A到B需要經(jīng)過的最短方格路徑。如圖1，左側(cè)陰影方格A為起點，右側(cè)陰影方格B為終點，中間三個陰影方格為障礙物。

A*算法的搜索過程依賴于“路徑代價值”的估算，“路徑代價值”的計算公式就是緒論中提到的：f（n）=g（n）+h（n），這里簡單記為：F=G+H。

假定每次水平移動和豎直移動的代價為10，根據(jù)勾股定理，對角線的長度是兩個直角邊平方和的2次方根，因此對角的移動代價為14.14。為了簡單起見，本文使用10和14。

G是從起點A移動到給定方格的實際移動代價值。計算給定方格G值的方法是，用其移動路線中前一個方格的G值加上10或者14，分別對應(yīng)水平豎直移動和對角線移動。那么，前一個方格的G值如何計算呢？不用擔(dān)心，因為不斷往前延伸，總會找到起點，而起點的G值是0。圖2為起點方格A周圍八個方格的G值。

H是從給定方格移動到終點B的預(yù)估移動代價值。之所以稱為“預(yù)估”，是因為這只是一個猜測，它不考慮移動中可能遇到的障礙，只計算從給定方格水平或豎直移動到終點經(jīng)過的方格總數(shù)，并忽略對角移動和障礙物，然后將方格總數(shù)乘上水平或豎直移動一格的代價值10，以得到H值。圖3為起點方格A周圍八個方格的H值。

F是從起點經(jīng)由給定方格到達(dá)終點的綜合代價值，即G和H的簡單相加。圖4為起點方格A周圍八個方格的G、H、F值。

接下來A*算法會通過對F和G值的判斷找到最短路徑，但由于A*搜索過程復(fù)雜，本文不在這里贅述。

從圖中不難看出，如果想讓搜索到的路徑更加精確，必須將方格劃分的更小。然而這樣一來方格數(shù)量就會激增，從而增加A*搜索的規(guī)模，降低搜索效率。那么，如何才能在滿足應(yīng)用要求的情況下，降低搜索規(guī)模呢，這是本文下面要討論的內(nèi)容。

3A*算法規(guī)?？刂?/p>

實際應(yīng)用中，目標(biāo)往往只出現(xiàn)在某些固定的點，不會毫無規(guī)律；又或是應(yīng)用本身對精度要求并不高，只需要找到目標(biāo)所在區(qū)域即可?；谶@樣的思路，作者提出兩個降低搜索規(guī)模的可行方案。

如圖5所示，傳統(tǒng)方法會將搜索區(qū)域進(jìn)行這樣的劃分，并進(jìn)行A*搜索。本文下面以這張圖舉例分析如何降低搜索規(guī)模。

節(jié)點網(wǎng)：

如圖6所示，如果目標(biāo)只會出現(xiàn)在圖中小圓點位置，那完全沒有必要將圖劃分成那么多方格，只要將節(jié)點連接起來形成一張節(jié)點網(wǎng)，就可以使用A*算法找到這些點之間的最短連接路徑。

節(jié)點網(wǎng)和傳統(tǒng)網(wǎng)格方法的本質(zhì)是一樣的，它們都是對算法難以操作的狀態(tài)空間進(jìn)行簡化，但是節(jié)點網(wǎng)比傳統(tǒng)網(wǎng)格方法存儲代價低得多，但缺點是不能很好地適應(yīng)動態(tài)障礙。對于這個問題，較好的解決方法是在節(jié)點網(wǎng)中融合進(jìn)避障系統(tǒng)，利用避障系統(tǒng)來對付移動障礙，利用節(jié)點網(wǎng)來實現(xiàn)在地圖中的常規(guī)穿行，這樣即使在常規(guī)行進(jìn)的路線上出現(xiàn)障礙物，壁障系統(tǒng)也能幫忙躲開它。

區(qū)域網(wǎng)：

如圖7所示，搜索區(qū)域被劃分成幾個多邊形區(qū)域，如果對搜索精度要求不高，只需要確定目標(biāo)在某個區(qū)域，那么就可以使用這種區(qū)域網(wǎng)。設(shè)計時可以把多邊形區(qū)域的中心點作為節(jié)點，從而形成節(jié)點網(wǎng)。

區(qū)域網(wǎng)具有節(jié)點網(wǎng)的大多數(shù)優(yōu)點，而且更加節(jié)省存儲空間，但必須使用避障系統(tǒng)，而且如果構(gòu)建區(qū)域網(wǎng)的方法本身不夠智能，那么就會出現(xiàn)一些看起來非常奇怪的路徑。

避障系統(tǒng)：

本文前面提到的避障系統(tǒng)，是一種利用磁鐵同性相斥原理設(shè)計出來的避開障礙物的系統(tǒng)。

簡單得說，就是當(dāng)探路者根據(jù)A*算法搜索出來的最佳路徑行進(jìn)時，突然遇到移動障礙物，或是因為路徑計算不夠精確而與障礙物有碰擦的危險，就對探路者施加一個反作用力，距離越近反作用力越強，好像同極性的兩塊磁鐵，以此來避開障礙物。有了它，節(jié)點網(wǎng)和區(qū)域網(wǎng)就有了用武之地。

4代碼實現(xiàn)

由于本設(shè)計是用JAVA語言進(jìn)行程序?qū)崿F(xiàn)與測試，因此以下給出的均為JAVA源代碼。

節(jié)點網(wǎng)和區(qū)域網(wǎng)中都牽涉到節(jié)點問題，所以節(jié)點的設(shè)計尤為關(guān)鍵。

以下是“節(jié)點”類的成員變量和重要成員函數(shù)：

classNode{

private Node parentNode；//父節(jié)點，此變量非常重要，是獲得最佳路徑的線索

private Stringid；//為了便于測試，加人一個節(jié)點id，作為將來的輸出顯示

private boolean attainability；//節(jié)點是否可通過

private int X，Y；//節(jié)點的位置信息

private int G；//當(dāng)前點到起點的移動耗費

private int H；//當(dāng)前點到終點的移動耗費

privateint F；//f=g+h

public Node[]getNeighborNodes（Node[][]map）{…}//獲得周圍節(jié)點

publicintgetNeighborNodeCostG（Node neighborNode）{…}//獲得相鄰節(jié)點G值

public void costGHF（Node endNode）{…}//計算當(dāng)前節(jié)點GHF值

getNeighborNodes函數(shù)用于獲得當(dāng)前節(jié)點周圍的節(jié)點，并自動給無效的節(jié)點作出標(biāo)記（即給無效節(jié)點賦值null）。入口參數(shù)為一個Node類型的二維數(shù)組，返回一個Node類型的一維數(shù)組。

getNeighborNodeCostG函數(shù)用于獲得當(dāng)前節(jié)點的相鄰節(jié)點的G值。人口參數(shù)為一個相鄰節(jié)點，返回一個整型的G值。

costGHF函數(shù)用于計算當(dāng)前節(jié)點的GHF值。入口參數(shù)為A*搜索的終點，無返回類型。

以下是“尋路”類的成員變量和重要成員函數(shù)：

public class PathFinding{

private intnodeMapRow；//節(jié)點地圖行數(shù)

private intnodeMapColumn；//節(jié)點地圖列數(shù)

private Node[][]nodeMap；//地圖數(shù)組

private Node startNode；//起點

private Node endNode；//終點

private Stack open；//開啟列表

private Stack close；//關(guān)閉列表

private Node getMinCostNode（Stack s）{…}//獲得最小代價節(jié)點

private void Astar（）{…}//A*算法

public

Stack

getPath（intstartX，intstartY，intendX，intendY）{…}//獲得最佳路徑

public

void printPathontstartX，intstartY，intendX，intendY）{…}//打印最佳路徑

getMinCostNode函數(shù)用于從提供的開放列表中獲得最小代價值節(jié)點，同時將其從開放列表中刪除。函數(shù)入口參數(shù)為一個堆棧類型的開放列表，返回一個最小代價的節(jié)點。

Astar函數(shù)用于A*搜索，是本文最核心的函數(shù)之一。此函數(shù)既無人口參數(shù)也無返回類型，原因在于很多準(zhǔn)備工作已在其他類和函數(shù)中完成。

getPath函數(shù)用于獲得A*算法搜索出的路徑節(jié)點。入口參數(shù)為起點和終點的X、Y坐標(biāo)，返回的路徑節(jié)點用堆棧存儲。

printPath函數(shù)用于打印getPath獲得的最佳路徑。入口參數(shù)為起點和終點的X、Y坐標(biāo)，無返回類型。此函數(shù)在A*搜索中并不起任何作用，只是為了測試A*搜索而編寫的。

5結(jié)論

測試結(jié)果：

圖8和圖9，是使用本設(shè)計之前和之后針對同一個搜素區(qū)域進(jìn)行1000次循環(huán)搜索的對比。采用本設(shè)計后的搜索時間只有傳統(tǒng)方式的1/5，顯然大大縮減了搜索時間，提高了搜索效率。需要指出的是，本設(shè)計雖然有效降低的搜索規(guī)模，但并非適用于所有場合。至于所適用的場合在前文中已有討論，不在此贅述。