A*算法總結

A*是一種啟發式搜索，一種有序搜索，它之所以特殊完全是在它的估價函數上，如果我要求的是從初始結點到目的結點的一個最短路徑（或加權代價）的可行解， 那對于一個還不是目標結點的結點，我對它的評價就要從兩個方面評價：第一，離目標結點有多近，越近越好；第二，離起始結點有多遠，越近越好。記號 [a,b]是表示結點a到結點b的實際最短路徑代價。設起始結點為S，當前結點為n，目標結點為G，于是n的實際代價應該是f*(n)=g*(n)+h* (n)，其中g*(n)=[S,n],h*(n)=[n,G]，對于是g*(n)是比較容易得到的，在搜索的過程中我們可以按搜索的順序對它進行累積計 算，當然按BFS和DFS的不同，我們對它的估價g(n)可以滿足g(n)>=g*(n)，大多可以是相等的。但是對于h*(n)我們卻了解得非常 少，目標結點正是要搜索的目的，我們是不知道在哪，就更不知道從n到目標結點的路徑代價，但是或多或少我們還是可以估計的，記估價函數f(n)=g(n) +h(n)。

我們說如果在一般的圖搜索算法中應用了上面的估價函數對OPEN表進行排序的，就稱A算法。在A算法之上，如果加上一個條件，對于所有的結點x，都有h(x)<=h*(x)，那就稱為A*算法。如果取h(n)=0同樣是A*算法，這樣它就退化成了有序算法。

A*算法是否成功，也就是說是否在效率上勝過蠻力搜索算法，就在于h(n)的選取，它不能大于實際的h*(n)，要保守一點，但越接近h*(n)給我們的啟發性就越大，是一個難把握的東西。

過程:
1. 將開始節點放入開放列表(開始節點的F和G值都視為0);
2. 重復一下步驟:
i. 在開放列表中查找具有最小F值的節點,并把查找到的節點作為當前節點;
ii. 把當前節點從開放列表刪除, 加入到封閉列表;
iii. 對當前節點相鄰的每一個節點依次執行以下步驟:
1. 如果該相鄰節點不可通行或者該相鄰節點已經在封閉列表中,則什么操作也不執行,繼續檢驗下一個節點;
2. 如果該相鄰節點不在開放列表中,則將該節點添加到開放列表中, 并將該相鄰節點的父節點設為當前節點,同時保存該相鄰節點的G和F值;
3. 如果該相鄰節點在開放列表中, 則判斷若經由當前節點到達該相鄰節點的G值是否小于原來保存的G值,若小于,則將該相鄰節點的父節點設為當前節點,并重新設置該相鄰節點的G和F值.
iv. 循環結束條件:
當終點節點被加入到開放列表作為待檢驗節點時, 表示路徑被找到,此時應終止循環;
或者當開放列表為空,表明已無可以添加的新節點,而已檢驗的節點中沒有終點節點則意味著路徑無法被找到,此時也結束循環;
3. 從終點節點開始沿父節點遍歷, 并保存整個遍歷到的節點坐標,遍歷所得的節點就是最后得到的路徑;

搜索過程中設置兩個表：OPEN和CLOSED。OPEN表保存了所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。算法中有一步是根據估價函數重排OPEN表。這樣循環中的每一步只考慮OPEN表中狀態最好的節點。
Best_First_Search()
　　{
　　　　Open = [起始節點];
　　　　Closed = [];
　　　　while ( Open表非空 )
　　　　{
　　　　　　從Open中取得一個節點X, 并從OPEN表中刪除.
　　　　　　if (X是目標節點)
　　　　　　{
　　　　　　　　求得路徑PATH;
　　　　　　　　返回路徑PATH;
　　　　　　}
　　　　　　for (每一個X的子節點Y)
　　　　　　{
　　　　　　　　if( Y不在OPEN表和CLOSE表中 )
　　　　　　　　{
　　　　　　　　　　求Y的估價值;
　　　　　　　　　　并將Y插入OPEN表中;　//還沒有排序
　　　　　　　　}
　　　　　　　　else if( Y在OPEN表中 )
　　　　　　　　{
　　　　　　　　　　if( Y的估價值小于OPEN表的估價值 )
　　　　　　　　　　　　更新OPEN表中的估價值;
　　　　　　　　}
　　　　　　　　else //Y在CLOSE表中
　　　　　　　　{
　　　　　　　　　　if( Y的估價值小于CLOSE表的估價值 )
　　　　　　　　　　{
　　　　　　　　　　　　更新CLOSE表中的估價值;
　　　　　　　　　　　　從CLOSE表中移出節點, 并放入OPEN表中;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　將X節點插入CLOSE表中;
　　　　　　　　按照估價值將OPEN表中的節點排序;
　　　　　　}　//end for
　　　　}　//end while
　　}　//end func