6

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

我有一套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）。

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

4

3 回答 3

8

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

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

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

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

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

于 2010-05-19T19:22:54.387 回答
0

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

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

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

于 2010-05-19T23:49:26.163 回答