astar(啟發式搜尋算法)

啟發式搜尋算法

即A*算法，讀音為A-star。

啟發式搜尋就是在狀態空間中的搜尋，首先對每一個搜尋的位置進行評估，得到最好的位置，再從這個位置進行搜尋直到目標。這樣可以省略大量無謂的搜尋路徑，提高了效率。在啟發式搜尋中，對位置的估價是十分重要的。採用了不同的估價可以有不同的效果。

啟發中的估價是用估價函式表示的，如：f(n) = g(n) + h(n)

其中f(n) 是節點n的估價函式，g(n)是在狀態空間中從初始節點到n節點的實際代價，h(n)是從n到目標節點最佳路徑的估計代價。在這裡主要是h(n)體現了搜尋的啟發信息，因為g(n)是已知的。如果說詳細點，g(n)代表了搜尋的廣度的優先趨勢。但是當h(n) >> g(n)時，可以省略g(n)，而提高效率。