回溯和暴力搜索之间的差异

Question

我目前正在学习算法课程,而且我很难理解蛮力搜索和回溯的确切定义.据我了解,以下情况属实:

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

基本上,我只是想知道这是否准确,如果不是,我真的很感激一些澄清.提前致谢.

Answer 1

简短的回答:如果我正确地读出了问题,你是正确的.

那么像你说的明确约束都在限制域中的每个变量,这样X _我 ∈S _我.请注意,S _i不必作为集合声明.例如,您可以说S ₀是小于25的所有素数的集合.

另一方面,隐含约束是在两个或更多个变量 P(x ₁,x ₂,...,x _n)上定义的谓词.例如 x ₂ <x ₃.但它也可以在更多变量上定义(例如三个).

强力搜索仅考虑显式约束:它将所有可能的值从 S _i分配给变量 x _i,并将其分配给所有变量.在构造了这样的配置之后,它验证是否满足所有隐式约束.

另一方面, Bactracking旨在优化此过程.从分配了定义隐式约束的所有变量的那一刻起,它验证该约束.如果约束失败,则它立即为其中一个变量分配不同的值.优点是,如果例如蛮力已经指定2到 x ₁ = 2并且5到 x ₂ = 5,并且隐式约束 x ₁ > x ₂失败,那么它将不会将值赋给 x ₃,x ₄,.... ..只是发现对于这些值的所有配置都失败了.

当然,回溯中涉及一些簿记:您需要找出在设置某个值时哪些约束"触发".但是对于许多约束编程问题(例如SAT),存在有效的算法(使用观察的文字等).此外,像Gecode这样的约束编程库也具有高级排队机制,因此首先评估快速约束等.