一、A*搜尋算法

經典算法研究系列：一、A*搜尋算法              

作者：July、二零一一年一月

----------------------------------

部落客說明：

1、本經典算法研究系列，此系列文章寫的不夠好之處，還望見諒。

2、本經典算法研究系列，系我參考資料，一篇一篇原創所作，轉載必須注明作者本人July及出處。

3、本經典算法研究系列，精益求精，不斷優化，永久更新，永久勘誤。

歡迎，各位，與我一同學習探讨，交流研究。

有誤之處，不吝指正。

-------------------------------------------

引言

    1968年，的一篇論文，“P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100-107, 1968”。從此，一種精巧、高效的算法------A*算法橫空出世了，并在相關領域得到了廣泛的應用。

啟發式搜尋算法

    要了解A*搜尋算法，還得從啟發式搜尋算法開始談起。

    所謂啟發式搜尋，就在于目前搜尋結點往下選擇下一步結點時，可以通過一個啟發函數來進行選擇，選擇代價最少的結點作為下一步搜尋結點而跳轉其上（遇到有一個以上代價最少的結點，不妨選距離目前搜尋點最近一次展開的搜尋點進行下一步搜尋）。

    DFS和BFS在展開子結點時均屬于盲目型搜尋，也就是說，它不會選擇哪個結點在下一次搜尋中更優而去跳轉到該結點進行下一步的搜尋。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，隻能适用于問題規模不大的搜尋問題中。

    而與DFS,BFS不同的是，一個經過仔細設計的啟發函數，往往在很快的時間内就可得到一個搜尋問題的最優解，對于NP問題，亦可在多項式時間内得到一個較優解。是的，關鍵就是如何設計這個啟發函數。

A*搜尋算法

    A*搜尋算法，俗稱A星算法，作為啟發式搜尋算法中的一種，這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用于遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。該算法像Dijkstra算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜尋。

    A*算法最為核心的部分，就在于它的一個估值函數的設計上：

        f(n)=g(n)+h(n)

    其中f(n)是每個可能試探點的估值，它有兩部分組成：

    一部分，為g(n)，它表示從起始搜尋點到目前點的代價（通常用某結點在搜尋樹中的深度來表示）。

    另一部分，即h(n)，它表示啟發式搜尋中最為重要的一部分，即目前結點到目标結點的估值，

    h(n)設計的好壞，直接影響着具有此種啟發式函數的啟發式算法的是否能稱為A*算法。

   一種具有f(n)=g(n)+h(n)政策的啟發式算法能成為A*算法的充分條件是：

      1、搜尋樹上存在着從起始點到終了點的最優路徑。

      2、問題域是有限的。

      3、所有結點的子結點的搜尋代價值>0。

      4、h(n)=<h*(n) （h*(n)為實際問題的代價值）。

    當此四個條件都滿足時，一個具有f(n)=g(n)+h(n)政策的啟發式算法能成為A*算法，并一定能找到最優解。

    對于一個搜尋問題，顯然，條件1,2,3都是很容易滿足的，而條件4： h(n)<=h*(n)是需要精心設計的，由于h*(n)顯然是無法知道的，是以，一個滿足條件4的啟發政策h(n)就來的難能可貴了。

    不過，對于圖的最優路徑搜尋和八數位問題，有些相關政策h(n)不僅很好了解，而且已經在理論上證明是滿足條件4的，進而為這個算法的推廣起到了決定性的作用。

    且h(n)距離h*(n)的呈度不能過大，否則h(n)就沒有過強的區分能力，算法效率并不會很高。對一個好的h(n)的評價是：h(n)在h*(n)的下界之下，并且盡量接近h*(n)。  

A*搜尋算法的實作 

      先舉一個小小的例子：即求V0->V5的路徑，V0->V5的過程中，可以經由V1，V2，V3，V4各點達到目的點V5。下面的問題，即是求此起始頂點V0->途徑任意頂點V1、V2、V3、V4->目标頂點V5的最短路徑。

