困难的满足性问题

7.6.3 困难的满足性问题

我们现在来看DPLL和WALKSAT在实际中表现如何。我们对难题尤其感兴趣，因为容易的问题可以用任何旧算法来解决。在第五章中，我们看到关于特定种类问题的一些令人惊讶的发现。例如，n皇后问题——被认为对于回溯搜索算法是相当棘手的——对于局部搜索方法，比如最小冲突法，却非常的容易。这是因为解非常稠密地分布在赋值空间上，任意初始赋值都可以保证在其附近存在某个解。故此n皇后问题易于求解，因为它是约束过少的。

当我们考虑合取范式形式的可满足性问题的时候，约束过少的问题是一个具有相对较少的子句来约束变量的问题。例如，以下是随机生成的[13]具有5个符号和5个子句的3-CNF语句：

(¬D∨¬B∨C)∧(B∨¬A∨¬C)∧(¬C∨¬B∨E)

∧(E∨¬D∨B)∧(B∨E∨¬C)

32个可能的赋值中有16个是此语句的模型，因此，平均起来它只需进行两次随机猜测就可以找到一个模型。

那么难题在哪里？推测起来，如果我们增加子句的数量，维持符号的数量不变，可以使得问题受到的约束更多，解更难被找到。令m为子句的数量，n为符号的数量。图7.18（a）显示了一个随机的3-CNF语句可满足的概率，表示为子句/符号之比m/n的函数，其中n固定为50。正如我们所预期的，对于数值比较小的m/n，该概率接近于1，而对于大数值的m/n，概率接近于0。在m/n = 4.3附近，概率急剧下降。在这个临界点附近的CNF语句可描述为“近似满足的”或“近似不可满足的”。这是不是难题所在？

图7.18（b）显示了DPLL和WALKSAT在这一临界点附近的运行时间，这里我们把注意力限定在可满足问题上。有3件事情是清楚的：第一，临界点附近的问题比其它的随机问题更加难解决；第二，即使是最难的问题，DPLL也相当有效——与真值表枚举的步数250≈ 1015相比较，它的平均步数为几千；第三，在整个范围内，WALKSAT比DPLL更快。

图7.18 （a）图中显示了n=50个符号的随机3-CNF语句的可满足概率，作为子句/符号比m/n的函数。（b）DPLL和WALKSAT处理n=50的100个可满足的随机3-CNF语句时的中值运行时间图，在临界点附近m/n的一个狭小范围内

当然，这些结果只是对随机生成的问题而言的。实际问题无需与随机问题具有相同的结构——按照正文字和否定文字的比例、子句中连接符的密度等等来说。不过，实际中，WALKSAT 和相关算法也非常适合求解实际问题——通常和针对那些任务的最好的专用算法一样好。含有成千个符号和上百万子句的问题由诸如CHAFF这样的求解程序进行常规处理。以上观察结果暗示了，最小冲突启发式和随机行走行为的某些组合能为多数需要组合推理的场合下的问题求解提供一种通用能力。