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

Question

我目前正在学习算法课程，我在理解暴力搜索和回溯的确切定义方面遇到了一些困难。据我了解，以下说法正确的是：

• 暴力搜索（BFS）是一种算法，它计算问题的所有可能解决方案，然后选择满足要求的解决方案。
• 显式约束给出每个选择的可能值（例如，选择1-3仅限于

  {1, 2}

  ，选择4仅限于

  {3, 4, 5}

  等），这决定了搜索的“执行树”的形状.
• 隐式约束将不同的选择相互关联（例如，选择 2 必须大于选择 1 等），这在 BFS 中用于删除潜在的解决方案。
• 回溯是 BFS 的扩展，其中在每次选择后都会评估隐式约束（而不是在之后生成所有解决方案），这意味着潜在的解决方案可以在“完成”之前被丢弃.

基本上，我想知道这是否准确，如果不准确，我真的很感激一些澄清。预先感谢。

Answer 1

简短回答：如果我正确地阅读了问题，那么你是正确。

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

另一方面，

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

强力搜索仅考虑显式约束：它将S_i中的所有可能值分配给变量x_i，并将其分配给all变量。在构建了这样的配置后，它会验证是否满足所有隐式约束。

另一方面，

回溯旨在优化此过程。从定义了“隐式约束”的所有变量都被分配的那一刻起，它就会验证该约束。如果约束失败，它会立即为其中一个变量分配不同的值。优点是，如果暴力破解将 2 分配给 x1=2_{，将 5 分配给} x2=5_{，并且隐式约束} x1 > x_{2 失败，那么它不会将值分配给} x3,x₄,... _{只是为了发现这些值的所有配置都失败了。} 当然，回溯涉及一些簿记：您需要找出当设置某个值时哪些约束“触发”。但对于许多“约束编程”问题（例如 SAT），存在有效的算法来做到这一点（使用“监视文字”等）。此外，像

Gecode

这样的约束编程库也具有先进的排队机制，例如首先评估快速约束等。