R/C++中集合覆盖问题的变化

Question

给定一个元素U = {1,2,3,...,n}的宇宙以及这个宇宙中的许多集合{S1,S2,...,Sm},我们可以创建的最小集合是什么覆盖m组中的每一组中的至少一个元素？

例如,给定以下元素U = {1,2,3,4}并设置S = {{4,3,1},{3,1},{4}},以下几组将涵盖至少一个每组中的元素:{1,4}或{3,4}所以此处所需的最小大小为2.

有关如何扩大规模以解决m = 100或m = 1000套问题的任何想法？或者想一想如何用R或C++编写代码？

上面的样本数据使用R' library(sets).

s1 <- set(4, 3, 1)
s2 <- set(3, 1)
s3 <- set(4)
s <- set(s1, s2, s3)

干杯

Answer 1

这是打击集问题,基本上是设置覆盖元素和集合的角色互换.假设A = {4,3,1}且B = {3,1}且C = {4},则元素集包含关系为

  A B C
1 + + -
2 - - -
3 + + -
4 + - +

所以你基本上想要用集合1 = {A,B}和2 = {}和3 = {A,B}和4 = {A,C}来解决覆盖{A,B,C}的问题.

在实践中解决非常重要的集合覆盖实例的最简单方法可能是找到一个带有R或C++接口的整数编程包.您的示例将以LP格式呈现为以下整数程序.

Minimize
    obj: x1 + x2 + x3 + x4
Subject To
    A: x1 + x3 + x4 >= 1
    B: x1 + x3 >= 1
    C: x4 >= 1
Binary
    x1 x2 x3 x4
End

Answer 2

如果将每个集合限制为 2 个元素，则您将获得 np 完全问题节点覆盖。我猜想更普遍的问题也是 NP 完全的（对于确切的版本）。