AI Rookies

DPLL — 戴维斯-普特南-洛夫兰-洛格曼算法

事实

一种用于求解布尔可满足性问题的经典回溯算法。

人话

它像宿舍查违禁品:先翻一个柜子,若整层楼都对不上,就顺着线索倒回去重查,直到每间都自洽。

常用于 SAT 求解和自动推理,在冲突中回溯找可行赋值。

相关概念

Constraint Satisfaction Problem
它和约束满足问题很近,都是在一堆限制里找可行解。

Resolution Principle
它常和归结法对照:一个靠回溯搜索,一个靠逻辑推出矛盾。

Unification
它和合一都属于经典符号推理里的基础工具。