关于「最优串联集:工时与打扰频次约束下的选择」,《存量资产的超模串联》给出的定量结论是什么?

结论:第四章在工时与打扰上限下选最优串联集:贪心法在超模问题上最差只得最优值的 0.2188,配对感知挑法提到 0.5358;只要客户对打扰敏感,最优串联数就是有限的。

数据口径:在示意模型里,六项资产两两配对的十五对中有十二对互补、三对替代,全部打开时月度价值 23,104,各自相加只有 13,668。 书中参数为示意,不对应任何真实业务、客户、达人或成交;全部计算由书中程序生成。

English version

对照数据表

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

bound 1 - 1/e = 0.6321
(a) coverage, submodular
methodworst ratiomean ratioshare optimal
greedy0.92410.99370.750
greedy+swap0.93780.99810.895
pair-aware0.92410.99370.750
(b) paired bonus, supermodular
methodworst ratiomean ratioshare optimal
greedy0.21880.51950.000
greedy+swap0.21880.85550.595
pair-aware0.53580.97440.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}
}

本书其他章节结论