问题的回溯搜索

5.2 CSP问题的回溯搜索

上一节给出了把CSP问题看作搜索问题的形式化方法。用这种形式化方法，第三章和第四章中描述的任何搜索算法都可以求解CSP问题。假设我们把广度优先搜索应用于上一节给出的普遍CSP问题形式化。我们很快能注意到一些可怕的事情：顶层的分支参数就是nd，因为d个值的任何一个都可以赋给n个变量的任何一个。在下一层，分支参数是(n − 1)d，依此类推n层。我们生成了一棵有n!·dn个叶子的搜索树，尽管只有dn个可能的完全赋值！

我们看来合理但是天真的问题形式化忽略了所有CSP问题的一个共同的至关紧要的性质：可交换性。如果应用给定行动的顺序对结果没有影响，那么这个问题就是可交换的。这正是CSP问题的情况，因为当给变量赋值的时候，我们到达相同的不完全赋值而不考虑赋值的顺序。因此，所有CSP搜索算法生成后继时，在搜索树的每个节点上只考虑单个变量的可能赋值。例如，在对澳大利亚地图进行染色的搜索树的根节点，我们可能要在SA = red，SA = green和SA = blue之间选择，但我们永远不会在SA = red和WA = blue之间选择。有了这个限制，叶节点的个数如我们所希望的减少到了dn个。

术语回溯搜索用于深度优先搜索，它一次为一个变量选择值，当没有合法的值可以再赋给该变量时就回溯。该算法在图5.3中显示。注意它有效地利用了第3.4.3节描述的一次生成一个的渐增后继生成方法。同时，它也扩展当前的赋值来生成后继，而不是复制当前的赋值。因为CSP问题的表示是标准化的，不需要给 BACKTRACKING-SEARCH 提供领域特定的初始状态、后继函数或目标测试。图 5.4显示了澳大利亚问题的部分搜索树，其中我们按照WA，NT，Q，……的顺序来给变量赋值。

图5.3 约束满足问题的一个简单的回溯算法。该算法以第三章的递归深度优先搜索为模型。函数SELECT-UNASSIGNED-VARIABLE和ORDER-DOMAIN-VALUES可以用来实现本教材中讨论的通用启发式

一般的回溯在第三章的术语中是无信息算法，因此我们不期望它对大型问题非常有效。图 5.5 中第一列显示了某些样例问题的结果，证实了我们的预料。

在第四章中，我们通过提供源自问题知识的领域特定的启发函数来弥补无信息搜索算法的糟糕性能。我们可以不用领域特定的知识就有效地解决CSP问题。替代地，我们可以找到通用方法，提出以下问题：

1．下一步该给哪个变量赋值，按什么顺序来尝试它的值？

2．当前的变量赋值对其它未赋值变量意味着什么？

图5.4 用简单的回溯法生成的图5.1中的地图染色问题的部分搜索树

3．当一条路径失败时——也就是，到达一个变量没有合法值的状态——搜索能在后面的路径中避免重复这样的失败吗？

后面的部分将依次回答这些问题。

图5.5 不同CSP算法在不同问题上的比较。算法从左向右是简单的回溯算法，用MRV做启发式的回溯算法，前向检验算法，用MRV的前向检验算法，最小冲突的局部搜索算法。图中每栏中列出的值是求解该问题需要的相容性检验的平均次数（超过五次运行）；注意所有的数字中除了右上角的两个以外都在“千”（K）的数量级上。括号中的数字表示在分配的次数内没有找到解。第一个问题是美国50个州的四色问题。其余问题出自Bacchus和van Run（1995）的著述，表1。第二个问题是统计求解从2到50的全部n皇后问题需要的检验次数。第三个问题是“斑马问题”，在习题5.13中有描述。最后两个是人工的随机问题。（这两个问题没有运行最小冲突算法。）结果表明用MRV的前向检验算法在所有的问题上都比其它回溯算法要好，但是有时候没有最小冲突的局部搜索好