回溯和暴力搜索之间的区别
Differences between backtracking and brute-force search
我目前正在学习算法课程，但我在理解暴力搜索和回溯的确切定义时遇到了一些困难。据我了解，以下是正确的：
- 蛮力搜索 (BFS) 是一种算法，它计算问题的所有可能解决方案，然后选择一个符合要求。
- 显式 约束给出了每个选择的可能值（例如，选择 1-3 被限制为
{1, 2}，选择 4 被限制为 {3, 4, 5}等），这决定了搜索 "execution tree" 的形状。
- 隐式 约束将不同的选择相互关联（例如，选择 2 必须大于选择 1，等等），这在 BFS 中用于删除潜在的解决方案。
- Backtracking 是 BFS 的扩展，其中 implicit 约束在每次选择后进行评估（相对于 在 生成所有解之后），这意味着可以在 'finished'.
之前丢弃潜在的解
基本上，我想知道的是这是否准确，如果不准确，我将非常感谢您的澄清。提前致谢。
简答：如果我没看错问题，你正确。
就像你说的 显式约束 是对每个变量的 域 的约束所以xi∈Si。请注意 Si 不必声明为集合。例如，您可以声明 S0 是所有小于 25 的素数的集合。
另一方面，隐式约束是在两个或更多变量[=72]上定义的谓词=] P(x1,x2,...,xn)。例如x23 。但它也可以定义在更多变量（例如三个）上。
蛮力搜索 仅考虑 显式 约束：它分配所有可能的从 Si 到变量 xi 的值和这适用于 所有 变量。在构建了这样一个 配置 之后，它会验证是否满足所有 隐式约束 .
另一方面，Backtracking 旨在优化此过程。从分配了定义了 隐式约束 的所有变量的那一刻起，它就会验证该约束。如果约束失败，则它会立即为其中一个变量分配一个不同的值。优点是，如果例如蛮力分配 2 到 x1=2 和 5 到 x2=5，隐式约束x1 > x2 失败，那么它不会给 x3,x4,...[=72 赋值=] 只是为了发现这些值的所有配置都失败了。
当然，回溯涉及一些簿记：当设置某个值时，您需要找出哪些约束"fire"。但是对于很多 约束编程 问题（例如 SAT），存在有效的算法来做到这一点（使用 watched literals 等） .此外，像 Gecode 这样的约束编程库也有先进的排队机制，可以首先评估快速约束，等等
我目前正在学习算法课程，但我在理解暴力搜索和回溯的确切定义时遇到了一些困难。据我了解，以下是正确的：
- 蛮力搜索 (BFS) 是一种算法，它计算问题的所有可能解决方案，然后选择一个符合要求。
- 显式 约束给出了每个选择的可能值（例如，选择 1-3 被限制为
{1, 2}，选择 4 被限制为{3, 4, 5}等），这决定了搜索 "execution tree" 的形状。 - 隐式 约束将不同的选择相互关联（例如，选择 2 必须大于选择 1，等等），这在 BFS 中用于删除潜在的解决方案。
- Backtracking 是 BFS 的扩展，其中 implicit 约束在每次选择后进行评估（相对于 在 生成所有解之后），这意味着可以在 'finished'. 之前丢弃潜在的解
基本上，我想知道的是这是否准确，如果不准确，我将非常感谢您的澄清。提前致谢。
简答：如果我没看错问题，你正确。
就像你说的 显式约束 是对每个变量的 域 的约束所以xi∈Si。请注意 Si 不必声明为集合。例如，您可以声明 S0 是所有小于 25 的素数的集合。
另一方面，隐式约束是在两个或更多变量[=72]上定义的谓词=] P(x1,x2,...,xn)。例如x2
蛮力搜索 仅考虑 显式 约束：它分配所有可能的从 Si 到变量 xi 的值和这适用于 所有 变量。在构建了这样一个 配置 之后，它会验证是否满足所有 隐式约束 .
另一方面，Backtracking 旨在优化此过程。从分配了定义了 隐式约束 的所有变量的那一刻起，它就会验证该约束。如果约束失败，则它会立即为其中一个变量分配一个不同的值。优点是，如果例如蛮力分配 2 到 x1=2 和 5 到 x2=5，隐式约束x1 > x2 失败，那么它不会给 x3,x4,...[=72 赋值=] 只是为了发现这些值的所有配置都失败了。
当然，回溯涉及一些簿记：当设置某个值时，您需要找出哪些约束"fire"。但是对于很多 约束编程 问题（例如 SAT），存在有效的算法来做到这一点（使用 watched literals 等） .此外，像 Gecode 这样的约束编程库也有先进的排队机制，可以首先评估快速约束，等等