前言
本文希望讀者預先擁有廣度優(yōu)先搜索(BFS)的知識旺罢，如果寫過廣搜解迷宮的題就更好了氏淑。
什么是尋路算法
當我們給定一個地圖和終點起點的時候，我怎么找到一條最短(或者按情況最優(yōu))的路到達終點纤房，這就是尋路算法要解決的基本問題。尋路算法有很多暮现，暴力點的廣度優(yōu)先搜索或者dijkstra。這篇文章主要是介紹A*尋路并對比它和廣度優(yōu)先搜索的優(yōu)勢在哪里痢毒。
A*
A*算法送矩，也可以叫Astar。我們先用一些偽代碼解釋一下其算法哪替。
A*偽代碼
A*算法使用兩個狀態(tài)表栋荸，分別是Open表和Closed表。這里Open表由待考查的節(jié)點組成凭舶，而Closed表由已經(jīng)考查過的節(jié)點組成晌块。那么什么樣的節(jié)點才算是“已考查過”的節(jié)點呢？對于一個節(jié)點來說帅霜，當算法已經(jīng)檢查過與它相鄰的所有節(jié)點匆背，并計算出了這些節(jié)點的f，g和h值(后面會解釋)身冀，并把它們放入Open表中以待考查钝尸，那么這個節(jié)點就是“已考查過”的節(jié)點。
開始的時候搂根，Closed表為空珍促，而Open表里面只有起始節(jié)點。每次迭代中剩愧，A*算法將Open表中具有最小代價值(即f值最小)的節(jié)點取出進行檢查猪叙，如果這個節(jié)點不是目標節(jié)點，那么考慮該節(jié)點的所有4個相鄰節(jié)點(如果是八方向的話就是相鄰的8個節(jié)點)仁卷。
這里可以看出A和BFS的不同穴翩，這里取的是Open表中具有最小代價值的節(jié)點，所以一般A的實現(xiàn)都會依賴優(yōu)先隊列锦积，這里就已經(jīng)可以看出A*的啟發(fā)式搜索了芒帕。而BFS只是按隊列的先進先出取的節(jié)點，我們也可以稱之為盲目搜索丰介。
然后對于每個節(jié)點按下列規(guī)則處理：
- 如果它即不在Open表中背蟆，也不在Closed表中，則將它加入Open表中基矮。
- 如果它已經(jīng)在Open表中淆储，并且新的路徑具有更低的代價值冠场，則更新它的信息家浇。
- 如果它已經(jīng)在Closed表中，那么檢測新的路徑是否具有更低的代價值碴裙。如果是钢悲，那么將它從Closed表中移出加入Open表点额。如果不是的話就忽略。
重復上述步驟直到達到目標節(jié)點莺琳，如果Open表空了還沒達到目標節(jié)點就說明沒有可達路徑还棱。
A*核心概念介紹
估值函數(shù)
上面也點了一下，A*是啟發(fā)式搜索惭等，那么什么是啟發(fā)式搜索珍手？啟發(fā)式搜索和盲目搜索的區(qū)別是什么？
讀者可以想象一下這個場景辞做，我以前上學的時候為了趕時間喜歡騎單車去教室琳要，下課之后我到停車場的時候完全記不住我的單車究竟放在哪里了，這個時候我只能一輛一輛隨緣的"盲目"搜索秤茅。
如果我單車上有一個信號發(fā)射器稚补，我可以知道單車距離我還有多少米，那么這個時候我只需要向各個方向嘗試走幾步框喳，然后往距離縮減的方向前進就行了课幕，這就是啟發(fā)式。
估值函數(shù)其實就是這個告訴我單車離我現(xiàn)在多遠的一個東西五垮，當然乍惊，實際情況下我們肯定無法得到一個準確的“距離“，所以這個才叫“估值“函數(shù)拼余，值是一個估計值污桦。
A算法之所以效率高是因為它是啟發(fā)式的搜索算法，因此匙监，A算法的執(zhí)行效率高低在非常大的程度上是依賴于估值函數(shù)的凡橱，估值函數(shù)構造的越準確，則A*搜索的時間越短亭姥。
估值函數(shù)的計算
之前偽代碼的時候我們出現(xiàn)了幾個神奇的變量f稼钩，g還有h，這些都是每個節(jié)點的屬性达罗，現(xiàn)在我們來介紹一下它們坝撑。
g: 從起始節(jié)點到當前節(jié)點的代價。
h: 從當前節(jié)點到目標節(jié)點的"估計代價"
f=g+h: f是對經(jīng)過當前節(jié)點的這條路徑的代價的一個最好的估計值粮揉，f的值越小巡李，就認為這個經(jīng)過這個節(jié)點的路徑越好。
實踐(Javascript)
(如果有時間再補這一部分吧扶认，還有A*的解釋想畫幾個示意圖)
