给定一个集合 A = {a 1 ,a 2 ,...,a n }
给定名为 B 1 ,B 2 , ..., B m的 A 子集。如果一个名为 H 的 A 子集与所有给定的 B 有交集，我们称 H 为“覆盖子集”。对于给定的 A 和 B，是否有任何大小为 K（H 的基数为 K）的“覆盖子集”？证明这个问题是NP完全的。
我们应该将一些已知问题简化为“覆盖子集”问题。
问问题
1161 次
1 回答
3
更新 这称为命中集。您可以在维基百科文章中阅读相同的答案。
这个问题在某种程度上是双重设置覆盖问题。
我们将更改一些术语。让我们{B1, B2, ...}成为元素并{a1, a2, ...}成为集合。如果集合包含在原始问题 中，则“集合”在新问题中ai包含“元素” 。BjBjai
现在，您只需要选择ai覆盖所有 'elements' 的最小数量的 'sets' Bj。这个问题是NP完全的，如上面的链接所示。
为了阐明转换，一个问题定义可以通过替换 set/element 和 contains/contained 从另一个生成。比较以下
每个集合都Bj包含一些选定的元素ai
每个“元素”Bj都包含在某个选定的“集合”中ai
于 2011-01-30T04:37:41.937 回答