//是的，圖檔是引用rickone 的。

           通過上圖，我們可以看出：：A*算法最為核心的過程，就在每次選擇下一個目前搜尋點時，是從所有已探知的但未搜尋過點中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結點進行展開。

      而所有“已探知的但未搜尋過點”可以通過一個按f值升序的隊列(即優先隊列)進行排列。

      這樣，在整體的搜尋過程中，隻要按照類似廣度優先的算法架構，從優先隊列中彈出隊首元素（f值），對其可能子結點計算g、h和f值，直到優先隊列為空(無解)或找到終止點為止。

      A*算法與廣度、深度優先和Dijkstra 算法的聯系就在于：當g(n)=0時，該算法類似于DFS，當h(n)=0時，該算法類似于BFS。且同時，如果h(n)為0，隻需求出g(n)，即求出起點到任意頂點n的最短路徑，則轉化為單源最短路徑問題，即Dijkstra算法。這一點，可以通過上面的A*搜尋樹的具體過程中将h(n)設為0或将g(n)設為0而得到。 

A*算法流程：

    首先将起始結點S放入OPEN表，CLOSE表置空，算法開始時：

      1、如果OPEN表不為空，從表頭取一個結點n，如果為空算法失敗。

      2、n是目标解嗎？是，找到一個解（繼續尋找，或終止算法）。

      3、将n的所有後繼結點展開，就是從n可以直接關聯的結點（子結點），如果不在CLOSE表中，就将它們放入OPEN表，并把S放入CLOSE表，同時計算每一個後繼結點的估價值f(n)，将OPEN表按f(x)排序，最小的放在表頭，重複算法，回到1。

//OPEN-->CLOSE，起點-->任意頂點g(n)-->目标頂點h(n)

closedset := the empty set                 //已經被估算的節點集合  

    openset := set containing the initial node //将要被估算的節點集合

    g_score[start] := 0                        //g(n)

    h_score[start] := heuristic_estimate_of_distance(start, goal)    //h(n)

    f_score[start] := h_score[start]    

    while openset is not empty    //若OPEN表不為空

        x := the node in openset having the lowest f_score[] value //x為OPEN表中最小的

        if x = goal                                               //如果x是一個解

            return reconstruct_path(came_from,goal)             //

        remove x from openset

        add x to closedset                            //x放入

CLSOE表

        for each y in neighbor_nodes(x)

            if y in closedset

                continue

            tentative_g_score := g_score[x] + dist_between(x,y)

            if y not in openset

                add y to openset

                tentative_is_better := true

            else if tentative_g_score < g_score[y]

            else

                tentative_is_better := false

            if tentative_is_better = true

                came_from[y] := x

                g_score[y] := tentative_g_score

                h_score[y] := heuristic_estimate_of_distance(y, goal)  //x-->y-->goal

                f_score[y] := g_score[y] + h_score[y]

    return failure

function reconstruct_path(came_from,current_node)

    if came_from[current_node] is set

        p = reconstruct_path(came_from,came_from[current_node])

        return (p + current_node)

    else

        return the empty path 

     與結點寫在一起的數值表示那個結點的價值f(n)，當OPEN表為空時CLOSE表中将求得從V0到其它所有結點的最短路徑。

     考慮到算法性能，外循環中每次從OPEN表取一個元素，共取了n次（共n個結點），每次展開一個結點的後續結點時，需O(n)次，同時再對OPEN表做一次排序，OPEN表大小是O(n)量級的，若用快排就是O(nlogn)，乘以外循環總的複雜度是O(n^2 * logn)，

     如果每次不是對OPEN表進行排序，因為總是不斷地有新的結點添加進來，是以不用進行排序，而是每次從OPEN表中求一個最小的，那隻需要O(n)的複雜度，是以總的複雜度為O(n*n)，這相當于Dijkstra算法。

 本文完。

     July、二零一一年二月十日更新。

------------------------------------------------