关于「标准库 DPLL:单元传播、分支与「易、难、易」」,《规则叠加的悬崖》给出的定量结论是什么?
结论:DPLL 用赋值化简、单元传播与分支回溯判定规则册有没有解,单元传播推出的步骤本身就是一份可读的死锁说明。p21 显示,一本只有八个开关的规则册,第二周加一条规则后约束比只是 1.375,单元传播七步就证明了死锁,因为单开关硬规定把其余规则钉死了。p22 复现了「易、难、易」:死路数的中位数从 0.0 升到 26.5 再回落到 9.0。p23 显示单元传播把工作量压低两个数量级。可是,悬崖究竟在哪里,能不能不做实验就算出一个界?下一章用解数的期望、2-SAT 的精确阈值与子句长度给出答案。
数据口径:书中规则册与数据均为示意;全部计算由书中程序生成;本书属非个人化经营方法,不构成法律、合规或经营决策意见。 第四章给一本 24 个开关的示意规则册做体检:裸约束比 0.958,载荷 0.475,死锁时约束比中位数只有 1.292,最小冲突核横跨三个规则族。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0, 26.5, 9.0
| n = 50, 60 formulas per ratio; medians and 90th percentiles | |||||
| alpha | P(sat) | guesses | dead ends | dead ends p90 | max |
| 2.0 | 1.000 | 24.0 | 0.0 | 0.0 | 0 |
| 3.0 | 1.000 | 18.0 | 0.0 | 1.0 | 4 |
| 3.6 | 1.000 | 16.0 | 1.0 | 9.9 | 48 |
| 4.0 | 0.833 | 18.5 | 5.5 | 38.5 | 56 |
| 4.3 | 0.600 | 22.5 | 16.0 | 46.9 | 64 |
| 4.6 | 0.300 | 27.0 | 26.5 | 44.6 | 63 |
| 5.0 | 0.017 | 25.0 | 26.0 | 38.9 | 44 |
| 6.0 | 0.000 | 16.0 | 17.0 | 25.0 | 30 |
| 8.0 | 0.000 | 9.5 | 10.5 | 14.0 | 19 |
| 10.0 | 0.000 | 8.0 | 9.0 | 11.9 | 15 |
查看完整验算程序
# Chapter 2. p22: easy-hard-easy - search effort peaks at the cliff
# Model: random 3-SAT on n = 50 switches, 60 formulas per ratio
# (illustrative), DPLL with unit propagation and a weighted branching
# rule. Effort = number of guesses (branch points) the solver opens.
# Under-constrained sets are solved almost without guessing, heavily
# over-constrained sets are refuted quickly, and the median effort
# peaks near the 50 per cent point (Mitchell et al. 1992).
import random
import statistics
from collections import Counter
N, TRIALS = 50, 60
ALPHAS = [2.0, 3.0, 3.6, 4.0, 4.3, 4.6, 5.0, 6.0, 8.0, 10.0]
def assign(cls, lit):
out = []
for c in cls:
if lit in c:
continue
if -lit in c:
c = [x for x in c if x != -lit]
if not c:
return None
out.append(c)
return out
def dpll(cls, st):
while True:
unit = next((c[0] for c in cls if len(c) == 1), None)
if unit is None:
break
cls = assign(cls, unit)
if cls is None:
st[1] += 1
return False
if not cls:
return True
st[0] += 1
w = Counter()
for c in cls:
for x in c:
w[x] += 1 << max(0, 6 - len(c))
lit = max(w, key=lambda x: (w[x] + w[-x], w[x], -abs(x), x))
for b in (lit, -lit):
nxt = assign(cls, b)
if nxt is None:
st[1] += 1
elif dpll(nxt, st):
return True
return False
rng = random.Random(20261115)
print("n = %d, %d formulas per ratio; medians and 90th percentiles"
% (N, TRIALS))
print("alpha P(sat) guesses dead ends dead ends p90 max")
for a in ALPHAS:
m = round(a * N)
efforts, dead, ok = [], [], 0
for _ in range(TRIALS):
f = []
for _ in range(m):
vs = rng.sample(range(1, N + 1), 3)
f.append([v if rng.random() < 0.5 else -v for v in vs])
st = [0, 0]
if dpll(f, st):
ok += 1
efforts.append(st[0])
dead.append(st[1])
q = statistics.quantiles(dead, n=10)
print("%5.1f %6.3f %7.1f %9.1f %13.1f %4d"
% (a, ok / TRIALS, statistics.median(efforts),
statistics.median(dead), q[-1], max(dead)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《布尔可满足性相变阈值、促销合规与门禁叠加的约束比临界与全盘死锁预警母典》第 2 章「标准库 DPLL:单元传播、分支与「易、难、易」」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-252 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026252,
author = {Fan, Yafu},
title = {Boolean Satisfiability Phase Transitions: the Critical Constraint Ratio at Which Stacked Promotion, Compliance and Gate Rules Deadlock, and How to See It Coming},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}