algorithm - 最速爬坡与最佳优先搜索

Question

我正在尝试使用不同的算法来解决问题，最速爬坡 (SAHC) 和最佳优先搜索是我需要实现的其中两种算法。

根据 Wikipedia:

“在最陡峭的爬坡中，比较所有后继者并选择最接近解决方案的...”

“最速爬山类似于最佳优先搜索，它会尝试当前路径的所有可能扩展，而不是只尝试一个。”

SAHC:比较所有后继者并选择最接近解决方案的。
BestFS:尝试当前路径的所有可能扩展，而不是只尝试一个。

我真的不明白它们有什么不同。有人可以帮我解决这个问题，最好是用树来解释一下吗？

Answer 1

它们非常相似。不同之处在于，最佳优先搜索会考虑从起始节点到结束节点的所有路径，而最陡峭的爬山在搜索过程中只会记住一条路径。

例如，假设我们有一个图

start ---- A ---- B ---- end
  \                     /
   ------\    /---------
          \  /
           C

每条边都具有相同的权重:忽略我蹩脚的 ASCII 艺术技巧 :)。还假设在我们的启发式函数中，A 被认为比 C 更接近终点。(这仍然可能是 admissible heuristic——它只是低估了 A 的真实距离。)

那么最陡爬山会先选择A(因为它的启发值最小)，然后是B(因为它的启发值低于起始节点)，最后是结束节点。

另一方面，最佳优先搜索会

1. 将 A 和 C 添加到开放列表中。
2. 从开放列表中取出最佳值 A，然后添加 B。然后 OPEN = {B, C}。
3. 从开放列表中取出最佳节点(B 或 C，稍后详细介绍)，并添加其后继者，即目标状态。
4. 从开放列表中取出目标状态并返回到达那里的路径。

在第 3 步中选择 B 还是 C 完全取决于您使用的最佳优先搜索算法。 A*会将节点评估为到达那里的成本加上到达终点的成本估计，在这种情况下 C 将获胜(事实上，通过可接受的启发式算法，A* 保证始终为您提供最佳路径) . “贪婪的最佳优先搜索”会在两个选项之间任意选择。在任何情况下，搜索都会维护一个可能的出发地点列表，而不是一个。

现在两者的区别是不是更清楚了？