Так как этот вопрос требует алгоритмических c подходов к покрытию проектов, я предоставлю один, который дает точные ответы (или наилучший возможный дизайн), используя целочисленное программирование на R. Для каждого рассматриваемого вами k-кортежа ( k = 3 для вас, так как вы выбираете триплеты), определите переменную решения, которая принимает значение 1, если вы включаете его в свой дизайн, и 0, если нет. Таким образом, в вашем случае вы должны определить x_123, чтобы указать, выбран ли tuple (1,2,3), x_345 для (3,4,5) и т. Д.
Задача модели оптимизации состоит в том, чтобы чтобы свести к минимуму количество выбранных кортежей, то есть сумму всех ваших переменных решения. Однако для каждого t-кортежа (t = 2 в вашем случае) вам необходимо включить переменную решения, которая содержит этот t-кортеж. Это дает ограничение для каждого t-кортежа. Например, у нас x_123+x_124+x_125 >= 1 будет ограничение, которое требует, чтобы пара 12 находилась в некотором выбранном кортеже.
Это дает следующую модель оптимизации:
min x_123+x_124+...+x_345
s.t. x_123+x_124+x_125 >= 1 # constraint for 12
x_123+x_134+x_135 >= 1 # constraint for 13
...
x_145+x_245+x_345 >= 1 # constraint for 45
x_ijk binary for all i, j, k
Вы могли бы расширить это, чтобы потребовать r повторений каждого t-кортежа, изменив правую часть каждого неравенства на «r» и требуя, чтобы все переменные были целыми числами, а не двоичными.
Это легко решить с пакетом типа lpSolve в R:
library(lpSolve)
C <- function(v, k, tt, r) {
k.tuples <- combn(v, k)
t.tuples <- combn(v, tt)
mod <- lp(direction="min",
objective.in=rep(1, ncol(k.tuples)),
const.mat=t(apply(t.tuples, 2, function(x) {
apply(k.tuples, 2, function(y) as.numeric(sum(x %in% y) == tt))
})),
const.dir=rep(">=", ncol(t.tuples)),
const.rhs=rep(r, ncol(t.tuples)),
all.int=TRUE)
k.tuples[,rep(seq_len(ncol(k.tuples)), round(mod$solution))]
}
C(5, 3, 2, 1)
# [,1] [,2] [,3] [,4]
# [1,] 1 1 1 3
# [2,] 2 2 2 4
# [3,] 3 4 5 5
C(5, 3, 2, 3)
# [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
# [1,] 1 1 1 1 1 1 2 2 2 3
# [2,] 2 2 2 3 3 4 3 3 4 4
# [3,] 3 4 5 4 5 5 4 5 5 5
Хотя это точно решит вашу проблему, она не будет хорошо масштабироваться до больших размеров проблем. Это потому, что проблема NP-сложная - ни один известный точный алгоритм не будет хорошо масштабироваться. Если вам нужно решить большие проблемы, то эвристика, рекомендованная в других ответах, - ваш лучший выбор Или вы можете решить с помощью целочисленного программирования (как мы делаем здесь) и установить время ожидания; тогда вы будете работать с наилучшим решением, найденным по вашему тайм-ауту, которое представляет собой heuristi c решение проблемы в целом.