Best-First Search

定义 Definition

Best-first search（最佳优先搜索）：一种启发式搜索策略，在搜索过程中总是优先扩展“当前看起来最有希望”的节点；通常通过一个优先队列按某个评估函数（如启发函数 h(n) 或代价函数等）来选择下一个要扩展的节点。常见变体包括 Greedy Best-First Search（贪心最佳优先搜索） 与 A* Search（A星搜索）（A* 常被视为最佳优先搜索框架下的特例）。

发音 Pronunciation (IPA)

/ˌbɛst fɝːst sɝːtʃ/

例句 Examples

We used best-first search to find a path through the maze.
我们用最佳优先搜索在迷宫中找到一条路径。

In many AI planning problems, best-first search explores states according to a heuristic score, often reducing the number of expanded nodes compared with uninformed methods.
在许多人工智能规划问题中，最佳优先搜索会按启发式评分来探索状态，往往比无信息搜索方法扩展更少的节点。

词源 Etymology

该术语由 best（最优/最好）+ first（优先）+ search（搜索） 组合而成，字面意思是“先搜索最好的（最有希望的）”。它在人工智能与图搜索语境中逐渐固定为一种“按评价函数排序并优先扩展”的搜索家族名称。

相关词 Related Words

• A*
• Heuristic
• Priority Queue
• Greedy
• Uniform-Cost Search
• Breadth-First Search
• Depth-First Search
• Graph Search
• Node
• Pathfinding

文学与经典著作中的用例 Literary Works

• 《Artificial Intelligence: A Modern Approach》（Stuart Russell & Peter Norvig）——在“启发式搜索/最佳优先搜索”等章节中系统讨论 best-first search 及其变体（如贪心最佳优先与 A*）。
• 《Paradigms of Artificial Intelligence Programming》（Peter Norvig）——涉及用启发式与搜索策略（包括最佳优先思想）构建 AI 程序的讨论与示例。