人工智慧/搜尋/啟發式搜尋/A*搜尋
搜尋技術是通用的問題解決方法。當有一個公式化的搜尋問題時，一組狀態，一組操作，一個初始狀態和一個目標準則，我們可以使用搜索技術來解決問題（Pearl & Korf，1987）。Cawsey（1998）用簡單的話解釋了搜尋演算法：假設你試圖在一個有很多單行道的城鎮中找到自己的路。從你的初始狀態（A）到目標目的地（B）有許多路線，但你不知道要走哪一條。在現實生活中，你可以嘗試你喜歡的任何路線，儘管這可能是一個困難的過程。在整個過程中，可能會有很多不便之處：一旦你通過了一條街道，你可能無法返回，因為它是一條單行道，或者你可能被困在一個公園裡。這種簡化的尋找地點的思路表明，我們實際上可以在這樣的例子中映射出所有可能的路線；即使很累，你最終也會找到一條路。在上面介紹的小規模搜尋問題中，簡單的搜尋技術足以進行系統搜尋。但是，有時我們需要系統地搜尋這樣的路線，例如，在一個更復雜的圖上。我們該怎麼做？搜尋演算法很適合解決這類問題。問題可能是一個物理問題，例如從 A 步行或開車到 B；或者它可能是抽象的，例如定理中的一組步驟，這將允許我們從一組事實中證明。
A*搜尋演算法
啟發式搜尋利用了這樣一個事實，即大多數問題空間提供了一些資訊，可以區分不同狀態，這些資訊可以根據狀態導致目標的可能性來區分它們。這種資訊稱為啟發式評估函式（Pearl & Korf，1987）。換句話說，啟發式搜尋的目標是在尋找目標時減少搜尋的節點數量（Kopec & Marsland，2001）。
最廣泛使用的最佳優先搜尋形式稱為 A*，發音為 A 星。它是一種啟發式搜尋方法，用於最小化給定問題中的搜尋成本（Bolc & Cytowski，1992）。它旨在找到從給定的初始節點到目標節點的最低成本路徑。它是最佳優先搜尋演算法的擴充套件形式。最佳優先搜尋演算法也試圖找到一種解決方案來最小化搜尋路徑的總成本。但是，與最佳優先搜尋不同的是，A*還考慮了從開始點的成本，而不僅僅是先前訪問節點的區域性成本。最佳優先搜尋在任何預先確定的問題空間中找到目標狀態。但是，它不能保證它會選擇通往目標的最佳路徑（Pearl & Korf，1987）。例如，如果有兩個選項可以選擇，其中一個選項距離起點很遠，但對到達目標的距離估計略短，而另一個選項非常靠近起點，但對到達目標的距離估計略長，最佳優先搜尋將總是選擇擴充套件下一個距離估計最短的狀態。A*演算法修正了最佳優先搜尋的這個缺點（Pearl & Korf，1987）。
簡而言之，A*演算法搜尋從起點到找到最短路徑或最便宜成本到達目標的所有可能的路線。這裡的最短路徑、最便宜成本等術語指的是一個通用概念。它可能是根據問題而定的其他術語。例如，在地圖問題中，成本被替換為距離（Cawsey，1998）。A*可以減少搜尋空間中所有可能路徑的必要性，並導致更快的解決方案。A*透過組合 g(n) 和 h(n) 來評估節點。在討論 A* 時使用的標準術語中
f(n)= g(n)+h(n)
該方程的目的是在給定問題中獲得最低的 f 分數。n 是直到最終節點遍歷的節點數，
f(n) 是總搜尋成本， g(n) 是從初始起點到節點 n 的路徑的實際最低成本（最短距離）， h(n) 是從節點 n 到目標節點的最便宜成本（距離）的估計值。該方程的這一部分也稱為啟發式函式/估計。
在每個節點上，選擇最低的 f 值作為要擴充套件的下一步，直到選擇目標節點並將其用於擴充套件。（Pearl & Korf，1987）。只要啟發式函式滿足某些條件，A*搜尋既是完整的又是最優的（Russell & Norvig，2003）。
可接受性。保證找到最優解（如果有）的策略稱為可接受的。為了使啟發式方法可接受，需要滿足幾個條件。如果使用樹搜尋，A*的最優性分析起來很簡單（Russell & Norvig，2003）。在這種情況下，如果 h(n) 是可接受的啟發式方法，那麼 A* 是最優的。
h*(n) = 從 n 到目標的實際最小成本。
如果對所有狀態 n，h(n) ≤ h*(n)，則啟發式方法 h 是可接受的。
收斂性。如果搜尋策略承諾找到路徑、解圖或有關它們是否存在的資訊，則該策略是收斂的（Bolc & Cytowski，1992）。如果有解，A* 將始終找到它。對於任何具有非負成本函式的網路（有限或無限），A* 搜尋演算法的收斂性屬性都得到滿足。對於具有非負成本函式的有限網路，如果 A* 在找到解後終止，或者如果不存在解，則它就是收斂的。迴圈路徑中的路徑數量是有限的。先前檢查過的節點，例如 w，僅當搜尋找到比先前更小的成本時才會被重新訪問。成本函式是非負的；因此，一條邊只能檢查一次。因此，A* 是收斂的（Bolc & Cytowski，1992）。
A*搜尋演算法的問題
根據 Pearl & Korf（1987），A* 和任何最佳優先搜尋的主要缺點是其記憶體需求。由於必須儲存整個開放路徑列表，因此 A* 在實踐中是空間受限的，並且與廣度優先搜尋一樣實用。對於大型搜尋空間，A* 會耗盡記憶體。幸運的是，透過使用迭代加深 A*（IDA*）可以節省大量記憶體。
（匿名，2006）
create the open list of nodes, initially containing only our starting node
create the closed list of nodes, initially empty
while (we have not reached our goal)
{
consider the best node in the open list (the node with the lowest f value)
if (this node is the goal)
{
then we're done
}
else
{
move the current node to the closed list and consider all of its neighbors
for (each neighbor)
{
if (this neighbor is in the closed list and our current g value is lower)
{
update the neighbor with the new, lower, g value
change the neighbor's parent to our current node
}
else if (this neighbor is in the open list and our current g value is lower)
{
update the neighbor with the new, lower, g value
change the neighbor's parent to our current node
}
else this neighbor is not in either the open or closed list
{
add the neighbor to the open list and set its g value
}
}
}
}
A* 是最流行的尋路選擇，因為它相當靈活，可以在各種環境中使用，例如遊戲（8 數碼難題和尋路器）。
- A* 的變體
- 雙向搜尋
- 迭代加深
- 束搜尋
- 動態加權
- 頻寬搜尋
- 動態 A* 和終身規劃 A*
- http://www.policyalmanac.org/games/aStarTutorial.htm
- http://wiki.gamegardens.com/Path_Finding_Tutorial#A.2A_Examples
- intelligence.worldofcomputing.net/ai-search/a-star-algorithm.html
- 匿名，（2006）。尋路教程，（2008 年 10 月 14 日從 http://wiki.gamegardens.com/Path_Finding_Tutorial#Pseudo-code_A.2A 檢索）
- Bolc，L..，& Cytowski，J.，（1992）。人工智慧的搜尋方法。倫敦：學術出版社。
- Cawsey，A.（1998）。人工智慧的本質。新澤西州上鞍河：普倫蒂斯·霍爾
- Kopec, D. & Marsland, T.A. (2001). 搜尋。檢索於 2008 年 10 月 10 日，來自 http://www.cs.ualberta.ca/~tony/RecentPapers/Draft.5.2.pdf
- Pearl, J. & Korf, R. E.(1987). 搜尋技術。計算機科學年度評論, 451-467.
- Russell, S. J., & Norvig, P. (2003). 人工智慧：現代方法。新澤西州上鞍河：普倫蒂斯·霍爾