我有一个问题，我正在研究最快的算法来找到一个集合，该集合是原始集合 (S) 的子集并且不包含 S 的任何子集 (S1, ... Sn)。我想要的集合to find 可以包含 Si 的一些元素，但不包含全部。
例如原始集合:S = (1, 2, 3, 4, 5), S1 = (1, 2), S2 = (1, 3)
=> 最长的集合: (2, 3, 4, 5); 其他集合:(1, 4, 5), (2, 4, 5), (3, 4, 5), (1, 4),...
有人可以给我建议吗？谢谢!
最佳答案
坏消息
考虑选择不包含哪些元素的问题。
如果我们选择不包含元素 1，则满足 S1 和 S2 的约束。
如果我们选择不包含元素 2，则满足 S1 的约束。
如果我们选择不包含元素 3，则满足 S1 和 S3 的约束。
所以 1 给出 {S1,S2}，2 给出 {S1}，3 给出 {S3}。
您的问题可以表示为找到最少数量的不包含元素，使得满足集合(例如 {S1,S2})的并集覆盖所有给定集合。
这正是 set cover problem这是 NP 完全的。
好消息
在实践中，您可能会做得很好，只需根据最终覆盖最多集合的元素选择不包含的元素即可。
这是一个易于实现的贪心算法(尽管它不会总是给出最优答案)。
关于algorithm - 查找所有集不包含任何子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34047586/