算法:从集合中删除尽可能少的元素,以便不强制执行子集

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

这听起来像你要删除的最小碰集的A距离B(这是密切相关的顶点覆盖问题).

某些集合的命中集A本身就是一个集合,它包含每个集合中的至少一个元素A(它"命中"每个集合).最小击球组是最小的击球组.因此,如果您的集合中有MHS,则A每个集合中都有一个元素A.从中移除B意味着没有设置A可以是其子集B.

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

1. 如果您的数据集很小,请使用明显的强力解决方案
2. 使用概率算法获得快速,近似的答案(请参阅此PDF)
3. 远行,远在相反的方向