我目前正在学习算法课程，对蛮力搜索和回溯的具体定义有些困惑。我的理解如下：

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

基本上，我只是想知道这些是否准确，如果不准确，我非常希望得到一些澄清。提前感谢。

回答：

简短回答：如果我正确理解了问题，你是正确的。

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

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

蛮力搜索只考虑显式约束：它为变量x_i分配来自S_i的所有可能值，并且对所有变量都这样做。在构建这样的配置后，它验证所有隐式约束是否满足。

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

当然，回溯涉及一些记录工作：你需要找出当某个值被设置时哪些约束会“触发”。但对于许多约束编程问题（如SAT），存在高效的算法来做到这一点（使用监视字面量等）。此外，像Gecode这样的约束编程库还具有高级排队机制，以便首先评估快速约束等。