Установить аппроксимацию покрытия в R

Я пытаюсь решить или реализовать приближение к задаче покрытия множеств в 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 наборов, каждый из которых содержит от 1000 до 10000 элементов, а также вселенную или уникальные элементы в 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")
Источник

1 ответ

Решение

lpSolve пакет доступен на CRAN для задач линейного программирования. Используя вашу ссылку, которая получила ответ от очень уважаемого Ганса Борхера, а также немного более сложный пример (начиная с стр. 4/5) в http://math.mit.edu/~goemans/18434S06/setcover-tamara.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 являются минимальным прикрытием. "Коэффициенты столбца" определяют выбор "множеств".

Источник
Другие вопросы по тегам