在赋值轨迹中保存理由

冲突驱动子句学习通常简称CDCL,处理有限命题合取范式的可满足性问题。与基础DPLL一样,求解器交替进行单元传播和分支决定;不同的是,它把失败分支视为可以分析的证明材料,而非只撤销赋值再换一个方向。

每次主动决定开启一个决策层,由它引出的传播赋值属于相应层,并保存促成传播的理由子句。若某子句的全部文字都变假,该子句成为冲突的起点。决策层描述搜索的先后次序,理由则解释具体赋值为何被强制,二者在分析中承担不同作用。

参考:[1] [2]

学习子句必须由公式蕴含

例如,公式包含¬a∨b、¬c∨d、¬e∨f和¬f∨¬e∨¬b。第一层决定a真,传播得到b真;第二层决定c真,得到d真;第三层决定e真,得到f真,此时最后一个子句全部为假。

把冲突子句与¬e∨f在f上归结,可得¬e∨¬b;再与¬a∨b在b上归结,可得¬e∨¬a。这条学习子句说明a与e不能同时为真,它是原有子句的逻辑后果,而不是为排除失败路径临时添加的任意限制。上例的c、d不参与矛盾原因,故不应机械地把全部决定都写进结论。

参考:[1] [2]

利用冲突越过无关层

保留¬e∨¬a后,可撤销第二、第三层并回到第一层。在a仍为真的情况下,学习子句成为单元子句,立即强制e为假。这种回跳越过了与当前冲突无关的c决定,区别于每次只退一层的顺序回溯。

实际求解器通常依据蕴涵图分析冲突,并常采用第一唯一蕴涵点方案,使学习子句在适当回跳后能够传播。学习哪条子句、回到哪层、如何挑选下一个变量都影响效率,但必须维持推理的可靠性。根层传播已经产生冲突时,才可在没有尚待更换的分支决定下报告不可满足。

参考:[2] [3]

重启、遗忘与完备性

重启撤销当前搜索决定,通常保留部分或全部学习成果,因此不是完全失忆地重跑。子句删除则限制数据库的规模和传播成本;删除适当的冗余学习子句不会改变原问题的满足赋值,但可能改变后续搜索需要完成的工作。

可靠性与终止性不可混为一谈。一个每步都正确的程序,如果无限重启、重复学习或不断丢失进展,仍可能迟迟不作出判定;完整算法需要约束这些策略,保证搜索最终推进。CDCL大幅改善许多实际实例,却不提供所有输入都高效的承诺,也不是神经网络式训练。

参考:[2] [3]