Problema
Queremos resolver el problema del conjunto de cobertura en R. Calcular el número mínimo de conjuntos necesarios que contenga todos los elementos del universo. En nuestro ejemplo el universo es U = {1, 2, 3, 4, 5} y los conjuntos son s1 = {1, 2, 3}, s2 = {2, 4}, s3 = {3, 4}, s4 = {4, 5}.
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
df <- 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")
Solución
En nuestro ejemplo la solución es obvia, los conjuntos s1 y s4 serían el número de conjuntos mínimo necesario. Sin embargo, deseamos implementarlo en R para ser capaces de resolver problemas que comprendan miles de conjuntos con miles de elementos dentro de cada uno.
# El universo, elementos únicos de todos los conjuntos.
unique(df$n)
[1] 1 2 3 4 5
Empleamos el paquete lpSolve para resolver problemas de programación lineal.
# Creamos una representación matricial a partir del data frame
# Se asume que cada variable es >= 0! (ver ?lp)
items.mat <- t(table(df$sets, df$n))
dimnames(items.mat) = list(items = 1:5, sets = paste0("s", 1:4))
items.mat
# Matriz
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) # Valores de las variables de las inecuaciones
f.dir <- rep(">=", 5) # La cadena de texto de las restricciones por fila
f.rhs <- rep(1, 5) # Los valores de la desigualdad por fila
lp("min", f.obj, items.mat, f.dir, f.rhs)$solution
[1] 1 0 0 1
La solución son los conjuntos s1 y s4 indicados por los coeficientes de las columnas: el 1º y el 4º.
Referencias