4.1.1 背景介绍
1.回溯搜索
CSP问题是人工智能中的一个主要分支,求解CSP问题的常见方法都是基于回溯搜索的,其基本思想就是扩展问题的局部解。在搜索的每个阶段,算法都尝试将当前的局部解扩展为一个最终解[1,2]。如3.1.2节介绍,在搜索过程中,变量被分成3个集合:已赋值变量(PV)、当前变量(CV)和未赋值变量或自由变量(FV)。对于由PV中变量的赋值所构成的一个局部解,如果它无法再向其他的变量进行扩展且无法成为最终解的一部分,那么就产生了不一致。如果当前变量的所有取值都被尝试过,则产生死端。此时,在PV中有的变量就要被从当前局部解中移除,这就是回溯。
用于改进回溯算法的技术可以分为两类:前向方法和后向方法。当算法正在准备扩展局部解时,调用前向方法[3];而当搜索遭遇死端时,调用后向方法。在我们以前的工作[4]中,已经介绍过BFS-BB中的前向方法。而在本章,我们的焦点是后向方法,包括对死端产生的原因进行分析来决定需要回溯多远,以及记录有哪些新约束从而避免相同的矛盾在后面的搜索中再次出现[5]。
2.常见的回溯算法
时序回溯(Chronological Backtracking,BT)[1]是最简单、使用最多的回溯算法。对当前变量的赋值与已赋值变量的赋值之间的一致性检查是按照初始排序进行的。如果当前的一致性检查失败了,那么就尝试当前变量区间内的下一个值。如果再没有值可以尝试了,那么BT会回溯到最近的一个被赋值变量。在一个新的变量被赋值且一致性检查成功后,要记录一个部分解。
回跳(BackJumping,BJ)[2]与BT类似,但是当无法为当前变量(如x i)发现一致的赋值,也就是说遇到死端时,BJ的效率更高。不同于BT回溯至上一个最新赋值变量,BJ回跳到与当前变量有矛盾的最深的已赋值变量(如x j)。为x j选择另一个赋值可能会进而产生x i的一致性赋值,但是改变x i和x j之间任何变量的赋值都是无用的,因为那不是死端产生的原因。BJ会直接来到导致死端的矛盾变量,而略过与死端无关的变量。(https://www.daowen.com)
矛盾驱动的回跳(Conflict-directed BackJumping,CBJ)[3]的工作方式比BJ还复杂。每个变量都有其矛盾变量集,该矛盾变量集中是与其当前赋值不一致的已赋值变量。当当前变量x i的赋值V i与某个过去变量x j的赋值V j不一致时,将x j加入x i的矛盾变量集合。当当前变量x i再无值可以选择时,CBJ回溯至x i的矛盾变量集中最深的变量x h。同时,在x i的矛盾变量集中,除了x h都被加入x h的矛盾变量集中,这样就不会丢失任何关于矛盾的信息。此时,除了以前所述的3个变量集合,还多了一个集合,即矛盾变量集。
不同于上述向回追溯的检查方法,前向检查(Forward Checking,FC)[5]是向前进行一致性检查,也就是说,一致性检查是在当前变量和未来变量之间进行的。当当前变量被赋值后,未来变量的区间是按照如下方式进行削减的:所有与当前变量的赋值不一致的取值都被移除。如果没有未来变量的区间被消除(即每个未来变量的区间内还有取值),那么下一个变量的赋值就在其被削减后的区间之内选择;否则FC就失效了,需要尝试下一个变量。如果没有值可以为当前变量选择,那么FC进行时序回溯。BFS-BB采用FC作为其回溯策略。
混合搜索算法前向检查-矛盾驱动的回溯(Forward Checking and Conflict-directed BackJumping,FC-CBJ)[3,6]集成了FC和CBJ的优势。与FC的时序回溯不同,FC-CBJ记录导致当前不一致的变量,并由此确定回溯点。当当前变量x i的赋值V i与某个未来变量x j的值V j不一致时,将x j加入x i的矛盾变量集。而当x k的区间被消除时,在x k的矛盾变量集中的变量就被加入当前变量x i的矛盾变量集。如果没有赋值可以为当前变量x i选择,那么FC-CBJ回溯至x i的矛盾变量集中最深的变量x h。同时,在x i的矛盾变量集中,除了x h外都被加入x h的矛盾变量集,这样就不会丢失任何关于矛盾的信息。Prosser[7]认为FC-CBJ是回溯算法中的冠军,如图4-1所示,其中处于更下方的程序效率更高。
图4-1 回溯算法的层次
