在 R 中设置覆盖近似
Set cover approximation in R
我正在尝试解决或实现 R 中 set cover problem 的近似值。给定这样的数据框。
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
我想计算覆盖 n（宇宙）中所有独特元素的较小数量的集合（第 sets 列）。在这个例子中有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过它，我知道可以应用贪心算法来找到近似值。我也检查了这个link，其中他们提到了两个包来解决这些问题，LPsolve 和Rsymphony，但我什至不知道如何开始。在我现实生活中的例子中，我有超过 40,000 个集合，每个集合包含 1,000 到 10,000 个元素和 80,000 个 unviverse 或 unique 元素。
非常感谢任何有关如何开始或继续的帮助或指导。
数据
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")
CRAN 上提供了 lpSolve 包来解决线性规划问题。使用你的 link 得到了非常有名望的 Hans Borchers 的回应，以及 http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf 中的一个稍微复杂的例子（从第 4/5 页开始）作为模板来理解设置的正确结构，然后对 ?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是最小覆盖。 "column coefficients" 决定选择 "sets".
我正在尝试解决或实现 R 中 set cover problem 的近似值。给定这样的数据框。
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
我想计算覆盖 n（宇宙）中所有独特元素的较小数量的集合（第 sets 列）。在这个例子中有两个集合：s1 {1, 2, 3} 和 s4 {4, 5}。我在维基百科和互联网上读过它，我知道可以应用贪心算法来找到近似值。我也检查了这个link，其中他们提到了两个包来解决这些问题，LPsolve 和Rsymphony，但我什至不知道如何开始。在我现实生活中的例子中，我有超过 40,000 个集合，每个集合包含 1,000 到 10,000 个元素和 80,000 个 unviverse 或 unique 元素。
非常感谢任何有关如何开始或继续的帮助或指导。
数据
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")
CRAN 上提供了 lpSolve 包来解决线性规划问题。使用你的 link 得到了非常有名望的 Hans Borchers 的回应，以及 http://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf 中的一个稍微复杂的例子（从第 4/5 页开始）作为模板来理解设置的正确结构，然后对 ?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是最小覆盖。 "column coefficients" 决定选择 "sets".