差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
代码术语:sat [2026/10/16 12:31] – 撰写 SAT(布尔可满足性问题)词条 张叶安代码术语:sat [2026/10/16 12:32] (当前版本) – 为 SAT 词条添加全文结构思维导图 张叶安
行 292: 行 292:
  
 返回:[[代码术语]] 返回:[[代码术语]]
 +
 +```mdk height=600 color=#7c3aed
 +# SAT
 +## 判断语境
 +- 算法 / 论文 / 验证工具 → 可满足性问题
 +- 网络配置 → 地址转换
 +- 工程交付 → 现场验收测试
 +- 考试 / 留学 → 美国高考
 +- 前端色彩 → saturation 饱和度
 +## SAT 问题是什么
 +### 五个零件
 +- 变量 x1 x2 x3:只有真 / 假
 +- 文字:x 或 ¬x
 +- 子句:若干文字的或
 +- CNF:若干子句的与
 +- 赋值 / 模型:让公式为真的取值
 +### 结论只有两种
 +- SAT:存在满足的赋值
 +- UNSAT:任何赋值都不满足
 +### 例子
 +- (x1 ∨ ¬x3) ∧ (x2 ∨ x3 ∨ ¬x1)
 +- x1=T, x2=F, x3=T 即满足
 +## 怎么编码成 CNF
 +### 约束直接写
 +- 互斥:¬A ∨ ¬B
 +- 蕴含:¬A ∨ B
 +- 恰好一个:至少一个 + 两两互斥
 +### Tseitin 变换
 +- 给子公式起辅助变量
 +- 规模从指数降到线性
 +- 代价是变量变多
 +### at-most-one 编码
 +- pairwise:O(n²),n 小才用
 +- sequential:O(n)
 +- 二进制:O(n log n)
 +- commander:常数更小
 +### 有整数就上 SMT
 +- 算术、数组、字符串别硬编
 +## DIMACS CNF
 +- c 开头是注释
 +- p cnf 变量数 子句数
 +- 每行一个子句,以 0 结尾
 +- 正数原文,负数取反
 +- cadical / minisat 直接吃这个格式
 +- PySAT:Glucose3 + add_clause
 +## 复杂度
 +- 2-SAT:线性,蕴含图 SCC
 +- Horn-SAT:线性,单元传播
 +- 3-SAT:NP 完全(Karp 1972)
 +- CNF-SAT:NP 完全(Cook–Levin 1971)
 +- #SAT:数解的个数,#P 完全
 +- MaxSAT:最大满足,NP 难
 +- QBF:带量词,PSPACE 完全
 +## 求解器原理
 +- DPLL:单元传播 + 分支回溯
 +- CDCL:冲突驱动子句学习
 +- 学习子句永久有效
 +- 非时序回溯,一步跳很远
 +- VSIDS 分支启发
 +- 两文字监视加速传播
 +- Luby 重启、子句删除
 +- 输出三态:SAT / UNSAT / UNKNOWN
 +- UNSAT 带 DRAT 证明可校验
 +## 工具
 +- MiniSat、Glucose、CaDiCaL、Kissat
 +- CryptoMiniSat:XOR 友好
 +- PySAT:Python 统一接口
 +- Z3 / CVC5 / Yices:SMT
 +## 工程现实
 +- 百万变量、千万子句的实例可解
 +- 难在结构,不在规模
 +- 随机 3-SAT 才是真硬
 +- 预处理先缩小问题
 +## 用在哪
 +- 硬件形式验证、等价性检查
 +- 限界模型检查 BMC
 +- 符号执行、测试生成
 +- SMT 与程序验证
 +- 自动规划 SATPLAN
 +- 依赖解析:PubGrub 风格
 +- 配置、装箱、排课、调度
 +- 数独、N 皇后、图着色
 +- 密码分析搜原像
 +- MaxSAT 最小改动修复
 +## 别混淆
 +- SMT = SAT + 理论
 +- SAST / DAST:源码与应用扫描
 +- 3-SAT 是 SAT 的特例
 +- SNAT / DNAT:网络地址转换
 +- SAT 考试、Site Acceptance Test
 +- .sat:ACIS 三维模型
 +- saturate():饱和度
 +## 常见坑
 +- UNKNOWN 当成无解
 +- 整数问题硬编码成布尔
 +- p cnf 头信息与内容不符
 +- at-most-one 写成 O(n²)
 +- UNSAT 不留证明
 +- 拿随机实例判定 SAT 不行
 +- 以为模型不同是结论不同
 +## 记住这句
 +- SAT 问「有没有一组取值让公式成立」
 +- 它是第一个被证明的 NP 完全问题
 +- CDCL 让有结构的工业实例真的可解
 +```
  

该主题尚不存在

您访问的页面并不存在。如果允许,您可以使用创建该页面按钮来创建它。

  • 代码术语/sat.1792125119.txt.gz
  • 最后更改: 2026/10/16 12:31
  • 由 张叶安