原理
A* （A-Star)算法是一種靜態路網中求解最短路徑最有效的直接搜尋方法，也是許多其他問題的常用啟發式算法。注意——是最有效的 直接搜尋算法，之後湧現了很多預處理算法（如ALT，CH，HL等等），線上查詢效率是A*算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中， f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價，
h(n) 是從狀態n到目標狀態的最佳路徑的估計代價。
（對於路徑搜尋問題，狀態就是圖中的節點，代價就是距離）
h(n)的選取
保證找到最短路徑（最優解的）條件，關鍵在於估價函式f(n)的選取（或者說h(n)的選取）。
我們以d(n)表達狀態n到目標狀態的距離，那么h(n)的選取大致有如下三種情況：
如果h(n)< d(n)到目標狀態的實際距離，這種情況下，搜尋的點數多，搜尋範圍大，效率低。但能得到最優解。
如果h(n)=d(n)，即距離估計h(n)等於最短距離，那么搜尋將嚴格沿著最短路徑進行， 此時的搜尋效率是最高的。
如果 h(n)>d(n)，搜尋的點數少，搜尋範圍小，效率高，但不能保證得到最優解。
1.如果h(n)< d(n)到目標狀態的實際距離，這種情況下，搜尋的點數多，搜尋範圍大，效率低。但能得到最優解。
2.如果h(n)=d(n)，即距離估計h(n)等於最短距離，那么搜尋將嚴格沿著最短路徑進行， 此時的搜尋效率是最高的。
3.如果 h(n)>d(n)，搜尋的點數少，搜尋範圍小，效率高，但不能保證得到最優解。
簡單案例
參見參考資料中的“A*算法入門” 。
另外，A*同樣可以用於其他搜尋問題，只需要對應狀態和狀態的距離即可。
算法分類
該算法在最短路徑搜尋算法中分類為：
直接搜尋算法：直接在實際地圖上進行搜尋，不經過任何預處理；
啟發式算法：通過啟發函式引導算法的搜尋方向；
靜態圖搜尋算法：被搜尋的圖的權值不隨時間變化（後被證明同樣可以適用於動態圖的搜尋 ）。
實際運用
距離估計與實際值越接近，估價函式取得就越好
例如對於幾何路網來說，可以取兩節點間曼哈頓距離做為距離估計，即f=g(n) + (abs(dx - nx) + abs(dy - ny))；這樣估價函式f(n)在g(n)一定的情況下，會或多或少的受距離估計值h(n)的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜尋向終點的方向進行。明顯優於Dijkstra算法的毫無方向的向四周搜尋。
算法實現（路徑搜尋）
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
算起點的h(s);
將起點放入OPEN表;
保存路徑，即從終點開始，每個節點沿著父節點移動直至起點，這就是你的路徑；
用C語言實現A*最短路徑搜尋算法 ，作者 Tittup frog(跳跳蛙)。
其它算法
啟發式搜尋其實有很多的算法
比如：局部擇優搜尋法、最好優先搜尋法等等，當然A*也是。這些算法都使用了啟發函式，但在具體的選取最佳搜尋節點時的策略不同。像局部擇優搜尋法，就是在搜尋的過程中選取“最佳節點”後捨棄其他的兄弟節點、父親節點，而一直得搜尋下去。這種搜尋的結果很明顯，由於捨棄了其他的節點，可能也把最好的節點都捨棄了，因為求解的最佳節點只是在該階段的最佳並不一定是全局的最佳。最好優先就聰明多了，它在搜尋時，並沒有捨棄節點（除非該節點是死節點），在每一步的估價中都把當前的節點和以前的節點的f(n)比較得到一個“最佳的節點”，這樣可以有效的防止“最佳節點”的丟失。那么A*算法又是一種什麼樣的算法呢？
好處
其實A*算法也是一種最好優先的算法
只不過要加上一些約束條件罷了。由於在一些問題求解時，我們希望能夠求解出狀態空間搜尋的最短路徑，也就是用最快的方法求解問題，A*就是幹這種事情的！
我們先下個定義，如果一個估價函式可以找出最短的路徑，我們稱之為可採納性。A*算法是一個可採納的最好優先算法。A*算法的估價函式可表示為：
f'(n) = g'(n) + h'(n)
這裡，f'(n)是估價函式，g'(n)是起點到節點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)的信息，即減小約束條件。但算法的準確性就差了，這裡就有一個平衡的問題。
