关于「贪心集合覆盖与 ln n:最小原语集的可证界」,《冲突多半是冗余》给出的定量结论是什么?

结论:第五章给出贪心集合覆盖的界与差距证书,平常实例上平均只差 1.0919 倍。

数据口径:书中规则库与数值均为示意;全部计算由书中程序生成;本书属非个人化经营方法,不构成法律、合规或经营决策意见,规则的增删须由主事者人工放行。 第一章正面陈述并量化命题:一千条示意规则里,标红配对中真矛盾只占 0.0392,裁决后 971 条是冗余,只剩 18 条约束性规则;越界规则占一成时真矛盾比例也只有 0.2667,但无解指标已遍及全部。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1.0919

300 instances40 rules, 25 candidate primitives, seed 20261113
greedy uses 0 more than the minimum127 instances
greedy uses 1 more than the minimum145 instances
greedy uses 2 more than the minimum27 instances
greedy uses 3 more than the minimum1 instances
median minimum cover 7 primitives (range 6 to 11)
mean ratio greedy / minimum1.0919
worst ratio observed1.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}
}

本书其他章节结论