蔣曉南

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

關(guān)鍵詞：A*算法；規(guī)模控制

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

1概述

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

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

2A*算法的基本思想

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

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

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

G是從起點(diǎn)A移動(dòng)到給定方格的實(shí)際移動(dòng)代價(jià)值。計(jì)算給定方格G值的方法是，用其移動(dòng)路線中前一個(gè)方格的G值加上10或者14，分別對(duì)應(yīng)水平豎直移動(dòng)和對(duì)角線移動(dòng)。那么，前一個(gè)方格的G值如何計(jì)算呢？不用擔(dān)心，因?yàn)椴粩嗤把由?，總?huì)找到起點(diǎn)，而起點(diǎn)的G值是0。圖2為起點(diǎn)方格A周?chē)藗€(gè)方格的G值。

H是從給定方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)代價(jià)值。之所以稱為“預(yù)估”，是因?yàn)檫@只是一個(gè)猜測(cè)，它不考慮移動(dòng)中可能遇到的障礙，只計(jì)算從給定方格水平或豎直移動(dòng)到終點(diǎn)經(jīng)過(guò)的方格總數(shù)，并忽略對(duì)角移動(dòng)和障礙物，然后將方格總數(shù)乘上水平或豎直移動(dòng)一格的代價(jià)值10，以得到H值。圖3為起點(diǎn)方格A周?chē)藗€(gè)方格的H值。

F是從起點(diǎn)經(jīng)由給定方格到達(dá)終點(diǎn)的綜合代價(jià)值，即G和H的簡(jiǎn)單相加。圖4為起點(diǎn)方格A周?chē)藗€(gè)方格的G、H、F值。

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

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

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

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

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

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

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

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

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

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

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

避障系統(tǒng)：

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

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

4代碼實(shí)現(xiàn)

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

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

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

classNode{

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

private Stringid；//為了便于測(cè)試，加人一個(gè)節(jié)點(diǎn)id，作為將來(lái)的輸出顯示

private boolean attainability；//節(jié)點(diǎn)是否可通過(guò)

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

private int G；//當(dāng)前點(diǎn)到起點(diǎn)的移動(dòng)耗費(fèi)

private int H；//當(dāng)前點(diǎn)到終點(diǎn)的移動(dòng)耗費(fèi)

privateint F；//f=g+h

public Node[]getNeighborNodes（Node[][]map）{…}//獲得周?chē)?jié)點(diǎn)

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

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

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

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

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

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

public class PathFinding{

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

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

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

private Node startNode；//起點(diǎn)

private Node endNode；//終點(diǎn)

private Stack open；//開(kāi)啟列表

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

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

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

public

Stack

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

public

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

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

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

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

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

5結(jié)論

測(cè)試結(jié)果：

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