Skip to content

双监视文字

Two-watched-literals scheme · Two literal watching · Watched literals

每个非单位子句监视两个文字,只在监视文字变假时扫描并维护单位传播状态。

条目类型
算法

形式陈述

双监视文字为每个长度至少为二的子句选择两个不同文字 w1,w2,并为每个文字 维护“正在监视 的子句”列表。当 trail 新增文字 时,只有监视 ¬ 的子句可能因这次赋值而新近成为单位或冲突,算法逐一处理这些子句。单位子句通常在根队列中单独登记,空子句立即报告冲突。

处理一个刚变假的 watch w1 时,算法先在其余非监视文字中寻找一个当前不为假的候选 u。找到后,把 watch 从 w1 移到 u,子句仍不需要传播。若找不到,所有非监视文字都已为假,此时另一 watch w2 完整决定状态:w2 为真则子句已满足;未赋值则子句为单位并传播 w2;为假则发生冲突。

真实不变量不是“两只 watch 始终都非假”。单位子句状态恰有一只 watch 未赋值、另一只为假;已满足子句也允许一只 watch 为假。操作不变量是:任何子句若会因新赋值成为单位或冲突,必有一只被监视文字刚刚变假,从而该子句会被访问,并在找不到替代者时正确处理。由此它实现的仍是同一单位传播闭包。

直觉

朴素传播每次都问所有子句“你现在只剩一个出口吗”。双监视反过来让子句只在一个关键出口关闭时醒来。只要还能把观察点移到另一个未关闭出口,就无需知道其他文字的精确状态;当再也移不动时,另一观察点便是最后出口或冲突证据。

Watch 是对子句状态的惰性索引,不是对两个“最重要文字”的语义判断。它们可随搜索改变,且不影响模型集合。恰因为索引只响应从未赋值到假的收紧动作,回溯把假值恢复为未赋值时无需把 watch 移回历史位置:约束只会放松,不会漏掉新单位或新冲突。

例子与边界

取子句

C=(a¬bcd),

初始监视 a,¬b。赋值 a=0 后,a 变假;扫描发现 c 未赋值,于是把第一只 watch 移到 c。随后赋值 b=1¬b 变假;扫描发现 d 未赋值,把第二只 watch 移到 d。现在 watches 为 c,d,而 a,¬b 已假。

再赋 c=0 时,处理 watch c。非监视候选 a,¬b 都假,找不到替代者;若 d 未赋值,C 成为单位子句并传播 d=1;若此前已有 d=0,两只 watches 及所有其他文字均假,报告冲突;若 d=1,子句已满足。三个分支直接覆盖处理规则,没有假设“两只 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。
关系图谱5 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

被这些条目使用

实现的抽象