Вызов Кода — Разделитель Собраний

Введение

Большие встречи тратят рабочее время. Наша цель — разделить большое собрание на несколько более мелких, чтобы среднее количество тем, которые обсуждает человек, было сведено к минимуму, но каждый человек должен присутствовать на каждом собрании, которое ему интересно.

Вход

Дана функция от набора тем \$T\$ к набору людей \$P\$, интересующихся этой темой $$f:T \rightarrow 2^P$$ и максимального размера раздела \$m\ $.

Это кодируется как массив массивов, где элемент \$f(i)\$ содержит темы человека \$i\$.

Тестовый пример

 m = 3
f = [
[9,7],
[3,7,6,4],
[3,1,2],
[7,5,4,2],
[6,2,8,1,4],
[3,7,2,9,8],
[4,3,2],
[3,4,6],
[1,9,5,3],
[6,4,1,2],
[9,7,3,1],
[1,7,4],
[5,1,7,2],
[5,2,7],
[4,2,6,9],
[6,4,1],
[6,5,9,8],
[9,1],
[9,1,5,6],
[1,2,4,8,7]                                                                     
]
 

Выход

Найдите разбиение \$T\$ (разбиение на непересекающиеся подмножества, покрывающие все множество) на $$X = {T_1, T_2, \ldots, T_n}$$, где \$n\le m\$ , так что минимизируется следующий член:

$$r = \sum_{T' \in X}{(|(\bigcup_{t \in T'} f(t))|\times |T'|)} $$

Чтобы лучше понять \$r\$, если на обсуждение каждой темы уходит час, то \$r\$ — это общее количество человеко-часов, необходимых для проведения собраний.

Если существует несколько размеров разделов с одинаковым \$r\$, \$n\$ также следует минимизировать.

Вывод должен содержать раздел \$X\$ в виде двумерного массива, например:

$$X = [[0,1,2,3],[4,5,6],[7,8,9]] $$

Условие победы

Я ищу самый быстрый алгоритм, который находит абсолютный минимум \$r\$ и \$n\$.

R с lpSolve

Превратите задачу в задачу целочисленного линейного программирования с переменными \$2^t\$ и ограничениями \$t+1\$, где \$t\$ — количество тем. Функция стоимости модифицируется путем умножения ее на \$m\$ и добавления размера раздела. Это делает размер раздела вторичной целью оптимизации.

 
 [[1,2,3,4],[6,8],[5,7,9]] 
 

В Debian для этого нужен пакет > source("opt.r") Loading required package: lpSolve > opt(3,f) [[1]] [1] 1 2 3 4 [[2]] [1] 6 8 [[3]] [1] 5 7 9 > . The code assumes that the topics start with 1 and that each topic number up to the maximum is used. Input and output is as list of vectors, which is not too nice. The test case example is defined in the code, but the list can of course also be entered directly.

Чтобы использовать его, запустите source and then R файл кода и используйте функцию следующим образом:

Так require("lpSolve") decode <- function(n) { res <- c() i <- 1 while (n>0){ if (n %% 2 == 1) res <- c(res,i) i <- i+1 n <- n %/% 2 } res } opt <- function(m,p) { nr_pers <- length(p) nr_topics <- max(unlist(p)) x <- array(0,c(nr_topics,nr_pers)) for (i in 1:nr_pers) for (j in 1:length(p[[i]])) x[p[[i]][[j]],i] <- 1 l <- array(0,c(2^nr_topics,nr_pers)) cb <- rep(0,2^nr_topics) w <- rep(1,2^nr_topics) mt <- matrix(0,nr_topics+1,2^nr_topics) mt[nr_topics+1,1] <- 1 len <- 1 for (i in 1:nr_topics) { for(j in 1:len) { j1 <- len+j l[j1,] <- l[j,]+x[i,] cb[j1] <- cb[j] + 1 w[j1] <- m*sum(l[j1,] != 0)*cb[j1]+1 mt[,j1] <- mt[,j] mt[nr_topics+1-i,j1] <- 1 } len <- 2*len } dir <- c(rep("=",nr_topics),"<=") rhs <- c(rep(1,nr_topics),m) sol <- lp("min",w,mt,dir,rhs,all.bin=TRUE)$solution res <- list() j <- 1 for (i in 1:length(sol)) if (sol[i]==1) { res[[j]] <- decode(i-1) j <- j+1 } res } # test case f <- list( c(9,7), c(3,7,6,4), c(3,1,2), c(7,5,4,2), c(6,2,8,1,4), c(3,7,2,9,8), c(4,3,2), c(3,4,6), c(1,9,5,3), c(6,4,1,2), c(9,7,3,1), c(1,7,4), c(5,1,7,2), c(5,2,7), c(4,2,6,9), c(6,4,1), c(6,5,9,8), c(9,1), c(9,1,5,6), c(1,2,4,8,7)) is an optimal partition for the test case.