algorithm - 回溯和暴力搜索之间的区别

Question

我目前正在学习算法类(class)，但我在理解暴力搜索和回溯的确切定义时遇到了一些困难。据我了解，以下内容是正确的:

• 蛮力搜索 (BFS) 是一种算法，它计算问题的所有可能解决方案，然后选择满足要求的解决方案。
• 显式约束给出每个选择的可能值(例如，选择 1-3 限于 {1, 2}，选择 4 限于 {3, 4, 5}, etc.)，这决定了搜索的“执行树”是如何形成的。
• 隐式约束将不同的选择相互关联(例如，选择 2 必须大于选择 1，等等)，这在 BFS 中用于删除潜在的解决方案。
• 回溯 是 BFS 的扩展，其中在每个选择之后评估隐式约束(而不是在生成所有解决方案之后) )，这意味着潜在的解决方案可以在“完成”之前被丢弃。

基本上，我想知道的是这是否准确，如果不准确，我将非常感谢您的澄清。提前致谢。

Answer 1

简答:如果我没看错问题，那么你是正确的。

就像你说的那样，显式约束 是对每个变量的域 的约束，所以x_i∈S_i。请注意，S_i 不必声明为集合。例如，您可以声明 S₀ 是所有小于 25 的素数的集合。

隐式约束另一方面，是在两个或多个变量上定义的谓词 P(x ₁,x₂,...,x_n)。例如 x₂3。但它也可以在更多变量(例如三个)上定义。

蛮力搜索 仅考虑显式约束:它分配S_{i< 中的所有可能值/sub>} 到变量 x_i 并且这适用于所有 变量。在构建了这样一个配置之后，它会验证是否满足所有隐式约束。

另一方面，

回溯 旨在优化此过程。从分配了定义了隐式约束 的所有变量的那一刻起，它就会验证该约束。如果约束失败，则它会立即为其中一个变量分配一个不同的值。优点是，如果例如蛮力已将 2 分配给 x₁=2 并将 5 分配给 x₂=5，而隐式约束x₁> x₂失败，则不会给x_3赋值,x₄,... 只是为了发现这些值的所有配置都失败了。

当然，回溯涉及一些簿记工作:您需要找出在设置特定值时“触发”哪些约束。但是对于很多约束编程问题(例如 SAT)，存在有效的算法来做到这一点(使用监视文字等)。此外，像 Gecode 这样的约束编程库也有先进的排队机制，例如首先评估快速约束等。