人工智慧/搜尋/啟發式搜尋/最佳優先搜尋
本文介紹了最佳優先搜尋的一般形式。有很多具體的演算法遵循最佳優先搜尋的基本形式，但使用更復雜的評估函式。A* 是最佳優先搜尋的一個流行變種。本頁面不會專門討論 A* 或其他變種，儘管本文包含的資訊與這些搜尋演算法相關。
最佳優先搜尋，在最一般形式上，是一種簡單的啟發式搜尋演算法。“啟發式”在這裡指的是一種通用的問題解決規則或一組規則，這些規則不能保證最佳解決方案，甚至不能保證任何解決方案，但它可以作為問題解決的有用指南。最佳優先搜尋是一種基於圖的搜尋演算法（Dechter and Pearl, 1985），這意味著搜尋空間可以表示為一系列由路徑連線的節點。
“最佳優先”這個名字指的是首先探索“得分”最高的節點的方法。一個評估函式用於為每個候選節點分配一個分數。該演算法維護兩個列表，一個包含待探索的候選節點列表（OPEN），另一個包含已訪問節點列表（CLOSED）。由於每個已訪問節點的所有未訪問後繼節點都包含在 OPEN 列表中，因此該演算法不限於僅探索最近訪問節點的後繼節點。換句話說，該演算法總是選擇所有已繪製的未訪問節點中得分最高的節點，而不是僅限於一小部分節點，例如直接鄰居。其他搜尋策略，例如深度優先和廣度優先，具有此限制。這種策略的優勢在於，如果演算法到達一個死衚衕節點，它將繼續嘗試其他節點（Pearl, 1984）。
最佳優先搜尋，在最基本的形式上，包含以下演算法（改編自 Pearl, 1984）
第一步是定義一個 OPEN 列表，該列表僅包含一個節點，即起始節點。第二步是檢查 OPEN 是否為空。如果為空，則演算法返回失敗並退出。第三步是從 OPEN 中移除得分最高的節點 n，並將其放到 CLOSED 中。第四步“擴充套件”節點 n，其中擴充套件是識別 n 的後繼節點。第五步然後檢查每個後繼節點，以檢視其中一個是否為目標節點。如果任何後繼節點是目標節點，則演算法返回成功和解決方案，該解決方案包括從目標節點到起始節點的反向追蹤路徑。否則，演算法將繼續進行第六步。對於每個後繼節點，演算法將評估函式 f 應用於該節點，然後檢查該節點是否已在 OPEN 或 CLOSED 中。如果該節點不在任何一個列表中，則將其新增到 OPEN 中。最後，第七步透過將演算法傳送回第二步來建立迴圈結構。只有當演算法在第五步返回成功或在第二步返回失敗時，才會打破此迴圈。
該演算法在此用偽程式碼表示
- 1. 定義一個列表 OPEN，該列表僅包含一個節點，即起始節點 s。
- 2. 如果該列表為空，則返回失敗。
- 3. 從列表中移除得分最高的節點 n（f 最小的節點），並將其移動到列表 CLOSED 中。
- 4. 擴充套件節點 n。
- 5. 如果 n 的任何後繼節點是目標節點，則返回成功和解決方案（透過從目標節點到 s 追蹤路徑）。
- 6. 對於每個後繼節點
- a) 將評估函式 f 應用於該節點。
- b) 如果該節點不在任何一個列表中，則將其新增到 OPEN 中。
- 7. 透過將演算法傳送回第二步來建立迴圈結構。
Pearl (2012?) 在 FOR 迴圈中添加了第三步，旨在防止已訪問節點的重新擴充套件。由於它並不常見於所有最佳優先搜尋演算法，因此上面省略了這一步。
用於確定節點得分的特定評估函式在上述演算法中沒有明確定義，因為實際使用的函式取決於程式設計師的決定，並且可能會根據搜尋空間的特殊情況而有所不同。雖然評估函式可以在很大程度上決定搜尋的有效性和效率（Pearl, 1984），但為了理解搜尋演算法，我們不需要關注該函式的具體細節。
最佳優先搜尋及其更先進的變體已應用於遊戲和網路爬蟲等應用。在網路爬蟲中，每個網頁都被視為一個節點，頁面上的所有超連結都被視為未訪問的後繼節點。使用最佳優先搜尋的爬蟲通常使用一個評估函式，該函式根據連結的父頁面內容與搜尋查詢的匹配程度來對連結進行優先順序排序（Menczer, Pant, Ruiz, and Srinivasan, 2001）。在遊戲中，最佳優先搜尋可以用作遊戲角色的路徑查詢演算法。例如，它可以被敵方代理使用來查詢遊戲世界中玩家的位置。有些遊戲將地形劃分為“方格”，這些方格可以被阻塞或不被阻塞。在這種情況下，搜尋演算法將每個方格視為一個節點，將相鄰的未阻塞方格視為後繼節點，並將目標節點視為目標方格（Koenig, 2004）。
- Dechter, R. & Pearl, J. (1985). Generalized Best-First Search Strategies and the Optimality of A*. Journal of the Association for Computing Machinery, 32, 505-536.
- Menczer, F., Pant, G., Ruiz, M.E. & Srinivasan, P. (2001). Evaluating Topic-Driven Web Crawlers. Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 241-249). New York: Association for Computing Machinery.
- Koenig, S. (2004). A Comparison of Fast Search Methods for Real-Time Situated Agents. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2 (pp. 862-871). Washington, DC: IEEE Computer Society.
- Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, MA: Addison-Wesley.