我遇到了一个我不知道如何解决的问题:
我有一套套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
之一的超集)。
是否有一种算法可以确定要删除的(最少数量的)元素?
最佳答案
听起来您想删除最小的 hitting set A
来自 B
(这与顶点覆盖问题密切相关)。
某些集合的集合 A
的命中集本身就是一个集合,这样它至少包含 A
中每个集合的一个元素(它“命中”每套)。最小命中集是最小的此类命中集。因此,如果您的集合 A
有一个 MHS,那么您在 A
中的每个集合中都有一个元素。从 B
中删除它意味着 A
中的集合不能是 B
的子集。
您需要做的就是计算 (A1, A2, ... An) 的 MHS,然后移除来自 B
的那个。不幸的是,找到 MHS 是一个 NP 完全问题。知道这一点后,您有几个选择:
- 如果您的数据集很小,则采用显而易见的蛮力解决方案
- 使用概率算法获得快速、近似的答案(参见 this PDF)
- 向相反的方向跑很远很远
关于算法:从集合中删除尽可能少的元素,以强制没有子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2865211/