关于「子模覆盖:从专著里选句的贪心代数与 1−1/e 的保证」,《专著改编的信息保留代数》给出的定量结论是什么?
结论:第一章把选句写成子模覆盖的最大化,贪心算法有 0.6321 的最坏保证,而显著度排序会把名额集中到同一个话题。
数据口径:书中参数为示意;全部计算由书中程序生成;本书不是法律意见,也不是个人化的经营或投资建议。 第六章在 40 个制作工时下求出播客、投影片与题库的最优组合,价值 2.0685,不做题库只有 1.4164;事实核对应放在上游;每周 2 次提醒使期望学习次数最高,为 6.2792,过量提醒有害,对脆弱学习者阈值更低;只改编有权改编的书,合成内容必须标识。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.6321
| greedy vs exhaustive optimum, 300 toy monographs | ||||
| 14 sentences, 10 weighted concepts | ||||
| k | mean ratio | worst ratio | greedy hits opt | guarantee |
| 1 | 1.0000 | 1.0000 | 1.0000 | 1.0000 |
| 2 | 0.9906 | 0.8158 | 0.8700 | 0.7500 |
| 3 | 0.9882 | 0.8491 | 0.7733 | 0.7037 |
| 4 | 0.9953 | 0.9149 | 0.8700 | 0.6836 |
| 5 | 0.9995 | 0.9444 | 0.9833 | 0.6723 |
| 6 | 1.0000 | 1.0000 | 1.0000 | 0.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}
}