本文作者:心月

A*算法實例詳解

心月IT博客 2019-02-26
摘要:A*搜尋算法俗稱A星算法。A*算法是比較流行的啟發式搜索算法之一,被廣泛應用于路徑優化領域。它的獨特之處是檢查最短路徑中每個可能的節點時引入了全局信息,對當前節點距終點的距離做出估計,并作為評價該節點處于最短路線上的可能性的量度。

A*搜尋算法俗稱A星算法。A*算法是比較流行的啟發式搜索算法之一,被廣泛應用于路徑優化領域。它的獨特之處是檢查最短路徑中每個可能的節點時引入了全局信息,對當前節點距終點的距離做出估計,并作為評價該節點處于最短路線上的可能性的量度。

A*算法描述:

A*改變它自己行為的能力基于啟發式代價函數,啟發式函數在游戲中非常有用。在速度和精確度之間取得折衷將會讓你的游戲運行得更快。在很多游戲中,你并不真正需要得到最好的路徑,僅需要近似的就足夠了。而你需要什么則取決于游戲中發生著什么,或者運行游戲的機器有多快。 假設你的游戲有兩種地形,平原和山地,在平原中的移動代價是1而在山地的是3,那么A星算法就會認為在平地上可以進行三倍于山地的距離進行等價搜尋。 這是因為有可能有一條沿著平原到山地的路徑。把兩個鄰接點之間的評估距離設為1.5可以加速A*的搜索過程。然后A*會將3和1.5比較,這并不比把3和1比較差。然而,在山地上行動有時可能會優于繞過山腳下進行行動。所以花費更多時間尋找一個繞過山的算法并不經常是可靠的。 同樣的,想要達成這樣的目標,你可以通過減少在山腳下的搜索行為來打到提高A星算法的運行速率。若想如此可以將A星算法的山地行動耗費從3調整為2即可。這兩種方法都會給出可靠地行動策略。

A*算法實例詳解:

A*算法詳解

在地圖中每個方格都有兩個屬性,一是方格是否可通行,二是指向其父結點的指針。

A星算法中有幾個相當重要的元素:

第一個就是指向其父結點的指針。

第二個就是OPEN表。

第三個就是CLOSE表,這兩張表的具體作用我們在后面邊用邊介紹。

第四個就是每個結點的F值(F值相當于圖結構中的權值) 。F = H + G 其中H值為從網格上當前方格移動到終點的預估移動耗費。這經常被稱為啟發式的,可能會讓你有點迷惑。

這樣叫的原因是因為它只是個猜測。我們沒辦法事先知道路徑的長度,因為路上可能存在各種障礙(墻,水,等等)。雖然本文只提供了一種計算H的方法,但是你可以在網上找到很多其他的方法。

我們定義H值為 終點所在行減去當前格所在行的絕對值 與 終點所在列減去當前格所在列的絕對值;

A*算法詳解

而G值為從其父方格移動到當前格的預估移動耗費,在這里我們設定一個基數10,每個H和G都要乘以10,這樣方便觀察

 

開始搜索:首先,我們將起點的父結點設置為NULL,然后將起點的G值設置為0,再裝進open表里面,然后將起點作為父結點的周圍4個點20,28,30,38(因為我們地圖只能走4個方向,如果是8方向,則要加個點進去)

都加進open列表里面,并計算每個結點的H值。然后再將起點從open列表刪除,放進close表中。

我們將放進close表的所有方格都用淺藍色線條進行框邊處理,所以這次搜索以后,圖片變為如下格式,其中箭頭代表的是其父結點

A*算法實例詳解

其中每個格子的左下方為G值,右下方為H值,左上方為H值。我們拿28號格子為例來講解一寫F值的算法,首先因為終點33在4行7列,而28在4行2列,則行數相差為0,列數相差為5,總和為5,

再乘以我們先前定的基數10,所以H值為50,又因為從28的父結點29移動到28,長度為1格,而29號為起點,G值為0,所以在父親結點29的基礎上移動到28所消耗的G值為(0 + 1) *10 = 10,

0為父親結點的G值,1為從29到28的消耗。當前OPEN表中的值: 20,28,30,38     當前CLOSE表中的值: 29

現在我們開始尋找OPEN列表中F值最低的,得出結點30的F值最低,且為40,然后將結點30從OPEN表中刪除,然后再加入到CLOSE表中,然后在判斷結點30周圍4個結點,因為結點31為障礙,

結點29存在于CLOSE表中,我們將不處理這兩點,只將21和39號結點加入OPEN表中,添加完后地圖變為下圖樣式

當前OPEN表中的值: 20,28,38,21,39   當前CLOSE表中的值: 29,30

A*算法實例詳解

接著我們重復上面的過程,尋找OPEN表中F值為低的值。我們發現OPEN表中所有結點的F值都為60,我們隨即取一個結點。這里我們直接取最后添加進OPEN表中的結點,

這樣方便訪問(因為存在這樣的情況,所有從一個點到另外一個點的最短路徑可能不只一條),我們取結點39,將他從OPEN表中刪除,并添加進CLOSE表中。然后觀察39號

結點周圍的4個結點。因為40號結點為障礙,所以我們不管它,而30號結點已經存在與OPEN表中了。所以我們要比較下,假設39號結點為30號結點的父結點,30號結點的G值會不會更小?

如果更小的話我們將30結點的父結點改為39號。這里我們以39號結點為父結點,得出30號結點的新G值為20。而30號結點原來的G值為10,并不比原來的小,所以我們不對30號進行任何操作。

同樣的對38號結點進行上述操作后我們也不對它進行任何操作,接著我們把48號結點添加進OPEN表中,添加完后地圖變為下圖樣式

當前OPEN表中的值: 20,28,38,21,48   當前CLOSE表中的值: 29,30,39

A*算法實例詳解

以后的過程中我們都重復這樣的過程,一直到遍歷到了最后終點,通過遍歷父結點編號,我們能夠得出一條最短路徑。

這里我再講出一個特例,然后基本A星算法就沒問題了。上面的最后一推導中,我們在觀察39號結點時,發現他周圍已經有結點在OPEN表中了,

我說"比較下假設39號結點為30號結點的父結點,30號結點的G值會不會更小,如果更小的話我們將30結點的父結點改為39號"。

但是剛才沒有遇到G值更小的情況,所以這里我假設出一種G值更小的情況。

然后讓大家知道該怎么操作,假設以39號為父結點,我們得出的30號的新G值為5(只是假設),比30號的原G值10還要小,所以我們要修改路徑,改變30號的箭頭,本來他是指向29號結點的,我們現在讓他指向39號結點,38號結點的操作也一樣

好了,A星算法的大體思路就是這樣了,對于8方向的地圖來說,唯一的改變就是G值方面,在上下左右,我們的G值是加10,但是在斜方向我們要加14,其他的和上面講的一樣~~~:)

文章版權及轉載聲明:

作者:心月 本文地址:http://www.rawkpk.live/algorithm/140.html發布于 2019-10-18
文章轉載或復制請以超鏈接形式并注明出處心月IT博客

分享到:
贊(

發表評論

快捷輸入:

    評論列表 (有 0 條評論,人圍觀)參與討論