6

给定一个包含元素 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's library(sets)。

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

干杯

4

4 回答 4

7

这就是命中集合问题，基本上是集合覆盖元素和集合的角色互换。令 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
于 2011-07-19T22:46:09.633 回答
2

起初我误解了问题的复杂性，并想出了一个函数来找到一个覆盖 m 个集合的集合 - 但后来我意识到它不一定是最小的一个：

cover <- function(sets, elements = NULL) {
  if (is.null(elements)) {
    # Build the union of all sets
    su <- integer() 
    for(si in sets) su <- union(su, si)
  } else {
    su <- elements
  }

  s <- su
  for(i in seq_along(s)) {
    # create set candidate with one element removed
    sc <- s[-i] 

    ok <- TRUE
    for(si in sets) {
      if (!any(match(si, sc, nomatch=0L))) {
        ok <- FALSE
        break
      }
    }

    if (ok) {
      s <- sc
    }
  }

  # The resulting set
  s
}

sets <- list(s1=c(1,3,4), s2=c(1,3), s3=c(4))
> cover(sets) # [1] 3 4

然后我们可以计时：

n <- 100  # number of elements
m <- 1000 # number of sets
sets <- lapply(seq_len(m), function(i) sample.int(n, runif(1, 1, n)))
system.time( s <- cover(sets) ) # 0.53 seconds

还不错，但仍然不是最小的。

显而易见的解决方案：生成元素的所有排列并传递给覆盖函数并保持最小的结果。这将接近“永远”。

另一种方法是生成有限数量的随机排列 - 这样您可以获得最小集合的近似值。

ns <- 10 # number of samples
elements <- seq_len(n)
smin <- sets
for(i in seq_len(ns)) {
   s <- cover(sets, sample(elements))
   if (length(s) < length(smin)) {
     smin <- s
   }
}
length(smin) # approximate smallest length
于 2011-07-20T15:17:37.037 回答
1

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

于 2011-07-19T16:51:33.477 回答
1

如果您只对算法感兴趣（而不是有效/可行的算法），您可以简单地生成基数递增的全域子集，并检查与 S 中所有集合的交集是否非空。一旦你得到一个有效的就停下来；基数是可能的最小值。

其复杂度为 2^|U| 在最坏的情况下，我认为。鉴于 Foo Bah 的答案，我认为您不会得到多项式时间的答案......

于 2011-07-19T16:53:44.613 回答