关注我的question 我使用以下代码:
dist<-c('att1','att2','att3','att4','att5','att6')
p1<-c('att1','att5','att2')
p2<-c('att5','att1','att4')
p3<-c('att3','att4','att2')
p4<-c('att1','att2','att3')
p5<-c('att6')
....
p32<-c('att35','att34','att32')
在实际情况下,可以有 1024 个向量。
我想找到所有相关的p
,它们的统一将是 dist 的最大分量。在这种情况下,解决方案将是 p1
、p3
、p5
。我想选择最小数量的p
。另外,如果没有办法覆盖所有的 dist 分量,所以我想选择具有最少数量的向量(p)的最大覆盖。
N = 32
library(qdapTools)
library(dplyr)
library(data.table)
## generate matrix of attributes
attribute_matrix <- mtabulate(list(p1, p2, p3, p4, p5,...,p32))
library (bigmemory)
## generate matrix of attributes
grid_matrix <- do.call(CJ, rep(list(1:0), N)) %>% as.big.matrix
Error: cannot allocate vector of size 8.0 Gb
我尝试了另一种方法:
grid_matrix <- do.call(CJ, rep(list(1:0), N)) %>% as.data.frame
grid_matrix <- as.matrix (grid_matrix)
仍然遇到同样的错误。
如何修复它并将其用于大数据?我想继续:
colnames(grid_matrix) <- paste0("p", 1:N)
combin_all_element_present <- rowSums(grid_matrix %*% attribute_matrix > 0) %>% `==`(., ncol(attribute_matrix))
grid_matrix_sub <- grid_matrix[combin_all_element_present, ]
grid_matrix_sub[rowSums(grid_matrix_sub) == min(rowSums(grid_matrix_sub)), ]
最佳答案
这称为集合覆盖问题。可以使用整数线性规划来求解。设 x1, x2, ... 为 0/1 变量(每个 p 变量一个),并将 p1, p2, ... 表示为 0/1 向量 P1, P2, ... 并将 dist 表示为 0/1向量D。那么问题可以表述为:
min x1 + x2 + ... + x32
such that
P1 * x1 + P2 + x2 + ... + P32 * x32 >= D
R 代码如下。首先创建一个列表 p
,其中 p 个向量按排序顺序排列。使用 mixedsort
使 p32 出现在末尾,而不是紧跟在 p3 之后。将attnames定义为所有p向量中所有att名称的集合。
然后制定目标函数(等于封面中 p 的数量)、约束矩阵(由 P 向量作为列组成)和约束方程的右侧(dist 作为 0/1 向量)。最后运行整数线性程序并将解从 0/1 向量转换为 p 个名称的向量。
library(gtools)
library(lpSolve)
p <- mget(mixedsort(ls(pattern = "^p\\d+$")))
attnames <- mixedsort(unique(unlist(p)))
objective <- rep(1L, length(p))
const.mat <- sapply(p, function(x) attnames %in% x) + 0L
const.rhs <- (attnames %in% dist) + 0L
ans <- lp("min", objective, const.mat, ">=", const.rhs, all.bin = TRUE)
names(p)[ans$solution == 1L]
## [1] "p2" "p4" "p5"
约束矩阵的每个 attnames
条目为一行,每个 p
向量为一列。
该解决方案生成 dist
中那些 attnames
元素的最小覆盖。如果 dist
的每个元素都出现在至少一个 p
向量中,则解将表示 dist
的覆盖。如果不是,解决方案将表示一个或多个也在 dist
中的 p
向量中的这些 att 名称的覆盖;因此,这处理了问题中讨论的两种情况。 dist
未覆盖的元素是:
setdiff(dist, attnames)
因此,如果长度为零,则解决方案代表 dist
的完整覆盖。如果不是,则解决方案代表覆盖
intersect(dist, attnames)
代码中完成的排序并不是严格需要的,但通过按逻辑顺序排列约束矩阵的行和列,可以更轻松地处理优化的各种输入。
注意:在运行上述代码之前运行问题中的此代码:
dist<-c('att1','att2','att3','att4','att5','att6')
p1<-c('att1','att5','att2')
p2<-c('att5','att1','att4')
p3<-c('att3','att4','att2')
p4<-c('att1','att2','att3')
p5<-c('att6')
p32<-c('att35','att34','att32')
关于r - 大数据列表覆盖最少数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44628888/