最陡峭的登山攀登与最佳第一搜索

Question

我正在尝试使用不同的算法来解决问题,而Steepest Ascent Hill Climbing(SAHC)和Best First Search是我需要实现的两种算法.

根据维基百科:

"在最陡峭的登山攀登中,所有后继者都进行了比较,并选择了最接近解决方案......"

"最陡峭的登山攀爬类似于最佳优先搜索,它尝试所有可能的当前路径扩展,而不是只有一个."

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

我真的不明白这些是如何不同的.有些人可以帮我解决这个问题,最好是用树木做一些解释吗？

Answer 1

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

例如,假设我们有一个图表

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

每个边缘具有相同的重量:忽略我糟糕的ASCII艺术技巧:).还假设在我们的启发式函数中,A被认为比C更接近末尾.(这可能仍然是一个可接受的启发式 - 它只是低估了A的真实距离.)

然后最陡峭的爬山将首先选择A(因为它具有最低的启发值),然后选择B(因为它的启发式值低于起始节点),然后选择结束节点.

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

1. 将A和C添加到打开的列表中.
2. 从开放列表中取A,最佳值,然后添加B.然后OPEN = {B,C}.
3. 从开放列表中取出最佳节点(B或C,在一秒钟内更多),并添加其后继者,即目标状态.
4. 将目标状态从打开的列表中移除并返回到达那里的路径.

在步骤3中选择B或C取决于您正在使用的最佳优先搜索算法.A*将评估节点作为到达那里的成本加上到达终点的成本估计,在这种情况下C将获胜(事实上,使用可接受的启发式,A*保证始终为您提供最优路径)."贪婪的最佳优先搜索"将在两个选项之间任意选择.在任何情况下,搜索都会保留一个可能的位置列表,而不是单个列表.

现在这两者有何不同之处更清楚了吗？