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

Question

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

algorithmsearchartificial-intelligencebacktracking

22

我目前正在学习算法课程，但是我对暴力搜索和回溯的确切定义有些困难。据我了解，以下内容是正确的：

暴力搜索 (BFS) 是一种算法，它计算问题的每个可能解决方案，然后选择一个符合要求的方案。
显式约束条件为每个选择提供了可能的取值范围（例如，选择1-3仅限于{1，2}，选择4仅限于{3，4，5}等），这决定了搜索“执行树”的形状。
隐式约束条件将不同的选择相互关联（例如，第2个选择必须大于第1个选择等），这在BFS中用于删除潜在的解决方案。
回溯是BFS的扩展，在每个选择之后评估隐式约束条件（而不是在生成所有解决方案之后），这意味着可能的解决方案可以在完成之前被丢弃。

基本上，我想知道这是否准确，如果不是，我希望得到一些澄清。先谢谢了。

- AptenodytesForsteri

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Willem Van Onsem · Accepted Answer

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

就像你所说的明确的约束是对每个变量的定义域的约束，因此x_i∈S_i。请注意，S_i不必以集合形式陈述。例如，您可以说明S₀是小于25的所有质数的集合。

隐含的约束则是针对两个或更多变量定义的谓词，如P(x₁,x₂,...,x_n)。例如x₂<x₃。但它也可以定义在更多变量上(例如三个)。

暴力搜索算法只考虑明确的约束: 它将来自S_i的所有可能值分配给变量x_i，并对所有变量执行此操作。构造出这样一个配置后，它验证所有隐含性约束是否得到满足。

另一方面，回溯旨在优化这个过程。从定义了一个隐含约束条件的所有变量被赋值的那一刻起，它便验证该约束条件。如果约束条件失败，则立即将不同的值分配给其中一个变量。好处是，例如枚举法已经将x₁=2和x₂=5分配为2和5，并且隐含约束条件x₁ > x₂失败了，那么它不会仅仅为了发现所有这些值的配置都失败而分配值给x₃、x₄、...。

当然，回溯需要进行一些记录：您需要找出在设置某个值时哪些约束“触发”。但对于很多约束编程问题（如SAT）来说，存在有效的算法来做到这一点（使用“监视文字”等）。此外，像Gecode这样的约束编程库还具有先进的排队机制，可以快速评估约束条件等。