A*（A-Star)算法是一種靜態路網中求解最短路最有效的方法。
　　公式表示為： f(n)=g(n)+h(n),
　　其中f(n) 是節點n從初始點到目標點的估價函數，
　　g(n) 是在狀態空間中從初始節點到n節點的實際代價，
　　h(n)是從n到目標節點最佳路徑的估計代價。
　　保證找到最短路徑（最優解的）條件，關鍵在于估價函數h(n)的選?。?br />　　估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
　　如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
　　估價值與實際值越接近，估價函數取得就越好。
　　例如對于幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優于Dijstra算法的毫無無方向的向四周搜索。
　　conditions of heuristic
　　Optimistic (must be less than or equal to the real cost)
　　As close to the real cost as possible
　　主要搜索過程：
　　創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
　　遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
　　While(OPEN!=NULL)
　　{
　　從OPEN表中取估價值f最小的節點n;
　　if(n節點==目標節點) break;
　　else
　　{
　　if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
　　if( X的估價值小于OPEN表的估價值 )
　　更新OPEN表中的估價值; //取最小路徑的估價值
　　if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
　　if( X的估價值小于CLOSE表的估價值 )
　　更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
　　if(X not in both)
　　求X的估價值;
　　并將X插入OPEN表中; //還沒有排序
　　}
　　將n節點插入CLOSE表中;
　　按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
　　啟發式搜索其實有很多的算法，比如：局部擇優搜索法、最好優先搜索法等等。當然A*也是。這些算法都使用了啟發函數，但在具體的選取最佳搜索節點時的策略不同。象局
　　部擇優搜索法，就是在搜索的過程中選取“最佳節點”后舍棄其他的兄弟節點，父親節點，而一直得搜索下去。這種搜索的結果很明顯，由于舍棄了其他的節點，可能也把最好的
　　節點都舍棄了，因為求解的最佳節點只是在該階段的最佳并不一定是全局的最佳。最好優先就聰明多了，他在搜索時，便沒有舍棄節點（除非該節點是死節點），在每一步的估價
　　中都把當前的節點和以前的節點的估價值比較得到一個“最佳的節點”。這樣可以有效的防止“最佳節點”的丟失。那么A*算法又是一種什么樣的算法呢？其實A*算法也是一種最
　　好優先的算法。只不過要加上一些約束條件罷了。由于在一些問題求解時，我們希望能夠求解出狀態空間搜索的最短路徑，也就是用最快的方法求解問題，A*就是干這種事情的！
　　我們先下個定義，如果一個估價函數可以找出最短的路徑，我們稱之為可采納性。A*算法是一個可采納的最好優先算法。A*算法的估價函數可表示為：
　　f'(n) = g'(n) + h'(n)
　　這里，f'(n)是估價函數，g'(n)是起點到終點的最短路徑值，h'(n)是n到目標的最斷路經的啟發值。由于這個f'(n)其實是無法預先知道的，所以我們用前面的估價函數f(n)做
　　近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多數情況下都是滿足的，可以不用考慮），h(n)代替h'(n)，但h(n)<=h'(n)才可（這一點特別的重要）。可以證明應用這樣的估價
　　函數是可以找到最短路徑的，也就是可采納的。我們說應用這種估價函數的最好優先算法就是A*算法。哈。你懂了嗎？肯定沒懂。接著看。
　　舉一個例子，其實廣度優先算法就是A*算法的特例。其中g(n)是節點所在的層數，h(n)=0，這種h(n)肯定小于h'(n)，所以由前述可知廣度優先算法是一種可采納的。實際也是
　　。當然它是一種最臭的A*算法。
　　再說一個問題，就是有關h(n)啟發函數的信息性。h(n)的信息性通俗點說其實就是在估計一個節點的值時的約束條件，如果信息越多或約束條件越多則排除的節點就越多，估價函
　　數越好或說這個算法越好。這就是為什么廣度優先算法的那么臭的原因了，誰叫它的h(n)=0，一點啟發信息都沒有。但在游戲開發中由于實時性的問題，h(n)的信息越多，它的計
　　算量就越大，耗費的時間就越多。就應該適當的減小h(n)的信息，即減小約束條件。但算法的準確性就差了，這里就有一個平衡的問題。
　　}
今天做了一個游戲模擬題，看著題牛X的我問pip說：能不能用A*，誰知道他更猛。500個點不值得用。。。。。。無語，結果我的處女A*無疾而終，只好寫了個普搜水過去了。。。。。，搞了一個pip推薦的dp無語還是腦殘，居然那么就才想到。。。。。。。。。