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