“朴素实现会在每次赋值后扫描全部子句。双监视文字用每个子句的两个观察点实现同一推理接口,只访问监视刚变假的文字的子句;它改变索引与扫描成本,不改变哪些单位后果有效。Horn 公式等受限类别上,…”
形式陈述 ​
双监视文字为每个长度至少为二的子句选择两个不同文字
处理一个刚变假的 watch
真实不变量不是“两只 watch 始终都非假”。单位子句状态恰有一只 watch 未赋值、另一只为假;已满足子句也允许一只 watch 为假。操作不变量是:任何子句若会因新赋值成为单位或冲突,必有一只被监视文字刚刚变假,从而该子句会被访问,并在找不到替代者时正确处理。由此它实现的仍是同一单位传播闭包。
直觉
朴素传播每次都问所有子句“你现在只剩一个出口吗”。双监视反过来让子句只在一个关键出口关闭时醒来。只要还能把观察点移到另一个未关闭出口,就无需知道其他文字的精确状态;当再也移不动时,另一观察点便是最后出口或冲突证据。
Watch 是对子句状态的惰性索引,不是对两个“最重要文字”的语义判断。它们可随搜索改变,且不影响模型集合。恰因为索引只响应从未赋值到假的收紧动作,回溯把假值恢复为未赋值时无需把 watch 移回历史位置:约束只会放松,不会漏掉新单位或新冲突。
例子与边界
取子句
初始监视
再赋
复杂度边界需要按实际 literal inspections 讨论。一次长子句扫描可能访问很多文字;缓存上次扫描位置可避免每次从头开始,但回溯、restart 和反复迁移仍影响总成本。不能把并查集的近常数摊还界套到 watch,也不能仅凭“每子句两个指针”宣称整轮传播严格线性。删除子句时还必须从两个 watch lists 安全摘除,悬空索引会造成漏传播或访问已释放内存。
推论与应用
双监视把传播成本集中到受当前赋值直接威胁的子句,是 CDCL 能频繁到达传播不动点的关键工程机制。二元子句可直接监视两个文字并在其中一个变假时传播另一个;对极多二元子句,专用 implication lists 还能减少通用扫描开销,但仍需保持相同逻辑结果。
在增量 SAT 中,assumption 撤销不要求恢复 watch,新增子句却必须初始化两个合法观察点并立即检查它在当前 trail 下是否已经单位或冲突。证明日志通常不记录 watch 移动,因为它们没有逻辑含义;checker 只验证传播或学习所依赖的子句,而求解器实现测试则应另行覆盖 watch-list 完整性。
参考资料
- Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik, “Chaff: Engineering an Efficient SAT Solver,” DAC, 2001, pp. 530–535。
- Ian P. Gent, “Optimal Implementation of Watched Literals and More General Techniques,” Journal of Artificial Intelligence Research 48, 2013, pp. 231–252。
- Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, eds., Handbook of Satisfiability, 2nd ed., IOS Press, 2021, Chapter 4。