我正在尝试使用不同的算法来解决问题，最速爬坡 (SAHC) 和最佳优先搜索是我需要实现的其中两种算法。
根据 Wikipedia:
“在最陡峭的爬坡中，比较所有后继者并选择最接近解决方案的...”
“最速爬山类似于最佳优先搜索，它会尝试当前路径的所有可能扩展，而不是只尝试一个。”
SAHC:比较所有后继者并选择最接近解决方案的。
BestFS:尝试当前路径的所有可能扩展，而不是只尝试一个。
我真的不明白它们有什么不同。有人可以帮我解决这个问题，最好是用树来解释一下吗？
最佳答案
它们非常相似。不同之处在于，最佳优先搜索会考虑从起始节点到结束节点的所有路径，而最陡峭的爬山在搜索过程中只会记住一条路径。
例如，假设我们有一个图
start ---- A ---- B ---- end
\ /
------\ /---------
\ /
C
每条边都具有相同的权重:忽略我蹩脚的 ASCII 艺术技巧 :)。 还假设在我们的启发式函数中，A 被认为比 C 更接近终点。(这仍然可能是 admissible heuristic——它只是低估了 A 的真实距离。)
那么最陡爬山会先选择A(因为它的启发值最小)，然后是B(因为它的启发值低于起始节点)，最后是结束节点。
另一方面，最佳优先搜索会
- 将 A 和 C 添加到开放列表中。
- 从开放列表中取出最佳值 A，然后添加 B。然后 OPEN = {B, C}。
- 从开放列表中取出最佳节点(B 或 C，稍后详细介绍)，并添加其后继者，即目标状态。
- 从开放列表中取出目标状态并返回到达那里的路径。
在第 3 步中选择 B 还是 C 完全取决于您使用的最佳优先搜索算法。 A*会将节点评估为到达那里的成本加上到达终点的成本估计，在这种情况下 C 将获胜(事实上，通过可接受的启发式算法，A* 保证始终为您提供最佳路径) . “贪婪的最佳优先搜索”会在两个选项之间任意选择。在任何情况下，搜索都会维护一个可能的出发地点列表，而不是一个。
现在两者的区别是不是更清楚了？
关于algorithm - 最速爬坡与最佳优先搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14741006/