从概率方法到构造性算法：秩提取器与δ-命中集的核心原理与实践

1. 项目概述：从理论到实践的桥梁

在算法设计与复杂性理论的研究中，我们常常会遇到一些看似“硬”的问题——它们难以找到精确的多项式时间算法，但又并非完全无解。这时，研究者的目光往往会转向两类强大的工具：概率方法和构造性技术。前者利用随机性来证明某些数学对象的存在性，后者则致力于给出该对象的具体、确定性的构建方案。我最近深入探索的一个课题，正是这两类方法在一个经典组合优化问题上的交汇与应用：秩提取器与δ-命中集。

简单来说，你可以把这个问题想象成一个“高效筛选”的场景。假设你有一个巨大的集合族（比如，所有可能的故障模式、所有潜在的广告投放组合，或者所有满足某种条件的代码字），每个集合都包含许多元素。我们的目标是找到一个尽可能小的“代表”集合（即δ-命中集），使得它能“碰触”到原始集合族中足够多的集合（达到一个比例δ）。同时，我们希望这个寻找过程是高效的，并且找到的代表集合本身具有某种良好的结构（比如，其“秩”或维度是可控的）。秩提取器，就是帮助我们从一个庞大的、可能结构复杂的集合中，高效地“提取”出一个核心的、低秩子结构的算法工具。

这项研究绝非纸上谈兵。它在多个前沿领域有着深刻的应用：在错误校正码的设计中，它帮助构造具有强大纠错能力的码字；在计算学习理论中，它与VC维、样本压缩集等概念紧密相连，关乎学习算法的样本效率；在组合优化与算法图论中，它是解决覆盖、击中、打包等问题的基础工具。理解并掌握基于概率与构造性方法的秩提取器，意味着你手中多了一把解开许多复杂计算问题的钥匙。无论你是理论计算机科学的研究者，还是从事算法研发的工程师，亦或是希望深入理解计算本质的学生，跟随我一起拆解这个课题，都将大有裨益。

2. 核心概念拆解：秩、命中集与概率方法

在深入技术细节之前，我们必须先夯实基础，清晰理解几个核心概念。这就像盖房子前要打好地基，概念模糊会导致后续的所有推导都摇摇欲坠。

2.1 秩：不仅仅是矩阵的专属

“秩”这个概念最广为人知是在线性代数中，一个矩阵的秩代表了其行（或列）向量中极大线性无关组的个数，直观反映了矩阵所包含的“信息维度”。在组合与计算理论中，“秩”的概念被极大地推广了。对于一个集合族 $\mathcal{F} \subseteq 2^U$（即全集U的某些子集构成的集合），我们可以定义多种“秩”函数。

