问题的结构

5.4 问题的结构

在这一节中，我们考虑以什么方式利用问题的结构，如约束图所表示的，能快速地找到解。这里的多数方法都是很通用的并且也适用于CSP以外的其它问题，例如概率推理。毕竟我们处理实际世界问题时有希望的唯一办法就是将它分解为很多子问题。我们用识别问题结构的眼光再来看看图5.1（b），可以看到一个事实：Tasmania和大陆不相连[24]。直观上来说，显然对Tasmania染色和对大陆染色是独立的子问题——任何对大陆区域染色的解和任何对 Tasmania 染色的解合并起来都得到整个地图的一个解。独立性可以简单地通过在约束图中寻找连通域来确定。每个连通域对应于一个子问题CSPi。如果赋值Si是CSPi的一个解，那么∪iSi是∪iCSPi的一个解。为什么这是很重要的？考虑以下问题：假设每个CSPi有总共n个变量中的c个变量，c是一个常数。那么就有n/c个子问题，解决每个子问题最多花费dc步工作。因此总的工作量是O(dcn/c)，是n的线性函数；而不进行分解的话，总的工作量是O(dn)，是n的指数函数。我们给一个更具体的例子：将一个n = 80的布尔CSP问题分解成4个c = 20的子问题，会使最坏情况下的时间复杂度从宇宙寿命那么长的时间减少到不到一秒。

完全独立的子问题是很诱人的，但是很少见。在多数情况下CSP的子问题之间是有联系的。最简单的情况是当约束图形成一棵树时：任何两个变量最多通过一条路径连通。图5.10（a）显示了一个示意性的例子[25]。我们将证明任何一个树状结构的CSP 问题可以在变量个数的线性时间内求解。算法的步骤如下：

1．任选一个节点作为树的根节点，从根节点到叶节点按顺序排列，每个节点的父节点都在它的前面。（见图 5.10（b）。）按顺序把它们标为变量 X1，…，Xn。现在除了根节点之外的每个变量都只有一个父变量。

2．令j从n到2，在弧(Xi,Xj)上应用弧相容算法，其中Xi是Xj的父变量，从DOMAIN[Xj]中删除必要的值。

3．令j从1到n，赋给变量Xj与给变量Xi赋的值相容的任何值，其中Xi是Xj的父变量。

这里有两个关键点需要注意。首先，在第2步之后这个CSP是有向弧相容的，因此第3步中的赋值不需要回溯。（参见第5.2.2节中“约束传播”对k相容问题的讨论。）其次，通过在第2步中应用弧相容算法进行反向检验，算法保证任何被删掉的值不会危及已经处理过的弧的相容性。完整算法的时间复杂度是O(nd [26])。

现在我们已经有了一个对树状结构的高效算法，我们可以考虑更一般的约束图是否能简化成树的形式。有两种基本的方式：一种是基于删除节点的，一种是基于合并节点的。

图5.10 （a）树状结构CSP的约束图。（b）与以A为根节点的树相容的变量的线性排序

第一种方法涉及先对其中的某些变量赋值，使剩下的变量能够形成一棵树。考虑澳大利亚的约束图，如图5.11（a）所示。如果我们能删除South Australia，这个图就会变成像（b）中的一棵树。幸运的是，我们可以做到这个（只是在图中删除，而不是真的从大陆上删除），通过给变量SA固定的值并且从其它变量的值域中删除任何与为SA选中的值不相容的值。

图5.11（a）图5.1的原始约束图。（b）删除SA之后的约束图

现在，在删除了SA和它的约束之后，CSP问题的每个解都将与为SA选择的值是相容的。（这对二元 CSP 问题是可行的；在高阶约束问题中情况会更复杂。）因此，我们可以用前面给出的算法求解剩余的树，并由此得到整个问题的解。当然，在一般情况下（与地图染色相反）为 SA 选择的值可能是错误的，因此我们将需要尝试所有的值。一般算法如下：

1．从VARIABLES[csp]中选择一个子集S，使得约束图在删除S之后成为一棵树。S称为环割集。

2．对于满足S所有约束条件的S中变量的每个可能赋值，

（a）从剩余变量的值域中删除与S的赋值不相容的值，并且

（b）如果去掉S后的剩余CSP有解，把解和S的赋值一起返回。

如果环割集的大小为c，那么总的运行时间为O(dc⋅ (n − c)d2)。如果约束图“近似于一棵树”，那么c将会很小，并且比直接回溯将有巨大的节省。然而在最坏情况下，c可能大到(n − 2)。找到最小的环割集是一个 NP 难题，但是对这个任务已知有些高效的近似算法。算法的总体方法叫做割集调整；我们将在第十四章再次见到，在那里用它来进行概率推理。

第二个方法是建立在构造约束图的树分解的基础上的，它把约束图分解为相关联的子问题集。每个子问题将会独立地求解，再把得到的结果合并起来。像多数分治算法一样，如果没有一个子问题特别大，它的效果就会很好。图5.12给出了地图染色问题的树分解，形成5个子问题。一个树分解必须满足以下3个条件：

• 每个原始问题中的变量至少在一个子问题中出现。

• 如果两个变量在原问题中由一个约束相连，那么它们至少同时出现在同一个子问题中（连同它们的约束）。

• 如果一个变量出现在树中的两个子问题中，它必须出现在连接这些子问题的路径上的所有子问题里。

前两个条件保证了所有的变量和约束都在分解中表示出来。第三个条件看起来更技术性，但是它只是反映了任何给定的变量在每个子问题中必须取值相同的约束；子问题之间的连接强制了这个约束。例如，在图5.12中SA出现在连接起来的所有4个子问题中。你可以从图5.11验证这种分解是有意义的。

图5.12 图5.11（a）中约束图的树分解

我们独立地求解每个子问题；如果其中任何一个无解，那么原始问题就无解。如果我们能求解所有的子问题，接下来我们就要尝试构造一个全局解。首先，我们把每个子问题视为一个“大变量”，它的值域是这个子问题的所有解的集合。例如，图5.12中最左边的子问题是一个有3个变量的地图染色问题，因此有6个解——其中一个是{WA = red，SA = blue，NT = green}。然后我们可以用前面给出的对树的有效算法来求解连接这些子问题的约束问题。对于子问题之间的约束仅仅需要保持它们的共享变量的相容性。例如，对第一个子问题给定的解{WA = red，SA = blue，NT = green}，下一个子问题的相容解只能是{SA = blue，NT = green，Q = red}。

一个给定的约束图允许有多种树分解；在选择分解的时候，目标是分解出来的子问题越小越好。图的树分解的树宽比最大的子问题的大小少 1；图自身的树宽定义为它所有树分解的最小树宽。如果一个图的树宽为w，并且给定相应的树分解，那么这个问题的时间复杂度是O(n dw+1)。因此，约束图树宽有界的CSP问题是多项式时间内可解的。不幸的是，找到最小树宽的树分解是一个NP难题，不过实际上有一些很可行的启发式方法。