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

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}，我们可以例如从中删除 1 和 2 B（这将产生B'={3,4,5}，这不是其中之一的超集A_i）。

是否有确定要删除的（最少）元素的算法？

Answer 1

听起来您想删除from的最小命中集（这与顶点覆盖问题密切相关）。AB

某些集合的命中集合A本身就是一个集合，它包含每个集合中的至少一个元素A（它“命中”每个集合）。最小击球集是最小的这样的击球集。因此，如果您的 set-of-sets 有一个 MHS，那么您在 中的A每个集合中都有一个元素A。从中删除它B意味着没有任何集合A可以是B.

您需要做的就是计算 (A ₁ , A ₂ , ... A _n ) 的 MHS，然后将其从B. 不幸的是，找到 MHS 是一个 NP 完全问题。知道这一点，你有几个选择：

1. 如果您的数据集很小，请执行明显的蛮力解决方案
2. 使用概率算法获得快速的近似答案（请参阅此 PDF）
3. 向相反的方向跑很远很远

Answer 2

我认为您应该从这些集合中找到最小长度，然后删除该集合中的这些元素。

Answer 3

如果您只需要一些近似值，请从 A 中的最小集合开始，然后从 B 中删除一个元素。（您可以随机抓取一个，或者检查 A 中哪个元素在最多集合中，具体取决于准确度，你需要多快）

现在 A 中的最小集合不是 B 的子集。从那里继续，但首先检查您正在检查的集合是否是此时的子集。

这让我想起了顶点覆盖问题，我记得一些类似于这个的近似算法。