最常见的是VC维。对于一个集合族$\mathcal{F}$，它的VC维是最大的整数d，使得存在一个大小为d的点集S，能被$\mathcal{F“打散”——即$\mathcal{F}$限制在S上，能产生所有$2^d$种可能的子集。VC维衡量了集合族的“表达能力”或“复杂程度”。在机器学习中，它直接关系到学习模型所需的样本量。

另一个关键概念是伪维或脂肪粉碎维，它是VC维的一种加权推广，在处理实值函数类时尤为重要。此外，还有图秩、拟阵秩等，它们都与所研究对象的“独立性”结构相关。

在本课题的语境下，“秩提取器”中的“秩”通常指的是某种广义的维度概念。提取器的目标就是：给定一个可能具有高VC维（或高伪维）的庞大集合族$\mathcal{F}$，我们希望能构造出一个新的、较小的集合族$\mathcal{F}'$，使得$\mathcal{F}'$的秩（如VC维）显著低于$\mathcal{F}$，但同时$\mathcal{F}'“近似”了$\mathcal{F}$的某些关键性质，例如对原始集合的覆盖关系。这就好比从一个杂乱无章的大仓库里，整理出一个井然有序、分类清晰的小样品间，并且这个小样品间足以代表仓库里大部分货物的特性。

2.2 δ-命中集：近似覆盖的艺术

“命中集”是一个经典的组合概念。给定一个全集U上的集合族$\mathcal{F} = {S_1, S_2, ..., S_m}$，一个集合 $H \subseteq U$ 被称为$\mathcal{F}$的命中集，如果对于每一个$S_i \in \mathcal{F}$，都有 $H \cap S_i \neq \emptyset$。也就是说，H至少包含了每个集合中的一个元素。

然而，寻找最小命中集是一个NP难问题。在实际应用中，我们常常退而求其次，寻找δ-命中集。其中δ是一个介于0和1之间的参数（通常接近1，如0.9、0.99）。一个集合 $H \subseteq U$ 被称为$\mathcal{F}$的一个δ-命中集，如果它至少“命中”了$\mathcal{F}$中比例为δ的集合。即： $$ |{ S \in \mathcal{F} : H \cap S \neq \emptyset }| \geq \delta \cdot |\mathcal{F}| $$

从精确解到近似解，这一转变带来了巨大的算法可能性。我们的目标不再是寻找那个绝对最小的、能命中所有集合的“完美”解，而是寻找一个大小可控、并能命中“绝大多数”集合的“实用”解。δ的引入，正是概率方法和近似算法大展身手的舞台。

2.3 概率方法：证明“存在”的魔法

概率方法是由保罗·埃尔德什等人发展起来的一套强大数学工具。其核心思想令人着迷：为了证明一个具有某种性质的数学对象（比如，一个小的δ-命中集）存在，我们并不需要直接构造它，而是可以构造一个随机的过程来生成候选对象，然后证明这个随机对象以正概率（甚至高概率）满足我们想要的性质。由于概率大于零，那么满足性质的对象就必然存在！

一个最简单的例子：证明任何一个具有m条边、n个顶点的图，都存在一个大小至少为 $n^2/(4m)$ 的独立集。证明思路是，随机地、独立地以概率p保留每个顶点，然后计算留下的顶点中期望的边数，通过巧妙选择p，可以证明存在一种选择使得去掉至少一条边的某个端点后，剩下的顶点集是一个满足大小要求的独立集。这里我们并没有给出构造独立集的具体算法，只是通过分析随机过程期望值，证明了它的存在性。

在δ-命中集的研究中，概率方法常这样使用：随机地从全集U中采样一个子集H（比如，每个元素以概率p独立地入选）。然后计算H“错过”某个特定集合S的概率（即$H \cap S = \emptyset$），再利用联合界或切尔诺夫界等概率工具，去界定H“错过”太多集合（超过(1-δ)比例）的概率。通过调整采样概率p，我们可以让这个“失败”概率小于1，从而证明存在一个好的δ-命中集H。这种方法往往能给出最优或接近最优的命中集大小界。

注意：概率方法只证明了“存在”，但没有告诉我们如何“找到”。它给出的可能是一个非构造性的证明。这就是为什么我们还需要“构造性技术”。

3. 从存在性到构造性：核心技术与方案选型

概率方法为我们照亮了道路，证明了小而精的δ-命中集的存在性。但作为算法研究者或工程师，我们并不满足于“知道它在那里”，我们想要“亲手把它造出来”。这就是构造性技术登场的时刻。本课题的精髓，就在于如何将概率方法证明中那种“可能性”，转化为确定性的、高效的算法。

3.1 去随机化：将概率固化

“去随机化”是连接概率证明与确定性算法的核心桥梁。其思想是：概率方法证明中，随机对象以高概率具有好性质，意味着“大多数”随机选择都是好的。那么，是否存在系统性的方法，去“模仿”或“替代”随机选择，从而确定性地找到一个好对象呢？答案是肯定的，常用技术包括：

1. 条件期望法：这是最直观的去随机化方法。考虑一个随机变量X（例如，随机命中集H的大小，或者它未命中的集合数量）。概率方法证明了E[X]（期望值）满足某个好的性质。我们可以通过“逐位确定”的方式来构造解。从第一个元素开始，我们计算在“该元素被选中”和“不被选中”两种条件下，剩余随机过程的期望值E[X|choice]。我们选择那个能使条件期望值更优（或至少不更差）的决策。然后以此类推，处理第二个、第三个元素……由于每一步都选择了不劣化期望值的选项，最终得到的确定性对象，其指标X值至少不会差于最初的期望值E[X]，从而保证了性质。

2. 两两独立与有限域：完全独立的随机变量需要大量随机比特。研究发现，许多概率论证并不需要完全的独立性，只需要“两两独立”或“k-明智独立”就足够了。而生成一组两两独立的随机变量，所需要的随机比特数远远少于完全独立的情况，有时甚至可以通过一个小的有限域上的多项式来确定性生成。这使我们能够用一个小规模的、确定性的搜索（遍历所有可能的种子）来替代庞大的随机空间，从而在多项式时间内找到满足要求的对象。

3. 伪随机数发生器：这是一个更高级的工具。PRG可以将一个短的、真正的随机种子，扩展成一个长的、看起来“像是”随机的序列。如果一个算法在完全随机序列下以高概率成功，并且该算法对随机性的依赖是“有限的”（例如，可以通过有限自动机或低阶多项式来检验），那么存在高效的PRG来“愚弄”这个算法。我们可以简单地枚举所有可能的短种子，运行算法，其中必有一个种子能产生成功的结果。这相当于用多项式时间的确定性搜索替代了概率过程。

在我们的课题中，构造一个δ-命中集，往往首先用概率方法分析随机采样得到好集的概率，然后利用上述去随机化技术（尤其是条件期望法），设计出一个确定性算法来逐元素构建这个集合。

3.2 秩提取器的构造：筛出低维结构

现在，让我们聚焦于“秩提取器”本身的构造。其输入通常是一个大的集合族$\mathcal{F}$（可能VC维很高），以及参数δ和期望的输出秩d。目标是输出一个新的集合族$\mathcal{F}'$，满足：

1. $\mathcal{F}'$的VC维 ≤ d。
2. $\mathcal{F}'$是原族$\mathcal{F}$的一个δ-覆盖：即对于$\mathcal{F}$中至少δ比例的集合S，都存在$\mathcal{F}'$中的某个集合S’，使得S’包含了S（或与S有某种紧密关系，如S’ ∩ C = S ∩ C 对于某个核心集C成立）。

一种强有力的构造范式是抽样与验证：

• 步骤一（概率存在性）：利用概率方法证明，存在一个大小适中（比如，大小为O(d/ε^2)）的“核心点集”C ⊆ U，具有这样的性质：将$\mathcal{F}$中每个集合S都替换为其在C上的限制（即 S ∩ C），得到的新族$\mathcal{F}|_C$，其VC维不会显著膨胀（仍然约为O(d)），并且这个限制操作保留了原集合族的大部分信息。这个证明通常依赖于ε-网或ε-近似的理论。
• 步骤二（构造性实现）：上述证明暗示，如果我们能“猜中”这个好的核心点集C，那么问题就简化了。我们可以通过构造性技术来寻找C。例如，使用条件期望法：将U中的元素排序，逐个决定是否将其加入C。在决定每个元素时，我们评估当前部分C下，$\mathcal{F}|_C“未来”的VC维期望（这需要能计算或估计给定部分点集上，集合族打散能力的期望）。我们选择那个能控制期望秩增长的决策分支。
• 步骤三（生成覆盖族）：一旦找到了好的核心点集C，并且得到了低VC维的受限族$\mathcal{F}|_C$，由于$\mathcal{F}|_C的VC维低，根据Sauer-Shelah引理，它的集合数量最多是|C|^O(d)。这个数量可能仍然很大，但已经是原始大小的多项式级别（而非可能是指数级）。我们可以进一步对这个受限族进行简化或采样，最终得到大小可控的$\mathcal{F}'$。

这个构造过程清晰地展示了概率方法与构造性技术的交织：概率论证提供了“好结构存在”的蓝图和规模估计；构造性技术则提供了按图索骥、一步步搭建出这个结构的具体施工方案。

4. 实操过程：构建一个δ-命中集与秩提取器的简化案例

理论或许有些抽象，让我们通过一个高度简化的模型，来亲手“演练”一遍如何构造一个δ-命中集，并体会其中秩的概念。假设我们的全集U是n个点，集合族$\mathcal{F}$由m个子集构成。我们的目标是构造一个小的小的集合H，命中至少90%（δ=0.9）的集合。

4.1 步骤一：概率分析确定采样率

我们采用最简单的随机采样策略。设H通过独立地以概率p包含每个元素而形成。

• 对于一个固定的集合S（大小为|S|），H完全错过S的概率是 $(1-p)^{|S|}$。
• 为了让H有希望成为δ-命中集，我们希望每个集合被错过的概率尽可能小。一个自然的想法是让 $(1-p)^{|S|} \leq 0.1$（这样“期望”未命中数就小于0.1m）。解这个不等式，得到 $p \geq 1 - 0.1^{1/|S|}$。如果|S|很小，p就需要很大。
• 更系统的分析是使用联合界。令随机变量X为未命中的集合数量。则E[X] = Σ_{S in F} (1-p)^{|S|}。我们希望E[X] < 0.1m，这样由马尔可夫不等式，Pr[X >= 0.1m] < 1，即存在一个实例使得X < 0.1m，也就是命中集。
• 为了最小化|H|的期望大小（即np），我们需要选择p来平衡E[|H|] = np 和 E[X]。这通常导出一个加权覆盖的思想：对于大小不同的集合，我们或许应该用不同的概率去覆盖其元素。但作为简化，假设所有集合大小约为k，那么最优选择p满足 (1-p)^k ≈ 0.1，即 p ≈ 1 - 0.1^{1/k}。当k较大时，p ≈ (ln 10)/k。

通过这个分析，我们知道了随机采样策略“理论上”可以 work，并且给出了采样率p的一个指导值。

4.2 步骤二：利用条件期望法进行去随机化构造

我们现在不抛硬币了，要确定性构造H。将U中元素编号为1, 2, ..., n。我们维护两个变量：

• H：当前已确定的命中集（初始为空）。
• 对于每个集合S ∈ $\mathcal{F}$，维护一个“存活概率”的估计值。更准确地说，我们维护一个“未命中计数”的期望值。

算法过程如下：

1. 初始化：对于每个集合S，其“当前未命中概率”prob_miss[S]初始为 $(1-p)^{|S|}$。总未命中期望E_total= Σ prob_miss[S]。
2. 对于i从1到n（遍历每个元素）： a.计算选择该元素的期望收益：假设我们将元素i加入H。那么对于所有包含i的集合S，它们被命中了，其prob_miss[S]将立即变为0。对于不包含i的集合S，其prob_miss[S]保持不变。计算新的总期望E_include= Σ_{S not contain i} prob_miss[S]。 b.计算不选择该元素的期望后果：假设我们不将元素i加入H。那么所有集合的prob_miss[S]需要更新，以反映“在剩余元素中继续随机选择”的期望。实际上，对于每个包含i的集合S，如果我们现在不选i，那么在后续的随机选择中（针对剩余元素，每个以概率p被选），它最终被错过的概率会变大。精确计算需要知道剩余元素的情况，比较复杂。一个经典且有效的简化是：我们假设在后续决策中，每个剩余元素被选中的“概率”仍然是p（尽管我们是确定性的，但在期望计算中我们仍沿用这个概率模型）。那么，对于每个集合S，如果我们现在不选i，并且i ∈ S，那么S的未命中概率更新为prob_miss[S] = prob_miss[S] / (1-p)（因为我们已经确定排除了i这个命中的机会，相当于在条件概率下，后续需要更“努力”才能不命中）。对于i ∉ S的集合，prob_miss[S]不变。计算新的总期望E_exclude。 c.比较并决策：比较E_include和E_exclude。我们选择能使总未命中期望E_total更小的那个决策。即，如果E_include <= E_exclude，则将i加入H，并更新所有相关集合的prob_miss[S]为0，E_total = E_include。否则，不将i加入H，并更新那些包含i的集合的prob_miss[S]（乘以1/(1-p)），E_total = E_exclude。
3. 遍历完所有元素后，得到的确定性集合H，其导致的最终未命中集合数的期望值E_total不大于初始的随机期望值。由于初始随机期望值E[X] < 0.1m，且我们的每一步选择都没有增加期望值，因此最终确定的H，其“未命中集合数”的期望值仍然小于0.1m。但注意，现在H是确定的，所以这个“期望值”实际上就是H未命中的真实集合数的一个上界（在概率模型下）。更严格的分析可以证明，通过这种方法构造的H，其未命中集合数不超过0.1m。因此，H就是一个确定的0.9-命中集。

4.3 步骤三：与秩提取器的联系

在上面的构造中，我们得到了一个确定的集合H。现在，考虑从这个过程中如何引申出“秩”的概念。假设我们的集合族$\mathcal{F}$具有较高的VC维（比如，它能打散一个较大的点集）。我们构造的H，虽然是一个点集，但我们可以考虑由H所“定义”的集合族：即所有形如 S ∩ H （其中S ∈ $\mathcal{F}$）的集合。这个新族是定义在较小的全集H上的。

关键观察：如果H是一个好的δ-命中集，那么对于大多数集合S，S ∩ H 是非空的。但这还不够“低秩”。秩提取器要求更多：它希望得到一个新的集合族$\mathcal{F}'$，而不仅仅是一个点集H。一种思路是，将H作为前述“核心点集”C的候选。我们可以分析$\mathcal{F}|_H$的VC维。由于H是通过一个贪心式的（基于条件期望的）过程选出的，它很可能具有一种“代表性”，使得$\mathcal{F}|_H无法打散H中太大的子集。事实上，有一些理论结果（基于采样引理）表明，从一个大集合族中随机（或伪随机）抽取一个足够大的样本点集C，以高概率保证$\mathcal{F}|_C的VC维被“压缩”到与原始族的VC维相当的水平。

在我们的确定性构造中，虽然H不是随机样本，但因为它是在控制“未命中期望”的目标下构建的，它同样倾向于覆盖那些“难以被同时错过”的元素组合，这间接地可能也控制了$\mathcal{F}|_H的“打散”能力。要严格证明这一点需要更复杂的分析，但直觉上，H作为一个小型“代表点集”，由它产生的限制族$\mathcal{F}|_H的复杂度（秩）应该是可控的。然后，我们可以将$\mathcal{F}|_H`本身，或者对它进行进一步简化（例如，合并那些在H上表现相同的原始集合），作为最终输出的低秩集合族$\mathcal{F}'$。这个$\mathcal{F}'$就是我们要的秩提取器的输出——一个VC维较低，但又能近似代表原族大多数成员行为的集合族。

5. 性能分析与参数权衡

任何构造性算法都必须关心其效率与效果。对于δ-命中集和秩提取器，我们主要关注以下几个核心参数：

1. 命中集大小 |H|：我们希望它尽可能小。从概率分析可知，随机采样给出的期望大小是n * p，其中p ~ O((log(1/(1-δ)))/k)（假设集合大小~k）。因此，|H| ~ O((n log m)/k) （这里简化了，实际界与δ和集合大小分布有关）。确定性构造（如条件期望法）得到的大小通常与这个随机期望值在同一定量级，有时会多出一个常数因子。

2. 构造时间：条件期望法需要遍历所有n个元素，并对每个元素检查所有m个集合来更新期望值。因此，朴素实现的时间复杂度是O(n * m)。当m和n很大时，这是不可接受的。优化方法包括：

   • 利用稀疏性：如果每个集合大小不大，或者每个元素所属的集合数不多，可以建立倒排索引，加速更新。
   • 近似计算：不一定在每一步都精确计算期望，可以采用蒙特卡洛抽样来估计，以时间换精度。
   • 并行化：期望值的更新对于不同集合是独立的，可以并行计算。
   • 对于秩提取器，分析$\mathcal{F}|_C的VC维可能是指数级的（因为需要检查所有子集是否被打散）。实际中，我们通常不显式计算VC维，而是依赖于组合引理（如Sauer-Shelah引理）给出的上界，或者设计一种隐式表示低秩族的方法。

3. 近似比：我们构造的是δ-命中集，而非最小命中集。近似比衡量的是我们解的大小与最优解大小的比值。对于最小命中集问题，即使δ=1，已知不存在O(log n)倍以内的近似算法（除非P=NP）。但对于δ<1，情况可能不同。我们的构造性方法给出的解，其大小与由概率方法证明存在的解的大小之比，通常是常数倍或对数倍，这已经是很好的理论保证了。

4. 秩的压缩率：这是秩提取器特有的指标。输入族$\mathcal{F}$的VC维为D，输出族$\mathcal{F}'$的VC维为d。我们希望d远小于D，同时保证覆盖比例δ足够高。理论上有著名的采样引理：从U中随机抽取一个大小为O((d/ε^2) log(d/ε))的点集C，则以高概率，$\mathcal{F}|_C的VC维不超过d，且对于$\mathcal{F}$中至少1-ε比例的集合，其在C上的行为能够代表其在全集上的行为（在某种度量下）。这里的d可以取为O(D)，但通过更精细的构造（如迭代重采样），有时可以获得d = O(D/ε)甚至更好的压缩。

参数权衡的实操心得：

• δ的选取：δ越接近1，对命中集的要求越苛刻，所需大小|H|通常也越大（因为需要覆盖那些“顽固”的、难以被同时命中的集合）。在实际问题中，δ=0.9或0.99往往已经足够，追求1.0可能会付出不成比例的代价。
• 时间与精度的平衡：完全精确的条件期望法可能太慢。在实践中，我经常采用“贪心+随机化”的混合策略。例如，先运行几轮随机采样得到一个候选集，然后在这个基础上用贪心法（每次选择能命中最多未覆盖集合的元素）进行增补。这种方法速度很快，虽然理论保证可能稍弱，但在实际数据上往往表现优异。
• 处理大规模集合族：当m极大时，甚至无法将所有集合载入内存。这时需要用到流算法或分布式算法。一种流式贪心算法是：维护当前命中集H，顺序读取集合流。当一个集合到达时，如果它未被当前H命中，则从该集合中随机（或根据某种启发式规则）选择一个元素加入H。可以证明，这种算法在流式设置下也能获得可证的近似比。

6. 常见问题、调试技巧与扩展应用

在实际实现和应用上述理论时，会遇到各种挑战。以下是我从项目实践中总结的一些常见问题和解决思路。

6.1 常见问题与排查

6.2 调试与验证技巧

• 小规模验证：永远先在一个人工构造的、结果已知的小实例上测试你的算法。例如，构造一个明确的、最小命中集大小已知的集合族，看你的算法能否找到接近大小的解。
• 与随机基线对比：实现一个简单的随机采样算法（按理论p采样）。你的确定性算法或改进算法的性能（命中集大小、运行时间）应该稳定地优于或至少不差于随机算法的平均值。
• 可视化中间结果：对于中等规模的问题，可以可视化元素-集合的关联矩阵。用热图展示哪些元素被选中，以及它们覆盖了哪些集合。这能直观地发现算法是否在重复覆盖某些“容易”的集合，而忽略了“困难”的集合。
• 理论边界检查：计算你算法输出解的实际大小，与概率方法证明的存在性大小上界（例如， (n ln m)/k）进行比较。如果你的结果远大于这个上界，要么是理论边界在此实例上很松，要么是算法实现有问题。

6.3 扩展应用场景

这项技术的应用远不止于理论计算机科学。

• 机器学习与特征选择：在高维机器学习中，特征组合可能构成一个巨大的假设空间（集合族）。寻找一个小的δ-命中集，可以理解为寻找一组“关键特征”或“原型样本”，它们能够激活（命中）大多数有效的特征组合模式。秩提取则对应着从复杂模型（高VC维）中蒸馏出一个更简单、可解释性更强的模型（低VC维），同时保持大部分预测能力。
• 数据库查询优化：在涉及多个查询条件（每个条件对应一个元组集合）的复杂查询中，预先计算一个小的δ-命中集（即一组“索引元组”），可以快速回答大多数查询是否可能返回非空结果，用于查询重写或优化。
• 网络诊断与监控：网络中的故障模式可以看作集合（受影响的节点或链路）。部署监控探针（命中集）的目标是以最小成本覆盖尽可能多的潜在故障。δ-命中集模型允许容忍对某些罕见故障模式的漏检。
• 组合拍卖与资源分配：竞拍者对资源包的估价可以建模为对某个集合的估值。卖家需要选择一组资源包（集合族）进行拍卖。秩提取器可以帮助卖家从指数级可能的资源包中，选出一个大小可控、但又能大致反映竞拍者偏好多样性（低秩近似）的子集，从而设计更高效的拍卖机制。

这个领域最吸引人的地方在于，它提供了从“存在性证明”到“实际构建”的完整方法论。当你用代码实现出那个确定性的构造算法，并看到它在一个具体问题上输出一个简洁而有效的解时，那种连接抽象数学与现实世界的成就感，是无与伦比的。我个人的体会是，在应用这些理论时，切忌生搬硬套公式。一定要深入理解你手中具体问题的数据结构、分布特性，然后对通用算法进行适配和优化，往往一个小的启发式改进，就能带来显著的性能提升。例如，在贪心构造命中集时，如果能为不同元素根据其所属集合的“稀缺性”赋予动态权重，效果通常会比简单的“覆盖最多未命中集合”规则更好。