NeFut Logo NeFut
EN 管理员登录

[AI学术] SAT-ACT:基于结果的 CDCL 分支学习

发布于:2026-11-03 22:00 最后更新:2026-11-05 00:45
#algorithm #AI #Machine Learning

学习驱动的 SAT 求解方法近年来受到关注,尤其是提升冲突驱动子句学习(CDCL)求解器的分支决策。传统做法要么利用公式的静态结构特征,要么依赖求解器的运行时反馈。但这些监督信号只能提供有限的状态依赖信息,且不同的结果度量可能倾向于不同的分支选择。为克服这些局限,本文提出 SAT‑ACT 框架,直接从分支动作的结果中提取偏好。我们设计了三种互补的结果比较准则:在同一求解状态下,对独立的分支回滚进行比较,只有当结果明确支持某一动作时才产生偏好;若证据不足或相互冲突,则保持比较未决,而不是强行使用预定义的标量度量。随后,使用状态条件网络学习这些偏好,并在搜索过程中直接输出分支优先级,无需在线回滚。进一步引入非支配启发式动作监督,仅当求解器选取的动作在当前偏好下仍为非支配时才将其作为训练目标。实验在三个 SAT 家族以及 SAT Competition 基准上进行,结果显示 SAT‑ACT 能持续降低 CDCL 搜索成本,并在 PAR‑2 指标上取得显著提升。\n\n点评:SAT‑ACT 通过结果导向的偏好提取和非支配监督,为 CDCL 分支学习提供了更可靠的状态依赖信号,实验验证了其在实际求解中的有效性。

原文链接: https://arxiv.org/abs/2610.41290

[h] 返回首页