💻 computer science

Generalizing CDCL with Graph Backtracking

本文提出了一种新颖且可靠的基于 CDCL 的 SAT 求解方案——图回溯，该方案通过利用蕴含图和用户定义的权重函数来最小化未赋值文字，从而推广了时序回溯与非时序回溯，正如 NapSAT 求解器所证明的那样，此举减少了传播次数并提升了运行效率。

原作者： Robin Coutelier, Thomas Hader, Laura Kovács

发布于 2026-05-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Robin Coutelier, Thomas Hader, Laura Kovács

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在尝试拼凑一个巨大而复杂的拼图，每一块都必须严丝合缝，否则整幅画面就会分崩离析。在计算机科学领域，这被称为SAT 求解（布尔可满足性问题）。计算机试图为成千上万个变量分配“真”或“假”，以使一个逻辑公式成立。

当计算机犯错并陷入死胡同（即“冲突”）时，它必须回退并改变主意。本文介绍了一种更聪明的“回退”方式，称为图回溯。

以下是使用简单类比进行的分解：

1. 旧方法：“撤销”按钮与“后退”按钮

在这篇论文之前，计算机主要使用两种方法来修正错误：

非时序回溯（NCB）： 这就像一个非常激进的“撤销”按钮。如果你在步骤 10 犯了错，计算机会检查逻辑并说：“哦，步骤 3 才是根源。”它会跳回步骤 3，并擦除步骤 3 到步骤 10 之间发生的所有事情。这很快，但很浪费。即使步骤 4 到 9 实际上没问题且并未导致问题，它也会将它们丢弃。
时序回溯（CB）： 这更像是一个标准的“后退”按钮。它只退回到你做的最后一件事（步骤 10）并再次尝试。它更安全，因为它不会丢弃有效的工作，但可能很慢，因为它可能不得不重复做同样的工作很多次。

问题所在： 这两种方法都很僵化。它们遵循严格的“栈”顺序（就像一摞盘子：你只能拿走最上面的那个）。它们无法说：“让我们保留最上面的 5 个盘子，但换掉第 3 个。”

2. 新想法：图回溯（“手术式”方法）

作者提出了图回溯，它将拼图视为依赖关系网（图），而不是一摞盘子。

网：想象你做的每一个决定都是网中的一个节点，通过线连接到它所导致的事物。
权重： 用户可以给拼图的每一块分配一个“权重”。有些块是“重”的（移动或更改成本高），有些是“轻”的（容易更改）。
策略： 当发生冲突时，计算机不再盲目擦除栈顶，而是查看这张网。它会计算：“我可以移除哪一组特定的连接块来修复错误，同时保留那些‘重’的块不动？”

类比：
想象你在搭建一座纸牌屋。

旧方法： 因为底部有一张牌不稳，你就推倒了整座塔，即使上面的 10 层都完美稳固。
图回溯： 你观察结构。你发现那张不稳的牌连接到一个特定的分支。你小心翼翼地只移除那个分支及其正上方的牌，让房子的其余部分保持站立。你甚至可能选择移除另一个分支，如果它更轻且更容易重建的话。

3. 实际运作方式

论文描述了一个系统，其中计算机：

映射依赖关系： 它绘制一张地图，显示哪些决定导致了哪些其他决定。
选择最便宜的修复方案： 它查看所有可能移除的牌组。它选择成本最低（基于用户的“权重”）的组进行撤销。
保留有效部分： 它保留那些“重”的决定（用户希望保留的那些）的赋值，即使它们在决策链的较高位置。

4. 结果

作者构建了一个名为NapSAT的原型求解器来测试这一点。

测试： 他们使用了"3-着色”问题（一个经典谜题，尝试仅用三种颜色给地图着色，使得相邻区域不共享颜色）。
结果： 与旧方法相比，图回溯犯了更少的错误（更少的“传播”）。因为它没有浪费时间撤销和重做那些不需要更改的事情，在其最佳测试中，求解器完成谜题的速度快了约30%。

5. 为什么这很重要

这不仅仅是关于稍微快一点。它赋予了用户控制权。

在过去，计算机决定遗忘什么。
有了图回溯，你可以告诉计算机：“不要碰这个特定变量；更改它的代价太高。找到另一种修复错误的方法。”

总结

将图回溯想象成从一把钝锤子（为了修复一件事而破坏一切）升级到一把手术刀（仅移除治愈患者所需的精确组织）。它允许计算机更加精确，保留更多有效工作，并通过尊重问题不同部分的“权重”或重要性，更高效地解决逻辑谜题。

注：该论文特别指出，这适用于 SAT 求解，并在“模型计数”、"AllSAT"和"MaxSAT"中具有潜在应用。它还提到正在开展将其集成到"Vampire"（一阶逻辑证明工具）中的工作。

技术摘要：基于图回溯的 CDCL 泛化

问题陈述

冲突驱动子句学习（CDCL）算法是命题可满足性（SAT）求解中的主导方法。当前的求解器主要依赖非时序回溯（NCB），或更近期地，依赖**时序回溯（CB）**来进行冲突修复。

