动机
CNF 公式可能不可满足,但我们仍然可以寻求一个尽可能多地满足公式的赋值。在带权 MAX-SAT 中,每个子句带有一个非负权重,目标是使被满足子句的总权重最大。随机赋值给出一个简单的基线:每个非空子句被满足的概率至少为二分之一。
这一期望论证也导出一个确定性算法。逐个固定变量,每次选取一个不会使最终得分的条件期望下降的取值。这是条件期望法的一个例子:概率性的存在性证明变成了一列明确的选择。
定义
定义 6.7.1
(带权 MAX-SAT 实例与得分)
输入是布尔(Boolean)变量上的有限子句列表,以及非负有理权重 。子句是文字出现的析取。若子句中至少有一个文字为真,则其得分等于其权重,否则得分为零。一个赋值的得分是所有被满足子句的权重之和, 是所有赋值中的最大得分。
同时含有 与 的子句称为重言子句,它总是被满足。同一文字的重复出现不改变子句的真值;计算相异变量个数时应去除重复。空子句总是为假。在主要定理中,我们假设每个非重言子句都非空;空子句对任何赋值的贡献均为零,故可以删去。
定义 6.7.2
(均匀随机赋值与总权重)
让每个变量独立且均匀地取假或真。令 ,求和范围为所有非空子句(包括重言子句)。在主要假设下,它是 的一个上界。
定理
定理 6.7.3
(二分之一近似)
对于权重非负且不含空子句的带权 MAX-SAT,均匀随机赋值的期望得分至少为 。一个确定性的多项式时间条件期望算法所得的得分至少为 。
定理 6.7.4
(恰好三个文字时的改进)
若每个子句恰好含有三个文字,且这三个文字属于三个相异变量,并且没有子句是重言子句,则同样的随机赋值的期望得分为 。条件期望法可得到一个确定性赋值,其得分至少为 。
证明
得分的期望
证明
(均匀赋值的期望得分)
含有 个相异变量的非重言子句为假,当且仅当其每个文字都为假。这些相异变量所需的取值相互独立,所以子句为假的概率是 ,被满足的概率是 。重言子句被满足的概率为一。
令 为子句 被满足的指示变量。它的加权期望贡献是 。由期望的线性性,
各子句的指示变量不必相互独立:不同子句可以共享变量。线性性并不要求它们相互独立。权重非负,保证了把每个满足概率换成其下界后不等式仍然成立。由于没有任何赋值的得分能超过 ,所以这个值至少为 。
当每个子句恰好含有三个相异变量且不是重言子句时,其为假的概率恰为 。每个子句被满足的概率都是 ,所以期望总得分恰为 。同样的上界 给出近似保证。这个值是期望值;个别赋值的得分可能更低,也可能更高。
证明透视
独立性只用在子句之内
这里结合了两种概率推理,其中只有一种需要独立性。在单个子句之内,相异变量的公平比特相互独立,因此子句为假的概率恰为 :使其为假的赋值把 个变量各定为一个值,概率相乘。重复的变量会破坏这一点,因为这时各文字并不独立;子句 为假的概率是 ,而不是 。在各子句之间只用到期望的线性性,它对指示变量之间的任何相依关系都成立,所以共用变量不构成代价。非负权重在最后一步起作用:把每个 换成下界 ,只有在每个权重都非负时才保持不等式。
用条件期望去随机化
证明
(条件期望永不下降)
按任意固定的顺序处理变量。假设已有一些变量被固定。计算在下一个变量取假、其余变量仍保持均匀随机时最终得分的期望;同样计算该变量取真时的期望。当前的条件期望是这两个数的平均值,因为下一个变量仍是一个公平的独立比特。至少有一种取法,其条件期望不小于当前值。把变量固定为这样的取值(若相等则任选),然后重复这一步骤。
所有变量都被固定之后,不再有任何随机性。此时的条件期望就是所构造赋值的实际得分。它不小于最初的期望,这就证明了两个确定性保证。
这两个期望可以由子句直接算出。已被满足的子句贡献其全部权重。若一个子句的已固定文字全部为假,且还有 个未赋值的相异变量,则当 时它贡献 ,当 时贡献零。重言子句贡献其全部权重。这些量都是有理数,可以精确求和。若有理输入权重以二进制表示,则直接通分并重复扫描子句,所用的位数与运算次数都是多项式的;2 的幂因子的指数至多为变量个数。
例题详解
例题 6.7.5
(单个子句)
对于无权子句 ,八个赋值中恰有一个使三个文字全为假。均匀赋值的期望得分是 。最优值为一,任何至少有一个变量为真的赋值都能达到它。
例题 6.7.6
(一次条件选择)
对于两个无权子句 与 ,初始期望得分为 。令 为真,期望得分为 ;令 为假,则为 。条件期望法选择 。接着它选择 ,最终得分为二。
例题 6.7.7
(相反的单位子句)
对于权重各为一的 与 ,每个赋值都恰好满足一个子句。期望得分为一,最优值也为一。上界 并不总是可以达到,所以用 作的近似证明可能偏保守。
例题 6.7.8
(重复的文字不增加随机性)
子句 在 为假时为假,概率是 ,而不是 。去掉重复后它就是一个单位子句。它不满足 结论中“恰好三个相异变量”的假设。
常见错误
反例模式
期望不是对每一次运行的保证
对于单个子句 ,随机赋值的期望得分是 ,但赋值 的得分为零。确定性的条件期望过程选取的是条件期望得分足够高的取值;而一次未经检验的随机运行不一定能达到该期望。
常见错误
(数文字出现次数而不是相异变量)
因子 要求每个子句含有三个相异变量。若某个变量重复出现,三个文字出现次数并不够。重言子句总是被满足,可以单独处理,但其满足概率是一,而不是恰好 。
常见错误
(忽略权重的符号)
非负权重很重要。若某个子句的权重为负,提高满足该子句的机会反而可能降低得分,而且 也不再以同样的方式成为最优值的上界。该定理不涵盖负权重。
理解确定性的选择
部分赋值把每个非重言子句分成三种情形。若某个已固定的文字为真,则该子句必然有贡献。若所有文字都已固定为假,则它不可能有贡献。否则,已固定的文字全为假,剩下的相异变量必须全部取各自唯一的使文字为假的值,子句才会失败。这就给出了算法所用的条件贡献。
条件期望并不是靠猜测未来来估计某个贪心赋值最终的得分。它是对其余变量所有补全方式取平均。下一个变量的两个分支把这些补全分成概率相等的两半,所以其中一个分支的平均值不小于当前的平均值。重复这一论证,就能保证所保证的值不会下降。
权重和子句都可以重复。它们的贡献按输入列表的规定分别计数。共享变量使子句之间产生依赖,但由期望的线性性,逐个计算条件贡献再求和仍然成立。
何时达到 的界
取三个变量 ,并包含所有八个子句,它们由独立地选择每个变量以正文字还是负文字出现得到。每个子句的权重为一。每个子句含有三个相异变量,且 。
对任意赋值,八个子句中恰有一个为假:在每个位置选取该赋值使其为假的文字即可。其余七个子句都被满足。因此每个赋值的得分都是七,最优值是七,而随机赋值的期望得分恰为 。这个例子说明,在恰好三个文字的假设下,对均匀随机赋值而言,相对于总子句权重的保证一般无法改进。它并不说明相对于最优值的近似比是 ,因为这里每个赋值都是最优的。
概念视角组合
数一数使子句为假的赋值
期望也可以看成计数。含 个相异变量的非重言子句,在 个变量的 个赋值中恰有 个使它为假,所以全体赋值的平均得分是 。在上面的例子中,八个子句各自恰被一个赋值弄假,而每个赋值恰好弄假一个子句,两边的数目恰好相符。
以 表示的保证与以 表示的保证,二者的区别很有用。不等式 把前者转化为后者,但当这些子句无法全部满足时,这样做会损失信息。更精细的近似分析可以使用比总权重更好的 上界。
一个带权的条件计算
考虑权重为二的子句 、权重为三的子句 和权重为一的子句 。起初它们的期望贡献分别为 、 和 ,总和为 。若 为真,第一个子句贡献二,第二个子句期望贡献 ,第三个子句期望贡献 ,总计四。若 为假,第一个子句贡献零,第二个贡献三,第三个期望贡献 ,总计 。四与 的平均值确实是 。
选取 。然后若选 ,则前两个子句被满足,得分为五;若选 ,则第一和第三个子句被满足,得分为三。算法选择真,输出得分五,超过了它的初始期望。这一计算没有假设第二和第三个子句的指示变量相互独立;它们的条件期望贡献只是直接相加。
精确算术与输入规模
对于部分赋值,幂 的分母,其二进制长度至多为一加上未赋值变量的个数。每个输入权重是分子分母均为二进制的有理数。把各输入分母相乘,得到的公分母的位长至多是它们位长之和。再包含所需的最大的 2 的幂,位长至多再增加变量个数。
因此,条件和的计算与比较可以用多项式位长的整数完成。朴素的实现可能对每个变量的两种取值都重新扫描每个子句;这对于显式输入规模来说仍是多项式的。更高效的增量更新是可能的,但要证明存在多项式时间的去随机化并不需要它们。
总结
均匀赋值满足每个非空子句的概率至少为二分之一,满足每个恰含三个相异变量的子句的概率为八分之七。条件期望法逐个固定变量,且不使期望总得分下降,从而在所述的非负权重模型下得到确定性的近似保证。
练习
快速检查
(在均匀赋值下,含有四个相异变量的非重言子句为假的概率是多少?)
解答 · 答案
使四个文字全为假的赋值是唯一的,其概率为 ,所以满足的概率是 。
快速检查
(对于权重相等的子句 与 ,每个赋值的得分是多少?)
解答 · 答案
两个子句中恰有一个被满足,所以当每个权重为一时,得分为一。尽管总子句权重为二,最优值仍是一。
快速检查
(为什么期望的证明不要求不同子句相互独立?)
解答 · 答案
得分是子句指示变量之和。无论是否存在依赖,期望对有限和都可分配;只需要计算每个单独子句的概率。
快速检查
(为什么条件期望算法总能选出一个不使当前期望下降的取值?)
解答 · 答案
当前期望是取假分支与取真分支的条件期望的平均值。两个实数中至少有一个不小于它们的平均值,所以选择该分支不会使值下降。