我正在尝试使用不同的算法解决问题，而最陡坡爬山 (SAHC) 和最佳优先搜索是我需要实现的其中两种算法。
根据维基百科：
“在最陡峭的爬坡过程中，所有后继者都会被比较，并选择最接近解决方案的人......”
“最陡坡爬山类似于最佳优先搜索，它尝试当前路径的所有可能扩展，而不是只尝试一个。”
SAHC : 比较所有后继者并选择最接近解决方案的。
BestFS：尝试当前路径的所有可能扩展，而不是只尝试一个。
我真的不明白这些有什么不同。有人可以帮我解决这个问题，最好用树来解释一下吗？
问问题
9214 次
3 回答
13
它们非常相似。不同之处在于，最佳优先搜索考虑了从起始节点到结束节点的所有路径，而最陡爬坡仅在搜索过程中记住一条路径。
例如，假设我们有一个像
start ---- A ---- B ---- end
\ /
------\ /---------
\ /
C
每条边都具有相同的权重：忽略我蹩脚的 ASCII 艺术技巧 :)。还假设在我们的启发式函数中，A 被认为比 C 更接近末端。（这仍然是一个可接受的启发式- 它只是低估了 A 的真实距离。）
然后最陡爬山会首先选择 A（因为它具有最低的启发式值），然后是 B（因为它的启发式值低于起始节点的），然后是结束节点。
另一方面，最佳优先搜索将
- 将 A 和 C 添加到打开列表中。
- 从打开列表中取出最佳值 A，然后添加 B。然后 OPEN = {B, C}。
- 从打开列表中取出最好的节点（B 或 C，稍后会详细介绍），并添加其后继节点，即目标状态。
- 将目标状态从打开列表中取出并返回到达那里的路径。
第 3 步中 B 或 C 的选择完全取决于您使用的最佳优先搜索算法。A*会将节点评估为到达那里的成本加上到达终点的成本估计值，在这种情况下 C 将获胜（事实上，通过可接受的启发式方法，A* 保证总是让您获得最优小路）。“贪婪的最佳优先搜索”将在两个选项之间任意选择。在任何情况下，搜索都会维护一个可能去处的列表，而不是一个地方。
现在更清楚两者有何不同了吗？
于 2013-02-07T00:04:51.833 回答
4
SAHC 将贪婪地选择一个单一的（可能不是最优的）路径——它只会在每一步中选择最好的节点，直到它达到目标。
另一方面，最佳优先生成整个搜索树。通常（在 A* 的情况下）它会找到最佳解决方案，但 SAHC 无法保证这一点。
于 2013-02-07T00:18:40.407 回答
0
Dint知道如何标记所以再次粘贴它，对不起。所以这就是我得到的不同之处。
不同之处在于理解在寻找目标状态时更关心什么。
问我们的目标是什么……最终目标状态是什么？或达到目标状态的最佳路径
最佳优先搜索是一种系统性搜索算法，在为每个当前节点找出相邻节点的最佳启发值的基础上，通过迭代向前推进来实现系统性。
这里的评估函数（启发式函数）计算实现目标状态的最佳路径。所以在这里我们可以看到最佳优先搜索关注的是达到目标状态的最佳路径。
然而，有很多问题并不关心“通往目标的道路” ，唯一关心的是以任何可能的方式或路径达到最终状态。（例如：8皇后问题）。
因此，为此使用了本地搜索算法。
本地搜索算法使用单个当前节点进行操作，并且通常仅移动到该节点的邻居。
爬山算法是一种局部搜索算法。所以在这里我们需要了解到达目标状态的方法，而不是考虑爬山时达到的最佳路径。
（如AI-A Modern Approach,SR & PN中所述）
基本上，要了解本地搜索，我们需要考虑状态空间景观。
景观既有
(i)位置（由国家定义）和
(ii)高程（由启发式函数或目标函数的值定义）
我们需要了解这两种海拔高度，
(i)如果高程对应于目标函数，则目标是找到最高峰，即全局最大值。
（因此，这些类型的海拔在不关心成本而只关心寻找最佳即时动作的不同场景中很有用）
(ii)如果海拔对应于成本，那么目标是找到最低谷，即全局最小值。
（这是最常见的事情，即最陡（总是加强更好的估计，即没有高原问题或任何其他问题）爬山类似于最佳优先搜索。这里的高程函数是提供最佳最小成本的启发式函数。和爬山这里只关心当前节点并遍历相邻节点以获得最小值并继续扩展最佳节点，类似于 Best First Search）
注意：
爬山算法不会超越当前状态的直接邻居。它只关心最佳邻居节点进行扩展。最佳邻居由上述评估函数决定。
然而，最佳优先搜索算法会先于直接邻居寻找到达目标的最佳路径（使用启发式评估），然后继续寻找最佳路径。所以区别在于局部搜索和系统搜索算法的方法。
了解方法的差异，您将了解为什么两者命名不同。
于 2015-11-17T09:59:53.400 回答