最佳优先搜索

BFS 是一种搜索方法，而不仅仅是一种算法，因此有许多最佳优先 (BFS) 算法，例如贪婪 BFS、A* 和 B*。BFS 算法是知情搜索算法，与非知情搜索算法（如广度优先搜索、深度优先搜索等）相反，即 BFS 算法利用可以编码为所谓启发式函数的领域知识（这就是他们被告知的原因！）。

每个 BFS 算法都定义了一个所谓的评估函数 $f$以下形式的

对于所有节点$n \in V$（在哪里$V$是搜索空间的节点或状态的集合），其中

• $g(n)$是从（搜索的）开始节点到节点的成本$n$， 和

• $h(n)$（所谓启发式，即包含领域知识来解决搜索问题的方式）是对从$n$到目标节点。

取决于你如何定义$f$尤其是启发式函数$h$，你会得到不同的 BFS 算法。例如，A* 是一种 BFS 算法，其中$h$是一个可接受的启发式（即它永远不会高估目标节点的成本）。由于这个可接纳性属性，A* 可以保证找到全局最优解（即所有路径中从起始节点到目标节点的最便宜的路径），但是您可以忽略这个细节。

要应用 BFS 算法，您需要定义评估函数和搜索空间，即状态（或节点）及其连接。例如，如果你想找到从巴黎到马德里的最便宜的路径，你需要定义巴黎是开始节点，马德里是目标节点，然后你需要定义巴黎和马德里之间的所有中间节点，但你还需要定义定义$g$和$h$.

爬山

爬山 (HC) 是一种通用搜索策略（因此它也不仅仅是一种算法！）。HC 算法是贪婪的局部搜索算法，即它们通常只找到局部最优值（与全局最优值相反）并且它们贪婪地这样做（即它们不向前看）。HC 算法背后的思想是向价值增加的方向移动（或攀爬）。HC 算法可用于解决优化问题，而不仅仅是定义明确的搜索问题，即您从某个解决方案开始，然后移动到最佳相邻解决方案，然后循环。

最佳优先搜索与爬山

• BFS 算法是知情的搜索算法（相对于不知情的）
• BFS 算法需要定义搜索空间和评估函数
• 一些 BFS 算法（例如 A*）保证找到最佳的全局解决方案
• HC 算法是通用的（即广泛适用的）但局部和贪婪的搜索和优化算法；因此，它们通常不能保证找到全局最优值（但在实践中，它们可能会很好地工作，这也取决于问题）。
• HC 算法不需要明确定义搜索空间（即不需要定义起始节点和目标节点等），但您只需要一种确定最佳相邻解决方案的方法

进一步阅读

Stuart Russell 和 Peter Norvig所著的《人工智能：一种现代方法》一书提供了有关这两种搜索方法的更多详细信息。（你可以在网上找到这本书的免费副本）。