关于「贪心集合覆盖与 ln n:最小原语集的可证界」,《冲突多半是冗余》给出的定量结论是什么?
结论:第五章给出贪心集合覆盖的界与差距证书,平常实例上平均只差 1.0919 倍。
数据口径:书中规则库与数值均为示意;全部计算由书中程序生成;本书属非个人化经营方法,不构成法律、合规或经营决策意见,规则的增删须由主事者人工放行。 第一章正面陈述并量化命题:一千条示意规则里,标红配对中真矛盾只占 0.0392,裁决后 971 条是冗余,只剩 18 条约束性规则;越界规则占一成时真矛盾比例也只有 0.2667,但无解指标已遍及全部。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.0919
| 300 instances | 40 rules, 25 candidate primitives, seed 20261113 |
| greedy uses 0 more than the minimum | 127 instances |
| greedy uses 1 more than the minimum | 145 instances |
| greedy uses 2 more than the minimum | 27 instances |
| greedy uses 3 more than the minimum | 1 instances |
| median minimum cover 7 primitives (range 6 to 11) | |
| mean ratio greedy / minimum | 1.0919 |
| worst ratio observed | 1.4286 |
| Johnson bound H(12) | 3.1032 (ln 12 + 1 = 3.4849) |
查看完整验算程序
# Chapter 5. p51: greedy primitive selection against the true minimum
# Model: 40 written rules must each be derivable from at least one
# chosen primitive; 25 candidate primitives each derive a random
# subset of the rules (sizes 2 to 12, illustrative), with every rule
# derivable from some candidate. Greedy (Johnson 1974; Lovasz 1975):
# repeatedly take the primitive deriving most still-uncovered rules,
# ties to the lowest index. The minimum is found by branch and bound.
# Johnson's guarantee: greedy / minimum <= H(k), k the largest set,
# H the harmonic number, computed exactly with Fraction. 300
# instances, one fixed seed.
import math
import random
from collections import Counter
from fractions import Fraction as F
def harmonic(k):
h = F(0)
for i in range(1, k + 1):
h += F(1, i)
return h
def greedy(sets, full):
cov, k = 0, 0
while cov != full:
best = max(range(len(sets)),
key=lambda i: (bin(sets[i] & ~cov).count("1"), -i))
cov |= sets[best]
k += 1
return k
def exact(sets, full, start):
best = [start]
def go(cov, k):
if cov == full:
best[0] = min(best[0], k)
return
if k + 1 >= best[0]:
return
left = full & ~cov
pick, cands = None, None
b = 0
while left:
if left & 1:
cs = [s for s in sets if (s >> b) & 1]
if cands is None or len(cs) < len(cands):
pick, cands = b, cs
left >>= 1
b += 1
for s in sorted(cands, key=lambda s: -bin(s & ~cov).count("1")):
go(cov | s, k + 1)
go(0, 0)
return best[0]
def instance(rng, n=40, m=25):
while True:
sets = []
for _ in range(m):
k = rng.randint(2, 12)
bits = 0
for e in rng.sample(range(n), k):
bits |= 1 << e
sets.append(bits)
full = (1 << n) - 1
allc = 0
for s in sets:
allc |= s
if allc == full:
return sets, full
rng = random.Random(20261113)
ratios = []
gaps = Counter()
opts = []
for _ in range(300):
sets, full = instance(rng)
g = greedy(sets, full)
o = exact(sets, full, g)
ratios.append(F(g, o))
opts.append(o)
gaps[g - o] += 1
worst = max(ratios)
print("300 instances: 40 rules, 25 candidate primitives, seed 20261113")
for d in sorted(gaps):
print(" greedy uses %d more than the minimum: %3d instances"
% (d, gaps[d]))
print("median minimum cover %d primitives (range %d to %d)"
% (sorted(opts)[150], min(opts), max(opts)))
print("mean ratio greedy / minimum %.4f"
% (math.fsum(float(r) for r in ratios) / 300))
print("worst ratio observed %.4f" % worst)
print("Johnson bound H(12) %.4f (ln 12 + 1 = %.4f)"
% (harmonic(12), math.log(12) + 1))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《跨卷规则消解与公理归约、千条机器规则阈值冲突检测与最小原语集母典》第 5 章「贪心集合覆盖与 ln n:最小原语集的可证界」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-258 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026258,
author = {Fan, Yafu},
title = {Cross-Volume Rule Resolution and Axiom Reduction: Detecting Threshold Conflicts among a Thousand Machine Rules and Finding a Minimal Primitive Set},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}