我们有一个集合 A = {a1,a2,...,an}
给定名为 B1,B2, ..., Bm 的子集。如果一个名为 H 的子集与所有给定的 B 有交集，我们称 H 为“覆盖子集”。对于给定的 A 和 B，是否存在任何大小为 K(H 的基数为 K)的“覆盖子集”？证明这个问题是NP完全的。
我们应该将一些已知问题简化为“覆盖子集”问题。
最佳答案
更新 这叫做hitting set .您可以在维基百科文章中阅读相同的答案。
这个问题在某种程度上是set cover problem 的双重问题。 .
我们将更改一些术语。设 {B1, B2, ...} 为元素，{a1, a2, ...} 为集合。如果集合 Bj 包含原始问题中的 ai，则“集合”ai 包含新问题中的“元素”Bj。
现在，您只需要选择覆盖所有“元素”Bj 的最小数量的“集合”ai。该问题是 NP 完全问题，如上面的链接所示。
为了阐明转换，只需替换集合/元素和包含/包含，就可以从另一个问题定义生成一个问题定义。比较以下
每个集合 Bj 都包含一些选定的元素 ai
每个“元素”Bj 都包含在某些选定的“集合”ai
关于algorithm - 证明问题的NP完全性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4841136/