关于「最优串联集:工时与打扰频次约束下的选择」,《存量资产的超模串联》给出的定量结论是什么?
结论:第四章在工时与打扰上限下选最优串联集:贪心法在超模问题上最差只得最优值的 0.2188,配对感知挑法提到 0.5358;只要客户对打扰敏感,最优串联数就是有限的。
数据口径:在示意模型里,六项资产两两配对的十五对中有十二对互补、三对替代,全部打开时月度价值 23,104,各自相加只有 13,668。 书中参数为示意,不对应任何真实业务、客户、达人或成交;全部计算由书中程序生成。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.2188, 0.5358
| bound 1 - 1/e = 0.6321 | |||
| (a) coverage, submodular | |||
| method | worst ratio | mean ratio | share optimal |
| greedy | 0.9241 | 0.9937 | 0.750 |
| greedy+swap | 0.9378 | 0.9981 | 0.895 |
| pair-aware | 0.9241 | 0.9937 | 0.750 |
| (b) paired bonus, supermodular | |||
| method | worst ratio | mean ratio | share optimal |
| greedy | 0.2188 | 0.5195 | 0.000 |
| greedy+swap | 0.2188 | 0.8555 | 0.595 |
| pair-aware | 0.5358 | 0.9744 | 0.780 |
查看完整验算程序
# Chapter 4. p42: greedy works for substitutes, can fail for complements.
# Pick k = 4 of 12 assets. Two families of random instances (seeded):
# (a) submodular: weighted coverage of 40 audience segments; each asset
# covers each segment with probability 0.15. Greedy is guaranteed at
# least 1 - 1/e of the optimum (Nemhauser, Wolsey and Fisher 1978).
# (b) supermodular: small stand-alone values a_i in [0, 1], plus a bonus
# b in [4, 8] for each of 5 random pairs that only pays when both
# members are chosen; 2 decoy assets with stand-alone value 2.5.
# Methods: plain greedy, greedy then single swaps, pair-aware greedy
# (also scores adding two assets at once). Ratios are to the exhaustive
# optimum over all C(12, 4) = 495 sets.
import itertools
import math
import random
K, NI = 4, 12
def greedy(f, k):
s = []
while len(s) < k:
s.append(max((x for x in range(NI) if x not in s),
key=lambda x: (f(s + [x]), -x)))
return s
def swaps(f, s):
s = list(s)
better = True
while better:
better = False
for i in range(len(s)):
for x in range(NI):
if x in s:
continue
t = s[:i] + [x] + s[i + 1:]
if f(t) > f(s) + 1e-12:
s, better = t, True
return s
def pair_greedy(f, k):
s = []
while len(s) < k:
opts = [[x] for x in range(NI) if x not in s]
if k - len(s) >= 2:
opts += [[x, y] for x, y in itertools.combinations(range(NI), 2)
if x not in s and y not in s]
s += max(opts, key=lambda o: ((f(s + o) - f(s)) / len(o), -o[0]))
return s
def run(make, rng, reps=200):
rows = {"greedy": [], "greedy+swap": [], "pair-aware": []}
for _ in range(reps):
f = make(rng)
opt = max(f(list(c)) for c in itertools.combinations(range(NI), K))
g = greedy(f, K)
for name, s in (("greedy", g), ("greedy+swap", swaps(f, g)),
("pair-aware", pair_greedy(f, K))):
rows[name].append(f(s) / opt)
return rows
def coverage(rng):
w = [rng.uniform(0.5, 1.5) for _ in range(40)]
cov = [[j for j in range(40) if rng.random() < 0.15] for _ in range(NI)]
def f(s):
hit = set()
for x in s:
hit.update(cov[x])
return math.fsum(w[j] for j in sorted(hit))
return f
def pairs(rng):
a = [rng.uniform(0.0, 1.0) for _ in range(NI)]
a[10] = a[11] = 2.5
allp = list(itertools.combinations(range(10), 2))
bonus = {p: rng.uniform(4.0, 8.0) for p in rng.sample(allp, 5)}
def f(s):
ss = set(s)
terms = [a[x] for x in s]
terms += [b for (x, y), b in sorted(bonus.items())
if x in ss and y in ss]
return math.fsum(terms)
return f
if __name__ == "__main__":
print("bound 1 - 1/e = {:.4f}".format(1 - 1 / math.e))
for title, make, rng in (("(a) coverage, submodular", coverage,
random.Random(37504)),
("(b) paired bonus, supermodular", pairs,
random.Random(37505))):
rows = run(make, rng)
print(title)
print(" method worst ratio mean ratio share optimal")
for name in ("greedy", "greedy+swap", "pair-aware"):
r = rows[name]
hit = len([x for x in r if x > 1 - 1e-9])
print(" {:<12} {:>12.4f} {:>11.4f} {:>14.3f}".format(
name, min(r), math.fsum(r) / len(r), hit / len(r)))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《存量武器库超模组合代数、邻近可能联想图谱与跨业务火力串联母典》第 4 章「最优串联集:工时与打扰频次约束下的选择」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-375 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026375,
author = {Fan, Yafu},
title = {Supermodular Weapon-Arsenals, Adjacent-Possible Recombination Graphs and Cross-Asset Cashflow Chaining},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}