4

我正在尝试解决或实现 R 中的集合覆盖问题的近似值。给定这样的数据框。

  sets n
1   s1 1
2   s1 2
3   s1 3
4   s2 2
5   s2 4
6   s3 3
7   s3 4
8   s4 4
9   s4 5

列中元素的唯一数量n是：

unique(d$n)
[1] 1 2 3 4 5

我想计算sets覆盖 n （宇宙）中所有唯一元素的较小数量的集合（列）。在此示例中，有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过它，我知道可以应用贪心算法来找到近似值。我也检查了这个链接，他们在其中提到了解决此类问题的两个包，LPsolve并且Rsymphony，但我什至不知道如何开始。在我的现实生活示例中，我有 40,000 多个集合，每个集合包含 1,000 到 10,000 个元素以及 80,000 个非生物或独特元素。

任何有关如何开始或继续的帮助或指导将不胜感激。

数据

d <- structure(list(sets = structure(c(1L, 1L, 1L, 2L, 2L, 3L, 3L, 
4L, 4L), .Label = c("s1", "s2", "s3", "s4"), class = "factor"), 
    n = c(1, 2, 3, 2, 4, 3, 4, 4, 5)), .Names = c("sets", "n"
), row.names = c(NA, -9L), class = "data.frame")
4

1 回答 1

3

该lpSolve软件包可在 CRAN 上用于线性规划问题。在http://math.mit.edu/~goemans/18434S06/setcover-tamara中使用您的链接，该链接得到了非常有名的 Hans Borchers 的响应，以及一个稍微复杂的示例（从第 4/5 页开始） 。 pdf作为模板来理解设置的正确结构，然后对第一个示例进行修改?lp：

library( lpSolve)
?lp
# In Details: "Note that every variable is assumed to be >= 0!"
# go from your long-form rep of the sets to a wide form for a matrix representation
( items.mat<- t(table(d$sets,d$n))  )  # could have reversed order of args to skip t()
#---------
> dimnames(items.mat) = list( items=1:5, sets=paste0("s", 1:4) )
> items.mat
     sets
items s1 s2 s3 s4
    1  1  0  0  0
    2  1  1  0  0
    3  1  0  1  0
    4  0  1  1  1
    5  0  0  0  1
#---------
f.obj <-  rep(1,4)  # starting values of objective parameters by column (to be solved)
f.dir <- rep(">=",5) # the constraint "directions" by row
f.rhs <- rep(1,5)    # the inequality values by row (require all items to be present)

lp ("min", f.obj, items.mat, f.dir, f.rhs)$solution
#[1] 1 0 0 1

所以设置s1和s4是一个最小的封面。“列系数”决定“集合”的选择。

于 2016-08-27T19:31:54.930 回答