人工智能/搜索/启发式搜索/最佳优先搜索
本文介绍了最佳优先搜索的一般形式。有很多具体的算法遵循最佳优先搜索的基本形式，但使用更复杂的评估函数。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.