算法:从集合中删除尽可能少的元素，以强制没有子集

Question

我遇到了一个我不知道如何解决的问题:

我有一套套A = {A_1, A_2, ..., A_n}我有一套 B .

现在的目标是从 B 中删除尽可能少的元素(创建 B' )，这样，在删除所有 1 <= i <= n 的元素之后, A_i 不是 B' 的子集.

例如，如果我们有 A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} , 和 B={1,2,3,4,5} ，我们可以例如从 B 中删除 1 和 2 (这会产生 B'={3,4,5} ，它不是 A_i 之一的超集)。

是否有一种算法可以确定要删除的(最少数量的)元素？

Answer 1

听起来您想删除最小的 hitting set A 来自 B(这与顶点覆盖问题密切相关)。

某些集合的集合 A 的命中集本身就是一个集合，这样它至少包含 A 中每个集合的一个元素(它“命中”每套)。最小命中集是最小的此类命中集。因此，如果您的集合 A 有一个 MHS，那么您在 A 中的每个集合中都有一个元素。从 B 中删除它意味着 A 中的集合不能是 B 的子集。

您需要做的就是计算 (A₁, A₂, ... A_n) 的 MHS，然后移除来自 B 的那个。不幸的是，找到 MHS 是一个 NP 完全问题。知道这一点后，您有几个选择:

1. 如果您的数据集很小，则采用显而易见的蛮力解决方案
2. 使用概率算法获得快速、近似的答案(参见 this PDF)
3. 向相反的方向跑很远很远