帶啟發(fā)的尋路算法

A*算法尋路算法的一種，它與Dijkstra、BFS不同。A*算法適用于二維平面地圖上的尋路算法，而Dijkstra需要先將平面地圖轉(zhuǎn)化成帶權(quán)的有向圖。除此之外，Dijkstra只是做簡單的廣度優(yōu)先搜索，搜索效率比較低，而A*算法利用地圖上兩個(gè)點(diǎn)之間的位置和距離信息進(jìn)行高效的搜索。

首先介紹一下啟發(fā)式搜索算法。 啟發(fā)式搜索依賴于啟發(fā)函數(shù)，也就是評(píng)估函數(shù)。評(píng)估函數(shù)的作用是根據(jù)起點(diǎn)和終點(diǎn)的位置和距離信息給出下一步需要搜索各個(gè)位置的評(píng)估值。而啟發(fā)式可以利用各個(gè)位置的評(píng)估值：

A*算法啟發(fā)函數(shù)

A*算法的啟發(fā)原理結(jié)合了BFS算法和Dijkstra算法。BFS算法的評(píng)估函數(shù)考慮的是當(dāng)前點(diǎn)與終點(diǎn)的距離，其策略是選擇于終點(diǎn)最進(jìn)的點(diǎn)進(jìn)行搜索，而Dijkstra算法關(guān)注的是起點(diǎn)于當(dāng)前點(diǎn)的距離，其策略是選擇與起點(diǎn)最近的點(diǎn)開始搜索。A*算法的啟發(fā)函數(shù)也是兩者的結(jié)合。

A*算法的啟發(fā)函數(shù)公式是

F(n) = G(n) + H(n) G(n)是從當(dāng)前點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)距離 H(n)是從當(dāng)前點(diǎn)到終點(diǎn)的移動(dòng)距離的估計(jì)值

如果假設(shè)G(n) 為 0， 則算法效果于BFS相似。反過來，如果H(n)的值為0， 則算法效果于Dijkstra相似。

H(n)是A*算法的距離估計(jì)值，通過距離評(píng)估函數(shù)的計(jì)算得到這個(gè)值，下面介紹三種常用的距離評(píng)估函數(shù)：

曼哈頓距離

兩個(gè)點(diǎn)在各個(gè)坐標(biāo)軸上的距離差值的總和叫曼哈頓距離 D = |(X1 -X2)| + |Y1 - Y2| ~~~~~~~~~~~~

歐氏幾何平面距離

兩個(gè)點(diǎn)之間的真實(shí)距離 D = sqrt( (X1 - X2) ^2 + (Y1 - Y2)^2 ) ~~~~~~~~~~~~

切比雪夫距離

向量中各個(gè)分量的差的最大的絕對(duì)值 D = max( |X1 - X2|, |Y1 - Y2| )

距離評(píng)估函數(shù)H(n)的值越小，啟發(fā)信息越少，搜索范圍越大，速度越慢，但是越有希望得到最短的路徑

A*算法主要內(nèi)容

根據(jù)我看的書《算法的樂趣》里的大概說一下

A*算法的搜索過程需要兩個(gè)表，一個(gè)是OPEN表，存放當(dāng)前已經(jīng)被發(fā)現(xiàn)但是還沒有搜索過的節(jié)點(diǎn)。另一個(gè)是CLOSE表，存放已經(jīng)搜索過的節(jié)點(diǎn)。

A*算法的主要步驟有三步

1. 初始化OPEN表和CLOSE表，將起點(diǎn)加入到OPEN表中

2. 從OPEN表中取出當(dāng)前F(n)值最小的節(jié)點(diǎn)作為當(dāng)前的搜索節(jié)點(diǎn)NOW， NOW節(jié)點(diǎn)加入到CLOSE表中

3. 對(duì)于每一個(gè)于NOW可連通的節(jié)點(diǎn)ADJ， 考察ADJ節(jié)點(diǎn)：

如果ADJ已經(jīng)在CLOSE表中，則對(duì)該節(jié)點(diǎn)不作處理； 如果ADJ不再OPEN表中，則計(jì)算F(ADJ)，將ADJ的前驅(qū)節(jié)點(diǎn)設(shè)置成NOW并將ADJ加入到OPEN表中； 如多ADJ在OPEN表中，比較 G(NOW) + 1 < G(ADJ)，則令G(ADJ) = G(NOW) + 1，同時(shí)將ADJ的前驅(qū)設(shè)置為NOW；

重復(fù)步驟2，3，直到2步得到的搜索節(jié)點(diǎn)NOW就是終點(diǎn)為止