A contribution of Richard M. Stallman & Gerald J. Sussman

提起 Richard M. Stallman 和 Gerald J. Sussman,人们的第一想到的可能是 Emacs 或 Scheme。然而,今天要谈的不是 Emacs 或 Scheme,而是他们在 1977 年发表的一篇论文:Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit analysis。这篇论文首次提出了 Constraint learning (i.e. NOGOOD assertion ) 的概念。

类似于 Dynamic programming 记录重复子问题;Constraint learning 记录 inconsistent 的 partial assignment —— 这个思想后来被广泛应用于各种 problem solving 算法,其中最知名的就是 CDCL (Conflict-driven clause learning) 。

CDCL 作为 DPLL (Davis–Putnam–Logemann–Loveland algorithm) 的加强版,是当前最先进的 SAT/SMT solving 技术,但就其本质而言,不过是在 DPLL 的基础上增加了 Constraint learning。

As of 2009, the technique Stallman and Sussman introduced is still the most general and powerful form of intelligent backtracking.

3 个赞

不明觉厉。。。