1回溯搜索算法Peter van Beek对于求解约束满足问题有许多算法技术：回溯搜索，局部搜索，和动态规 划。在本章，我们先回顾回溯算法。在文献中有时把基于动态规划15的算法 称为变量删除，复合或蕴涵算法在第 7 章讨论。局部或随机搜索算法在第 5 章 讨论。 解决约束满足问题(CSP)的一个算法或者是完备的或者不完备。完备或者系 统的算法能够保证如果问题存在解能够找到，并且可用于证明一个 CSP 没有一 个解和找到一个可证明的最优解。回溯搜索算法和动态规划算法通常上是完备 算法的实例。不完备或不系统的算法不能够用于证明一个 CSP 问题没有解或找 到一个可证明是最优的解。然而，那样的算法在问题有解存在时常常找到一个 解的效率较高并可用于找到一个近似最优解的次优解。局部搜索或随机搜索算 法是不完备算法的实例。 所有这两类算法-回溯搜索和动态规划是完备的，回溯搜索算法是实际中 目前最重要的。动态回溯算法的缺陷是它们经常会需要指数量级的时间和空间， 而且为了找到或使它容易生成所有的 CSP 解，它们确实做了不必要的工作。然 而，人们很少希望在实际中找到一个 CSP 问题的所有解。相比之下，回溯搜索 算法一次只寻找一个解，因而仅需要多项式规模的空间。 因为第一个对回溯算法的形式化描述是在 40 年以前30，57，因而很多改 进回溯算法效率的技术已经被提出和评价。在本章，我们回顾某些最重要的技 术，包括分支策略，约束传播，冲突记录，回跳，对变量和值排序的启发式， 随机与重起策略以及深度优先的另一种方案。这些技术并不总是排他的，而且 有时组合两个或多项技术到一个算法中有一个被增的效果（例如组合重新开始 与冲突记录） ，而有时它会有一个性能下降（例如增加的约束传播对回跳） 。给 定许多可能的方法，这些技术可以组合进一个算法中去，我们也回顾对比回溯 算法的工作。这些技术最好的组合带来了健壮的回溯算法，现在日常上用来求 解规模大的，难解的实际问题。 4.1 基础 在本节，我们首先通过一个简短的回顾所需要的回溯搜索的背景知识来定 义约束满足问题。 定义 4.1(CSP)一个约束满足问题 CSP 由变量集合 X=x1,x2,，值集合 D=a1,a2,ad，其中每一个变量 xiX 有一个关联的可能取值有限定义域 dom(xi)D，和一个约束集合所构成。 每一个约束 C 是一个关系某些变量集合上的元组集合，用 vars(C)表示。 Vars(C)的规模称为约束的元数。一个单元约束是一个一元约束，一个二元约束 是一个元为二的约束，非二元约束是一个元大于二的约束，而全局约束可能是 任意变量子集上的约束。一个约束可以通过确定约束中的元组必须满足的一个 公式所内涵定义，或着显示地列举约束中元组所外含定义。一个 CSP 的解是对 每个变量的值指派满足所有的约束。如果 CSP 问题没有解存在就称为不相容的 或不可满足的。 我们将使用 6-皇后问题作为回顾中的例子：在 66 的棋盘上我们如何放置 6 个皇后使得没有任何两个皇后之间彼此攻击。作为一个可行的 CSP 模型，令2棋盘的每一列用一个变量代表x1,x2,x6，每一个变量有一个定义域 dom(xi) =1,2,6。指派给一个变量 xi一个值 j 意味着在第 j 行第 i 列放置一个皇后。 对于 1ij6 变量 xi和 xj之间的每一个序偶，有一个约束 C(xi,xj)，限定(xixj) i-j xi-xj )。对于皇后问题一个可能的解是x1=4,x2=1,x3=5,x4=2,x5=6,x6=3。可满足性问题 SAT 是一个 CSP，其中变量的定义域是布尔值而约束是布尔 公式。我们将假定约束是合取范式因而写作子句（的合取） 。一个文字是一个布 尔变量或其否定，一个子句是文字的析取。例如，公式x1x2x3是一个子句。 只有一个文字的子句称为单元子句；没有文字的子句称为空子句。空子句是不 可满足的。 对一个 CSP 回溯搜索一个解可以看成是深度优先搜索树的遍历。当搜索进 行时生成搜索树而且描述了为了找到一个解可能必须检查的其他选择。在搜索 树中扩展一个节点的方法经常称为分支策略，在文献中有一些其他方法被提出 和考察（见 4.2 节） 。如果在算法执行的某一点，一个节点生成了，则回溯算 法访问这个节点。约束用于检查是否一个节点可能通向一个 CSP 的解和修剪不 包含解的子树。搜索树中的一个节点是死点，如果它不能通向一个解。 朴素的搜索算法(BT)是所有更加复杂回溯算法的起始点（见表 4.1）在 BT 搜索树中，在 0 层的根节点是指派为空集的而在第 j 层指派集合是 x1=a1,x2=a2,xj=aj。在搜索树的每一个节点一个没有赋值的变量被选中而这 一个点的分支有通过用这个变量的定义域中的值实例化该变量扩展此节点的所 有可能路径构成。分支体现了对那个变量可做的不同选择。在 BT 中，只有具 有未赋值的约束在此节点处要检查。如果一个约束检查失败约束是不可满足 的，要尝试当前变量的下一个定义域值。如果没有剩下更多的定义域值。BT 回 溯到最近赋值的变量。如果最后一个变量实例化后所有约束通过检查，那么就 找到一个解。图 4.1 展示了对一个 6-皇后问题一个朴素回溯算法(BT)生成的回溯树片段。 节点上的标记用速记的方式代表那个节点的指派集合。例如，节点标记 25 由指23456252532531253625314253643派集合x1=2,x2=5所组成。白色圆点表示具有未赋值变量的约束是可满足的 （没有两个皇后彼此互相攻击） 。黑色圆点表示其中一个或多个约束检测失败。 （对于阴影和虚线箭线第 4.5 节给出理由） 。为了简化的目的，我们假定一个静 态实例化排序其中变量 xi总是在搜索树的第 i 层被选中，指派给变量的值是按 照 1,2,6 的顺序排列。4.2 分支策略 在朴素回溯算法(BT)中，在搜索树中一个节点 p=x1=a1,x2=a2,xj=aj是一 个敷值指派集合，而 p 是选择一个变量 x 并对一个新的节点 px=a增加一个 新分支扩展得到的。随着树中搜索深度的增加，辅助指派被加上而且回溯这个 指派被追踪。然而，这仅是一种可能分支策略，而且在文献中另外几种方案被 提出和评价。 更一般地来说，回溯搜索算法搜索树中一个节点 p=b1,bj是一个分支约 束集合，其中 bi, 1ij，是搜索树中第 i 层加上的分支约束。对某些分支约束 bij+1, 1ik，通过增加分支 pb1j+1,pbkj+1扩展得到的。分支常常使用启 发式排序，最左侧的分支被认为是最有希望的。为了保证完备性，从一个节点 所有分支上被加的约束必须是相互独立的和枚举的。 通常上，分支策略由附加的单元约束构成。在此情况下，一个变量排序启 发式用于选择下一个要分支的变量而且分支排序启发式是由一个变量排序启发 式确定的（见第 4.6 节） 。作为一个使用的例子，令 x 是要被分支的变量，令 dom(x)=1,2,.,6，而且假定值排序启发式是按照字典序的。三个当前涉及单 元约束的主流分支策略如下： 1 枚举。变量 x 依次被实例化为其定义域中的值。对变量定义域中的每一 个值生成一个分支而且 x=1 沿着第一个分支被加上，x=2 沿着到二个分支被加 上，依次类推。枚举分支策略在许多讲述回溯的课本和关于求解 CSP 的回溯算 法工作中被假定。文献中这种分支策略的另一个名字是 d-分支，其中 d 是定义 域的规模。 2 二元选择点。变量 x 被实例化其定义域中的某个值，假定在我们的例子 中值 1 被选定，分别生成两个分支和两个约束 x=1 和 x1。这种分支策略常常 被应用在求解 CSP 的约束程序语言中（见文献72，123）并在文献116sabin 和 freuder 回溯算法搜索中维持弧相容所使用。这种分支策略在文献中的另一个 名字是 2-分法。 3 定义域划分。这里变量不必实例化，然而变量的选择在每个子问题中被 压缩了。对于象我们例子中的排序定义域，这可能有一个分支上附加一个形如 x3 另一个分支附加约束 x3 组成。 当然，如果定义域是二元的（例如在 SAT 中） ，这三种模式是相同的。表 4.1：某些命名为回溯的算法。综合算法是通过联字符号表示的组合算法。例如， MAC-CBJ 是一个维持弧相容和实现冲突有向回跳的算法。 BT 朴素的回溯：检查带有未赋值变量的约束；按照时间顺序回溯。 MAC 在一个至少有一个未赋值变量的约束上维持弧相容；按照时间顺序 回溯。 FC 前向检测算法：在一个恰好有一个未赋值的约束上维持弧相容；按 照时间顺序回溯。 DPLL 针对 SAT 问题的前向检测算法：使用单元传播；按照时间顺序回4溯。 MCk 维持强 k-相容；按照时间顺序回溯。 CBJ 冲突有向回跳；没有约束传播。 BJ 限定回跳；没有约束传播。 DBT 动态回溯：具有 0-排序相关-限定冲突记录回跳；没有约束传播。 由增加非单元约束构成的分支策略也被提出来了，象已有的分支策略是针 对特定类问题的。作为二着的例子，考虑车间作业调度，其中我们必须在一个 资源集合上调度一个任务 t1,tk集合。令 xi是一个描述 ti起驶时间的有限定义 域变量 di是 ti的固定持续时段。一个流行的分支策略是排序或序列化这些共享 一个资源的任务。分支策略是沿着一个分支增加一个约束 x1+d1x2沿着另一个 分支增加一个约束 x2+d2x1（见23）和这里的文献。这个过程直到一个死点检 测到或所有的任务已经排序。一旦所有的任务被排序，人们可以容易地构建一 个问题的解；也就是，对每个变量 xi的一个值指派。注意到，从概念上，上面 的分支策略等价于在分支的 CSP 模型上增加辅助变量是有意义的。对于共享两 个任务 t1和 t2，我们将增加辅助变量具有定义域为 dom(O12)和约束 O12=1 x1+d1x2和 O12=0 x2+d2x1。通常上，如果基本回溯算法有一个固定的策略， 人们可以通过增加辅助变量仿真不同的分支策略。因而，分支策略的选择和 CSP 模型的设计是相互依赖的决策。 关于分支策略有进一步的工作已经考察了策略的相对能力并提出了新策略。 Van Hentenryck128,pp.90-92检验了枚举和定义域划分策略间的平衡。Milano 和 van Hoeve97证明分支策略可以看成值排序启发式和定义域划分策略的组合。 值排序用于排列定义域值而定义域划分策略用于把定义域分成两个或多个集合。 当然，具有最高排序值的集合优先分支。在优化问题上已经证明此技术是非常 有效的。Smith 和 Sturdy121证明当使用具有 2-分支的时间回溯寻找所有解时， 值排序对回溯搜索效率有较大影响。这是令人吃惊的，因为已知值排序在 d-分 支环境下没有效果。Hwang 和 Mitchell71证明具有 2-分支的回溯与具有 d-分支 的回溯相比有指数量级的提高。显然 d-分支可以使用 2-分支模拟而没有效率损 失。Hwang 和 Mitchell 证明反之不成立。他们给出一类问题，其中具有优化变 量和值排序的 d-分支花费比具有简单变量和值排序的 2-分支算法指数量级多的 步骤。然而，注意到仅当 CSP 模型认为是固定的时这一结果成立。如果我们允 许向变量模型增加辅助变量这个结果不成立。4.3 约束传播在 CSP 上改善回溯算法性能的基本洞察 前向检查仅是限定约束传播的的一种方法；有许多可能变种。例如，人们 可以在具有大量未赋值变量的约束上维持弧相容。Bessiere 等人16考察了这种 可能性。人们可能也考察了当确定哪个约束应该传播时未赋值变量的定义域大 小。作为第三种选择，人们可以在约束传播算法本身上放置特定的限制：