前言
本文希望讀者預(yù)先擁有廣度優(yōu)先搜索(BFS)的知識，如果寫過廣搜解迷宮的題就更好了。
什么是尋路算法
當(dāng)我們給定一個地圖和終點(diǎn)起點(diǎn)的時候，我怎么找到一條最短(或者按情況最優(yōu))的路到達(dá)終點(diǎn)，這就是尋路算法要解決的基本問題。尋路算法有很多，暴力點(diǎn)的廣度優(yōu)先搜索或者dijkstra。這篇文章主要是介紹A*尋路并對比它和廣度優(yōu)先搜索的優(yōu)勢在哪里。
A*
A*算法，也可以叫Astar。我們先用一些偽代碼解釋一下其算法。
A*偽代碼
A*算法使用兩個狀態(tài)表，分別是Open表和Closed表。這里Open表由待考查的節(jié)點(diǎn)組成，而Closed表由已經(jīng)考查過的節(jié)點(diǎn)組成。那么什么樣的節(jié)點(diǎn)才算是“已考查過”的節(jié)點(diǎn)呢？對于一個節(jié)點(diǎn)來說，當(dāng)算法已經(jīng)檢查過與它相鄰的所有節(jié)點(diǎn)，并計(jì)算出了這些節(jié)點(diǎn)的f，g和h值(后面會解釋)，并把它們放入Open表中以待考查，那么這個節(jié)點(diǎn)就是“已考查過”的節(jié)點(diǎn)。
開始的時候，Closed表為空，而Open表里面只有起始節(jié)點(diǎn)。每次迭代中，A*算法將Open表中具有最小代價值(即f值最小)的節(jié)點(diǎn)取出進(jìn)行檢查，如果這個節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，那么考慮該節(jié)點(diǎn)的所有4個相鄰節(jié)點(diǎn)(如果是八方向的話就是相鄰的8個節(jié)點(diǎn))。
這里可以看出A和BFS的不同，這里取的是Open表中具有最小代價值的節(jié)點(diǎn)，所以一般A的實(shí)現(xiàn)都會依賴優(yōu)先隊(duì)列，這里就已經(jīng)可以看出A*的啟發(fā)式搜索了。而BFS只是按隊(duì)列的先進(jìn)先出取的節(jié)點(diǎn)，我們也可以稱之為盲目搜索。
然后對于每個節(jié)點(diǎn)按下列規(guī)則處理：
- 如果它即不在Open表中，也不在Closed表中，則將它加入Open表中。
- 如果它已經(jīng)在Open表中，并且新的路徑具有更低的代價值，則更新它的信息。
- 如果它已經(jīng)在Closed表中，那么檢測新的路徑是否具有更低的代價值。如果是，那么將它從Closed表中移出加入Open表。如果不是的話就忽略。
重復(fù)上述步驟直到達(dá)到目標(biāo)節(jié)點(diǎn)，如果Open表空了還沒達(dá)到目標(biāo)節(jié)點(diǎn)就說明沒有可達(dá)路徑。
A*核心概念介紹
估值函數(shù)
上面也點(diǎn)了一下，A*是啟發(fā)式搜索，那么什么是啟發(fā)式搜索？啟發(fā)式搜索和盲目搜索的區(qū)別是什么？
讀者可以想象一下這個場景，我以前上學(xué)的時候?yàn)榱粟s時間喜歡騎單車去教室，下課之后我到停車場的時候完全記不住我的單車究竟放在哪里了，這個時候我只能一輛一輛隨緣的"盲目"搜索。
如果我單車上有一個信號發(fā)射器，我可以知道單車距離我還有多少米，那么這個時候我只需要向各個方向嘗試走幾步，然后往距離縮減的方向前進(jìn)就行了，這就是啟發(fā)式。
估值函數(shù)其實(shí)就是這個告訴我單車離我現(xiàn)在多遠(yuǎn)的一個東西，當(dāng)然，實(shí)際情況下我們肯定無法得到一個準(zhǔn)確的“距離“，所以這個才叫“估值“函數(shù)，值是一個估計(jì)值。
A算法之所以效率高是因?yàn)樗菃l(fā)式的搜索算法，因此，A算法的執(zhí)行效率高低在非常大的程度上是依賴于估值函數(shù)的，估值函數(shù)構(gòu)造的越準(zhǔn)確，則A*搜索的時間越短。
估值函數(shù)的計(jì)算
之前偽代碼的時候我們出現(xiàn)了幾個神奇的變量f，g還有h，這些都是每個節(jié)點(diǎn)的屬性，現(xiàn)在我們來介紹一下它們。
g: 從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的代價。
h: 從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的"估計(jì)代價"
f=g+h: f是對經(jīng)過當(dāng)前節(jié)點(diǎn)的這條路徑的代價的一個最好的估計(jì)值，f的值越小，就認(rèn)為這個經(jīng)過這個節(jié)點(diǎn)的路徑越好。
實(shí)踐(Javascript)
(如果有時間再補(bǔ)這一部分吧，還有A*的解釋想畫幾個示意圖)