NCB 会激进地回溯到学习子句中的最高决策层级（通常是第二高），取消所有后续决策及其后果的赋值。虽然这种方法效率较高，但它强加了一种严格的自上而下的顺序，可能迫使用户希望保留的字面量被取消赋值，从而导致不必要的回溯并降低搜索局部性。
CB 的限制较少，仅回溯到最高决策层级减一，从而保留部分赋值。然而，它仍然遵循基于决策层级的严格时间顺序。

这两种方法都将蕴含图抽象为决策层级，从而对依赖关系进行了粗略的过度近似。这种抽象限制了求解器执行细粒度修复的能力，可能导致取消那些对于解决冲突并非严格必要的“重”（昂贵或优先）字面量的赋值。

方法论：图回溯（GB）

作者提出了图回溯（GB），这是一种新颖的方案，它直接利用蕴含图来确定取消哪些字面量的赋值，而不是仅仅依赖决策层级。

核心概念

块（Chunks）： GB 不再按决策层级对字面量进行分组，而是将它们聚类为块。一个块 $ck_\ell$ 定义为蕴含图中所有依赖于特定决策字面量 $\ell$ 的字面量集合。如果一个蕴含字面量依赖于多个决策，它可能属于多个块。
用户定义的权重函数： GB 引入了一个权重函数 $\zeta: \mathcal{L} \to \mathbb{R}$ ，将字面量映射到实数。这允许用户为希望保留赋值的字面量（例如“重”字面量）分配更高的权重。
块选择策略： 检测到冲突子句 $C$ $C$ 时，GB 识别出参与冲突的块集合 $\gamma(C)$ $γ (C)$ 。它选择一个块集合 $\Gamma^*$ $Γ^{*}$ 进行撤销，使得：
- 恰好撤销 $\gamma(C)$ 中的一个块（以确保学习到的子句变为单元子句）。
- 被撤销字面量的总权重最小化。
- 终止保障： 为防止无限循环（即在不学习新子句的情况下重复出现相同的冲突），选择被限制为“终止回溯候选”。如果候选者要么导致学习到一个新子句，要么涉及冲突中最近的块，则该候选者有效。

算法调整

冲突分析： 标准的 1-UIP（唯一蕴含点）分析被调整以在块上运行。算法解析子句，直到恰好保留一个属于选定块 $\Gamma^*$ 的字面量，从而生成一个蕴含翻转字面量的学习子句。
回溯： 与取消赋值路径中连续后缀的 NCB/CB 不同，GB 取消特定块的赋值。这需要重新计算剩余字面量的决策层级，并动态管理路径结构。
监视字面量与不变量： 标准的双监视字面量方案依赖于一种栈式不变量，即监视字面量在其他字面量之前被取消赋值。GB 打破了这种顺序。为了保持健全性，作者引入了跨块（cross-chunks）（ $\eta(\ell)$ ），即如果撤销这些块，则要求字面量 $\ell$ 被重新传播的块集合。这导致了一个修订后的不变量（不变量 2），确保如果某个监视字面量被取消赋值，另一个监视字面量要么已满足，要么将被重新传播。

主要贡献

泛化： 已证明 GB 是 NCB 和 CB 的泛化。通过定义特定的权重函数，GB 可以模拟 NCB（回溯到第二高层级）和 CB（回溯到最高层级减一）的行为。
细粒度控制： 该方法允许进行“手术式”的冲突修复，根据用户偏好（权重）而非仅仅是决策顺序来最小化取消赋值的字面量数量。
理论保证： 本文提供了 GB 算法的健全性、完备性和终止性的证明。
实现： 作者在实验求解器 NapSAT 中实现了 GB，包括以下优化：
- 阻挡器（Blockers）： 针对 GB 和跨块进行了适配。
- 块合并： 包括急切（ECM）和懒惰（LCM）策略，以处理遗漏的蕴含并避免冗余回溯。
- 最佳块选择（BB）： 一种启发式方法，用于平衡最小化取消赋值与确保进展之间的权衡。

实证结果

作者在 1,000 个可满足的 3-着色实例上评估了 GB 与 NCB、CB 以及 LSCB（懒惰强时序回溯）的性能。

传播次数： GB 变体始终比标准方法需要更少的字面量传播。最佳配置（GB+ECM）比 NCB 减少了 47% 的传播次数。
运行时间： 传播次数的减少转化为最佳配置约 30% 的运行时间改进。
权衡： 虽然 GB 减少了取消赋值的数量，但由于维护块和跨块的开销，每次传播的成本更高。然而，在困难实例上，净效应是积极的。
重启： 作者指出，标准重启会惩罚 GB 的性能，因为它们与 GB 最小化取消赋值的目标相冲突。GB 在单次求解或决策重排序不如保留特定赋值重要的场景中表现最佳。

意义与主张

本文声称，图回溯提供了一种更灵活且由用户引导的 SAT 求解方法。通过挑战决策层级的抽象，GB 使求解器能够保留那些原本会被激进回溯方案丢弃的“重”字面量。

作者将 GB 定位为并非所有现有策略的替代品，而是一个通用框架，它涵盖了 NCB 和 CB，同时在最小化回溯范围有益的特定基准测试（如图着色）中提供卓越的性能。他们强调了其在 AVATAR 框架和 SMT 求解中的潜在适用性，在这些领域中，传统 CDCL 的刚性栈结构可能是一个限制，尽管他们承认扩展到大量决策以及与理论求解器集成仍然是一个未解决的挑战。