关于「子模覆盖:从专著里选句的贪心代数与 1−1/e 的保证」,《专著改编的信息保留代数》给出的定量结论是什么?

结论:第一章把选句写成子模覆盖的最大化,贪心算法有 0.6321 的最坏保证,而显著度排序会把名额集中到同一个话题。

数据口径:书中参数为示意;全部计算由书中程序生成;本书不是法律意见,也不是个人化的经营或投资建议。 第六章在 40 个制作工时下求出播客、投影片与题库的最优组合,价值 2.0685,不做题库只有 1.4164;事实核对应放在上游;每周 2 次提醒使期望学习次数最高,为 6.2792,过量提醒有害,对脆弱学习者阈值更低;只改编有权改编的书,合成内容必须标识。

English version

对照数据表

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

greedy vs exhaustive optimum, 300 toy monographs
14 sentences, 10 weighted concepts
kmean ratioworst ratiogreedy hits optguarantee
11.00001.00001.00001.0000
20.99060.81580.87000.7500
30.98820.84910.77330.7037
40.99530.91490.87000.6836
50.99950.94440.98330.6723
61.00001.00001.00000.6651
limit 1 - 1/e = 0.6321
查看完整验算程序
# Chapter 1. p11: greedy sentence selection against the exhaustive optimum.
# A toy monograph has 14 sentences and 10 weighted concepts; each sentence
# covers a random subset of concepts. Coverage value f(S) is the total
# weight of concepts touched by the chosen sentences: monotone and
# submodular. Greedy picks the sentence with the largest marginal gain;
# the optimum is found by enumerating every subset of size k. The bound
# 1 - (1 - 1/k)^k >= 1 - 1/e is the classical guarantee for greedy.
# Weights and coverage probabilities illustrative; seed fixed.
import itertools
import math
import random

rng = random.Random(20261112)
N_SENT, N_CON, TRIALS = 14, 10, 300


def make_book():
    w = [rng.randint(1, 9) for _ in range(N_CON)]
    cover = []
    for _ in range(N_SENT):
        c = [j for j in range(N_CON) if rng.random() < 0.22]
        if not c:
            c = [rng.randrange(N_CON)]
        cover.append(frozenset(c))
    return w, cover


def value(w, cover, picks):
    seen = set()
    for i in picks:
        seen |= cover[i]
    return math.fsum(w[j] for j in sorted(seen))


def greedy(w, cover, k):
    picks = []
    for _ in range(k):
        base = value(w, cover, picks)
        best, gain = None, -1.0
        for i in range(N_SENT):
            if i in picks:
                continue
            g = value(w, cover, picks + [i]) - base
            if g > gain:
                best, gain = i, g
        picks.append(best)
    return value(w, cover, picks)


def optimum(w, cover, k):
    return max(value(w, cover, c)
               for c in itertools.combinations(range(N_SENT), k))


books = [make_book() for _ in range(TRIALS)]
print("greedy vs exhaustive optimum, {} toy monographs".format(TRIALS))
print("{} sentences, {} weighted concepts".format(N_SENT, N_CON))
print(" k   mean ratio  worst ratio  greedy hits opt  guarantee")
for k in range(1, 7):
    ratios = []
    hits = 0
    for w, cover in books:
        g, o = greedy(w, cover, k), optimum(w, cover, k)
        ratios.append(g / o)
        hits += g == o
    bound = 1.0 - (1.0 - 1.0 / k) ** k
    print("{:2d}  {:10.4f}  {:11.4f}  {:15.4f}  {:9.4f}".format(
        k, math.fsum(ratios) / TRIALS, min(ratios), hits / TRIALS,
        bound))
print("limit 1 - 1/e = {:.4f}".format(1.0 - math.exp(-1.0)))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《一书多吃内容裂变代数:从硬核专著自动编译双人播客、导学投影片与通关题库》第 1 章「子模覆盖:从专著里选句的贪心代数与 1−1/e 的保证」(版本 1.0.0). 5D Library. DOI 待发布

DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-151 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026151,
  author    = {Fan, Yafu},
  title     = {Content Fission Algebra: Compiling Hard-Core Monographs into Two-Host Podcasts, Study Slides and Quiz Banks},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

本书其他章节结论