动机
局部搜索可以通过改变一个变量来修复一个未被满足的约束,但这一修复可能破坏原本已被满足的约束。对于 2-SAT,只要公式可满足,一个简单的随机游走就能在多项式期望时间内找到满足赋值。其分析把当前赋值与一个固定的满足赋值作比较,而算法本身无需知道这个赋值。
在每一个未成功的步骤中,向满足赋值靠近的概率至少为二分之一。我们并不假设各步相互独立,而是使用一个具有负条件漂移的距离势函数。再通过有限的时间上限和相互独立的重启,把期望时间的论证转化为单侧错误的概率保证。
定义
模型与算法
定义 5.3.1
(2-CNF 公式)
2-CNF 公式是若干子句的合取,每个子句至多含两个文字。文字是一个布尔(Boolean)变量或其否定。去掉重言子句以及子句内重复的文字;若出现空子句,则立即报告不可满足。若没有剩余子句,则返回任意赋值。在其余情形下,令 为变量个数,并设每个子句含一个或两个互异且互不相反的文字。
定义 5.3.2
(随机游走搜索)
从任意赋值出发。只要当前赋值不满足该公式,就选取任一当前未被满足的子句,在其变量中均匀随机地选取一个,并翻转该变量。子句的选取可以依赖于整个过去;而在该子句的变量之间所作的随机选择,在给定历史的条件下是全新且均匀的。若当前赋值满足所有子句,则返回该赋值。
定理
定理 5.3.3
(可满足公式上的期望搜索时间)
若公式有满足赋值,则从任一初始赋值出发,随机游走首次到达某个满足赋值之前的期望翻转次数至多为 。
定理 5.3.4
(带上限的单侧随机化过程)
让游走至多运行 次翻转,并检查所得赋值。对于可满足公式,该次运行未能找到满足赋值的概率至多为 。使用全新且相互独立的随机选择重复 次运行,可使失败概率至多为 。即使公式不可满足,所返回的任何赋值也都可被验证为满足赋值。
若所有运行均失败,带上限的过程返回“未找到”。该结果不是不可满足性的证明。定理只在存在满足赋值时才界定其概率。
证明
固定的满足赋值带来进展
为便于分析,固定任一满足赋值 。令 为当前赋值与 之间的汉明(Hamming)距离,即两者取值不同的变量个数。算法并不知道 ,也从不计算 。
引理 5.3.5
(向固定解靠近的进展)
设 为一个满足赋值, 为当前赋值与 之间的汉明距离。在到达满足赋值之前的每一步,在给定整个历史的条件下,下一次翻转使 减一的概率至少为 ,否则使它加一。若所选子句只含一个变量,或 ,则减小的概率为一。
证明
(为什么假子句带来进展)
在一个不满足公式的赋值处,所选子句为假。由于 满足该子句,该子句中至少有一个文字在当前赋值与 之间由假变为真。因此它的变量与 不同。一个子句至多含两个互异变量,所以均匀翻转使 减小的条件概率至少为二分之一。任何被翻转的变量要么与 一致,使距离增加一;要么与 不一致,使距离减少一。对于单文字子句,距离以概率一减小。
若 ,则每个变量都与 不同,故每一种可能的翻转都使距离减小。若 ,则当前赋值等于 ,已经是满足赋值。距离过程可能依赖于先前的子句选择,但在终止之前,该条件下界对每一种允许的历史都成立。
势函数及其条件漂移
证明
(借助势函数估计期望时间)
对 定义 。它非负且至多为 。对于 ,令 。则
若距离减小的概率为 ,则条件期望变化至多为
在 处,距离以概率一减小,且 。因此,在找到满足赋值之前的每一步,势函数的条件期望至少下降一。
令 为首次到达满足赋值的时间(以翻转次数计),并在该时间之后冻结过程。对前 次可能的翻转累加条件漂移并取期望,得到
左侧非负,故 。令 趋于无穷并利用单调收敛定理,得 。特别地,游走几乎必然到达某个满足赋值。它可能更早到达一个不同于固定的 的满足赋值;在第一个满足赋值处冻结只会对论证有利。
证明透视
势函数与停时各自的作用
每个假设都恰在一处使用。子句大小至多为二,给出减小的概率 ;对 有 ,于是 ;在 处则必然减小。不显然的一步是选用二次势函数。距离本身的期望变化为 ,公平的一步为零,对终止性毫无说明;而凹函数 把每个公平的一步变成恰为 的漂移。
论证通过停时收束。对每个有限的 , 的界都成立; 的非负性把它变成 的界;再用单调收敛令 。证明没有用到 的马尔可夫(Markov)性,只用到在每个历史之下的漂移界。
漂移界是关于条件期望的陈述,并不是关于单次翻转的陈述。
反例模式
靠近的机会均等并不意味着单调进展
一次翻转可能增大与固定解的距离。例如,当一个为假的双文字子句含有一个与 一致的变量和一个与 不一致的变量时,均匀翻转以各二分之一的概率向任一方向移动。具体地,在下面的两个变量的例题中,游走位于 时假子句为 ;翻转 得到 ,它与解 的距离为 ,而原来的距离是 。证明所用的是弯曲势函数的期望下降,而不是声称每次翻转都改进赋值。
为什么这个势函数的形状恰到好处
考虑距离为 的理想化无偏游走,设距离零为吸收态,距离 总是移动到 。若 是其到达零的期望时间,则一步方程给出
其中 。代入 可满足所有这些方程。这一观察启发了势函数的选取:它正是参照游走的期望时间的精确解;而对于这个递增的凹函数,向下移动的可能性不低于参照游走的过程,其条件期望变化不会更大。
证明并不要求实际的距离过程是马尔可夫链。两个历史可能具有相同的距离,却有不同的当前赋值和不同的可用假子句。条件漂移不等式对每个这样的历史都成立,所以累加仍然有效。若不加论证地把距离当作独立的对称随机游走,就会忽略这一区别。
参照方程也解释了为什么线性距离势函数在此不够用:公平的一步其距离的期望变化为零,而二次势函数的二阶差分贡献严格为负。子句大小的上界对这一特定论证同样至关重要。若有三个互异文字,一个假子句可能只需有一个变量与固定的满足赋值不同,从而使减小的概率低至三分之一。例如,在 处子句 为假,而满足赋值 仅在 上不同。在其三个变量中均匀选择,向该所选解靠近的概率为三分之一。这并不证明随机游走对 3-SAT 无益;它说明的是为何二分之一漂移的证明不能原封不动地照搬。
最后,势函数可能停在正值上,因为游走可能到达一个不同于分析中所固定的那个满足赋值。裂项求和的界只要求停止后的势函数非负。要求它恰为零,会增加一个不必要且一般而言不成立的假设。
从期望时间到有限上限
证明
(马尔可夫不等式与重启)
马尔可夫不等式给出 。检查初始赋值以及每次翻转之后的赋值,可确保在上限之前到达的满足状态被返回。若一次运行失败,则从任意赋值出发,使用全新的随机选择重新开始。同样的条件界适用于每次运行,所以全部 次运行都失败的概率至多为 。
对于不可满足的公式,没有任何赋值能通过显式的子句检查,所以该过程绝不会返回虚假的满足赋值。它的“未找到”结果无法区分不可满足的公式与可满足公式上运气不佳的一次运行。这是一种随机化搜索保证,而不是不可满足性的独立证明。
设有 个子句,直接的实现为找到一个未被满足的子句而检查所有子句,每次翻转需要 时间,初始化一个赋值需要 时间。在文字求值为常数时间的假设下, 次带上限的运行在预处理之后共需 时间。在双文字子句中选择变量使用一个公平比特;单文字子句则无需随机比特。一次运行至多使用 个这样的比特。2-SAT 存在更快的确定性算法;本章分析的是随机游走方法,并不声称它是最快的方法。
例题详解
例题 5.3.6
(两个变量的游走)
考虑 ,其唯一的满足赋值为 。从 出发,第一个子句为假。翻转任一变量得到 或 ,各以二分之一的概率出现。从任一状态出发,唯一的假子句都含有一个通向 的翻转和一个回到 的翻转。因此在最初两次翻转内成功的概率为 。
例题 5.3.7
(单位子句)
对于公式 ,从 出发,选取唯一的变量并把它翻转为一。游走在一次翻转内成功。条件减小概率为一,强于下界二分之一。
例题 5.3.8
(不可满足的实例)
对于 ,没有任何赋值能同时满足两个子句。在任一赋值处恰有一个单位子句为假,若无上限,游走将永远翻转 。带上限的过程返回“未找到”;它从不声称存在满足赋值。
例题 5.3.9
(重启放大成功概率)
若对一个可满足公式独立运行四次,每次上限为 次翻转,则四次运行全部失败的概率至多为 。当找到满足赋值时,运行可能提前停止。这个估计是最坏情形的界,而不是对每个公式都精确的失败概率。
常见错误
常见错误
(假子句不必所有变量都与解不同)
一个假子句含有与某个特定解不同的变量,并不意味着该子句中的每个变量都与之不同。均匀选取一个变量翻转,可能远离该解。证明只需要“减小”的条件概率至少为二分之一。
常见错误
(期望时间并不是每次运行的上界)
期望时间的结果并不对每一次运行提供确定性的上界。随机选择可能反复回到相同的赋值。上限给出一个带有明确失败概率的有限过程;重复运行会降低该概率,但在有限次运行之后并不能使之为零。
常见错误
(搜索失败并不证明不可满足)
最后,随机搜索失败并不证明公式不可满足。在此算法中,只有返回的赋值才是证书。另一个确定性的 2-SAT 算法可以判定这两种答案。
总结
对于可满足的 2-CNF 公式,每个假子句都含有一个与固定解不一致的变量。随机翻转使汉明距离减小的条件概率至少为二分之一。势函数 在找到满足赋值之前,期望漂移至多为负一,由此得到 的期望翻转次数上界。加上限并重启,便得到一个有限的单侧随机化搜索过程。
练习
快速检查
(对于公式 ,从 出发,当 时,计算翻转次数及势函数的下降量。)
计算 。
解答 · 答案
一次翻转把 变为一并满足该子句。与解的距离由一变为零;,,所以势函数下降一。
快速检查
(在两个变量的例题中,计算从 出发在两次翻转内成功的概率。)
列出两种等可能的第一次翻转,并分别跟进。
解答 · 答案
第一次翻转之后,状态为 或 。在两种情形下,对该假子句的两种等可能翻转中,都有一种到达 。因此概率为 。
快速检查
(若每次带上限的运行失败的概率至多为二分之一,需要多少次独立运行才足以使失败概率至多为 ?)
解 。
解答 · 答案
五次运行即足够,因为 。
快速检查
(解释为什么在一次带上限的运行失败后返回“不可满足”是不合理的。)
在可满足公式上运气不佳的一次运行,会不会看起来一样?
解答 · 答案
可满足的公式也可能出现运气不佳的翻转序列,使得在上限之前没有到达满足赋值。算法只能控制这种失败的概率;它并不产生不存在任何满足赋值的证书。