我目前正在学习算法课程，而且我很难理解蛮力搜索和回溯的确切定义 . 据我了解，以下情况属实：
-
暴力搜索（BFS）是一种算法，它计算问题的每个可能的解决方案，然后选择满足要求的解决方案 .
-
显式约束为每个选项提供可能的值（例如，选项1-3限于
{1, 2}，选项4限于{3, 4, 5}等），这决定了搜索的"execution tree"的形状 . -
隐式约束将不同的选择与彼此相关联（例如，选项2必须大于选择1等），这在BFS中用于移除潜在的解决方案 .
-
回溯是BFS的扩展，其中在每次选择之后评估隐式约束（而不是在生成所有解决方案之后），这意味着潜在的解决方案可以在它们被'finished'之前被丢弃 .
基本上，我只是想知道这是否准确，如果不是，我真的很感激一些澄清 . 提前致谢 .
1 回答
Short answer ：如果我正确地阅读了这个问题，你就是 correct .
就像你说 explicit constraints 是每个变量的域的约束所以xi∈Si . 请注意，Si不必作为集合声明 . 例如，您可以声明S0是小于25的所有素数的集合 .
另一方面， Implicit constraints 是在两个或多个变量P（x1，x2，...，xn）上定义的谓词 . 例如x2 <x3 . 但它也可以在更多变量上定义（例如三个） .
Brute force search 仅考虑显式约束：它将所有可能的值从Si分配给变量xi，并将其分配给所有变量 . 在构造了这样的配置之后，它验证是否满足所有隐式约束 .
另一方面， Bactracking 旨在优化这一过程 . 从分配了定义隐式约束的所有变量的那一刻起，它验证该约束 . 如果约束失败，则它立即为其中一个变量分配不同的值 . 优点是，如果例如蛮力已经分配2到x1 = 2和5到x2 = 5，并且隐式约束x1> x2失败，那么它将不会将值分配给x3，x4，...仅用于查找对于这些值的所有配置，它都会失败 .
当然，回溯中涉及一些簿记：您需要找出设置某个值时的哪些约束"fire" . 但是对于许多约束编程问题（例如SAT），存在有效的算法（使用监视文字等） . 此外，像Gecode这样的约束编程库也具有高级排队机制，因此首先评估快速约束，等等 .