經(jīng)典算法研究系列：一、A*搜索算法  

啟發(fā)式搜索算法
    要理解A*搜尋算法，還得從啟發(fā)式搜索算法開始談起。
    所謂啟發(fā)式搜索，就在于當(dāng)前搜索結(jié)點往下選擇下一步結(jié)點時，可以通過一個啟發(fā)函數(shù)來進(jìn)行選擇，選擇代價最少的結(jié)點作為下一步搜索結(jié)點而跳轉(zhuǎn)其上（遇到有一個以上代價最少的結(jié)點，不妨選距離當(dāng)前搜索點最近一次展開的搜索點進(jìn)行下一步搜索）。

    DFS和BFS在展開子結(jié)點時均屬于盲目型搜索，也就是說，它不會選擇哪個結(jié)點在下一次搜索中更優(yōu)而去跳轉(zhuǎn)到該結(jié)點進(jìn)行下一步的搜索。在運氣不好的情形中，均需要試探完整個解集空間, 顯然，只能適用于問題規(guī)模不大的搜索問題中。

    而與DFS,BFS不同的是，一個經(jīng)過仔細(xì)設(shè)計的啟發(fā)函數(shù)，往往在很快的時間內(nèi)就可得到一個搜索問題的最優(yōu)解，對于NP問題，亦可在多項式時間內(nèi)得到一個較優(yōu)解。是的，關(guān)鍵就是如何設(shè)計這個啟發(fā)函數(shù)。

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

    A*算法最為核心的部分，就在于它的一個估值函數(shù)的設(shè)計上：
        f(n)=g(n)+h(n)

    其中f(n)是每個可能試探點的估值，它有兩部分組成：
    一部分，為g(n)，它表示從起始搜索點到當(dāng)前點的代價（通常用某結(jié)點在搜索樹中的深度來表示）。
    另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當(dāng)前結(jié)點到目標(biāo)結(jié)點的估值，
    h(n)設(shè)計的好壞，直接影響著具有此種啟發(fā)式函數(shù)的啟發(fā)式算法的是否能稱為A*算法。

   一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：
      1、搜索樹上存在著從起始點到終了點的最優(yōu)路徑。
      2、問題域是有限的。
      3、所有結(jié)點的子結(jié)點的搜索代價值>0。
      4、h(n)=<h*(n) （h*(n)為實際問題的代價值）。

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

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

    不過，對于圖的最優(yōu)路徑搜索和八數(shù)碼問題，有些相關(guān)策略h(n)不僅很好理解，而且已經(jīng)在理論上證明是滿足條件4的，從而為這個算法的推廣起到了決定性的作用。

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

A*搜尋算法的實現(xiàn) 
      先舉一個小小的例子：即求V0->V5的路徑，V0->V5的過程中，可以經(jīng)由V1，V2，V3，V4各點達(dá)到目的點V5。下面的問題，即是求此起始頂點V0->途徑任意頂點V1、V2、V3、V4->目標(biāo)頂點V5的最短路徑。

//圖片是引用rickone 的。上圖中，說白了，無非就是：一個隊列，open 往close 插入元素。
           通過上圖，我們可以看出：：A*算法最為核心的過程，就在每次選擇下一個當(dāng)前搜索點時，是從所有已探知的但未搜索過點中(可能是不同層，亦可不在同一條支路上)，選取f值最小的結(jié)點進(jìn)行展開。
      而所有“已探知的但未搜索過點”可以通過一個按f值升序的隊列(即優(yōu)先隊列)進(jìn)行排列。
      這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊列中彈出隊首元素（f值），對其可能子結(jié)點計算g、h和f值，直到優(yōu)先隊列為空(無解)或找到終止點為止。

      A*算法與廣度、深度優(yōu)先和Dijkstra 算法的聯(lián)系就在于：當(dāng)g(n)=0時，該算法類似于DFS，當(dāng)h(n)=0時，該算法類似于BFS。且同時，如果h(n)為0，只需求出g(n)，即求出起點到任意頂點n的最短路徑，則轉(zhuǎn)化為單源最短路徑問題，即Dijkstra算法。這一點，可以通過上面的A*搜索樹的具體過程中將h(n)設(shè)為0或?qū)(n)設(shè)為0而得到。 

A*算法流程：
    首先將起始結(jié)點S放入OPEN表，CLOSE表置空，算法開始時：
      1、如果OPEN表不為空，從表頭取一個結(jié)點n，如果為空算法失敗。
      2、n是目標(biāo)解嗎？是，找到一個解（繼續(xù)尋找，或終止算法）。
      3、將n的所有后繼結(jié)點展開，就是從n可以直接關(guān)聯(lián)的結(jié)點（子結(jié)點），如果不在CLOSE表中，就將它們放入OPEN表，并把S放入CLOSE表，同時計算每一個后繼結(jié)點的估價值f(n)，將OPEN表按f(x)排序，最小的放在表頭，重復(fù)算法，回到1。

//OPEN-->CLOSE，起點-->任意頂點g(n)-->目標(biāo)頂點h(n)
closedset := the empty set                 //已經(jīng)被估算的節(jié)點集合   
    openset := set containing the initial node //將要被估算的節(jié)點集合
    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]
                tentative_is_better := true
            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 

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

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

     如果每次不是對OPEN表進(jìn)行排序，因為總是不斷地有新的結(jié)點添加進(jìn)來，所以不用進(jìn)行排序，而是每次從OPEN表中求一個最小的，那只需要O(n)的復(fù)雜度，所以總的復(fù)雜度為O(n*n)，這相當(dāng)于Dijkstra算法。

 本文完。
     July、二零一一年二月十日更新。
------------------------------------------------

后續(xù)：July、二零一一年三月一日更新。
簡述A*最短路徑算法的方法：
   目標(biāo)：從當(dāng)前位置A到目標(biāo)位置B找到一條最短的行走路徑。

   方法：從A點開始，遍歷所有的可走路徑，記錄到一個結(jié)構(gòu)中，記錄內(nèi)容為（位置點，最小步數(shù)）
         當(dāng)任何第二次走到一個點的時候，判斷最小步驟是否小于記錄的內(nèi)容，如果是，則更新掉原最小步數(shù)，一直到所有的路徑點都不能繼續(xù)都了為止，最終那個點被標(biāo)注的最小步數(shù)既是最短路徑，
         而反向找跟它相連的步數(shù)相繼少一個值的點連起來就形成了最短路徑，當(dāng)多個點相同，則任意取一條即可。

   總結(jié)：
   A*算法實際是個窮舉算法，也與課本上教的最短路徑算法類似。課本上教的是兩頭往中間走，也是所有路徑都走一次，每一個點標(biāo)注最短值。