Алгоритм извлечения элементов с наибольшей суммой из матрицы без повторения строк или столбцов?

Question

У меня есть числовая c матрица, и мне нужно извлечь набор элементов с максимально возможной суммой с учетом ограничения, что никакие 2 элемента не могут происходить из одной строки или одного столбца. Есть ли какой-либо эффективный алгоритм для этого, и есть ли реализация этого алгоритма для R?

Например, если матрица (с использованием записи матрицы R):

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

, тогда уникальное решение - [1,3], [2,1], [3,2], которое извлекает числа 9, 8 и 6, всего 23. Однако, если матрица:

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

, то есть 3 одинаково хороших решения: 1,8 , 9; 3,6,9; и 5,6,7. Все это в сумме составляет 18.

Дополнительные примечания:

• Если есть несколько одинаково хороших решений, мне нужно найти все из них. (Возможность найти дополнительные решения, которые почти также хороши, также была бы полезна, но не обязательна.)
• Все элементы матрицы неотрицательны, и многие из них будут нуль. Каждая строка и столбец будут содержать по крайней мере 1 элемент, отличный от нуля.
• Матрица может содержать повторяющиеся элементы.
• Матрица не обязательно должна быть квадратной. В нем может быть больше строк, чем столбцов, или наоборот , но ограничение всегда одно: ни одна строка или столбец не могут использоваться дважды.
• Эту проблему также можно переформулировать как нахождение максимального - оценка набора ребер между двумя половинами двудольного графа без повторного использования какого-либо узла.
• Если это помогает, вы можете предположить, что существует небольшое фиксированное k, такое, что ни одна строка или столбец не содержат более k ненулевые значения.

Если кому-то интересно, строки матрицы представляют элементы, которые нужно пометить, столбцы представляют метки, а каждый элемент матрицы представляет «оценку согласованности» для присвоения метки к элементу. Я хочу присвоить каждую метку ровно одному элементу таким образом, чтобы максимизировать общую согласованность.

Answer 1

Вот 2 варианта:

1) Подходя к этому как к задаче оптимизации, где целевая функция состоит в максимизации суммы выбранных элементов с учетом ограничений, что каждая строка и столбец не могут быть выбраны более одного раза.

пример данных:

set.seed(0L)
m <- matrix(sample(12), nrow=4)
#m <- matrix(sample(16), nrow=4)
m

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

код:

library(lpSolve)
nr <- nrow(m)
nc <- ncol(m)

#create the indicator matrix for column indexes
colmat <- data.table::shift(c(rep(1, nr), rep(0, (nc-1)*nr)), seq(0, by=nr, length.out=nc), fill=0)
#create indicator matrix for row indexes
rowmat <- data.table::shift(rep(c(1, rep(0, nr-1)), nc), 0:(nr-1), fill=0)
A <- do.call(rbind, c(colmat, rowmat))

#call lp solver
res <- lp("max",
    as.vector(m),
    A,
    rep("<=", nrow(A)),
    rep(1, nrow(A)),
    all.bin=TRUE,
    num.bin.solns=3)

пример вывода:

which(matrix(res$solution[1:ncol(A)], nrow=nr)==1L, arr.ind=TRUE)
     row col
[1,]   1   1
[2,]   4   2
[3,]   3   3

2) И приведенное выше приводит к жадному эвристический подход для выбора самого большого элемента и удаления выбранной строки и столбца, а затем повторения для меньшей матрицы:

v <- integer(min(nc, nr))
allix <- matrix(0, nrow=length(v), ncol=2)
for (k in seq_along(v)) {
    ix <- which(m == max(m), arr.ind=TRUE)
    allix[k,] <- ix
    v[k] <- m[ix]
    m <- m[-ix[1], -ix[2], drop=FALSE]
}
v
#[1] 12  9  8

Но это не приводит к множественным решениям и, следовательно, не развивает дальнейшее извлечение индексов.

Answer 2

Я предлагаю (1) найти все комбинации элементов, следуя правилу , что в каждой комбинации не должно быть двух элементов из одной строки или одного столбца (2) вычислить сумму элементов в каждой комбинации (3) найдите максимальную сумму и соответствующую комбинацию.

Здесь я показываю только случай квадратной матрицы, неквадратная матрица будет следовать аналогичной идее.

(1) Предположим, матрица n * n, сохраняйте порядок строк от 1 до n, все, что мне нужно сделать, это найти все перестановки индекса столбцов (1: n), после объединения индекса строки и одной перестановки индекса столбцов, затем я мог бы получить позиции элементов в одной комбинации, которые следуют правилу , таким образом я могу идентифицировать позиции элементов во всех комбинациях.

matrix_data <- matrix(c(6,2,1,4,9,5,8,7,3), byrow=T,nrow = 3)
## example matrix

n_length <- dim(matrix_data)[1]
## row length

all_permutation <- permn(c(1:n_length))
## list of all the permutations of columns index 

(2) Найти сумму элементы в каждой комбинации

index_func <- function(x){ ## x will be a permutation from the list all_permutation
  matrix_indexs <- matrix(data = c(c(1:n_length),x),
                         byrow = F, nrow = n_length)
  ## combine row index and column index to construct the positions of the elements in the matrix

  matrix_elements <- matrix_data[matrix_indexs]
  ## extract the elements based on their position

  matrix_combine <- cbind(matrix_indexs,matrix_elements)
  ## combine the above two matrices

  return(matrix_combine)
}


results <- sapply(all_permutation, sum(index_func(x)[,"matrix_elements"]))
## find the sums of all the combination

(3) Найдите максимальную сумму и соответствующую комбинацию

max(results) ## 18 maximum sum is 18

max_index <- which(results==max(results)) ## 1 2 4 there are three combinations

## if you want the complete position index
lapply(all_permutation[max_index], index_func)

## output, first column is row index, second column is column index, last column is the corresponding matrix elements
[[1]]
         matrix_elements
[1,] 1 1               6
[2,] 2 2               9
[3,] 3 3               3

[[2]]
         matrix_elements
[1,] 1 1               6
[2,] 2 3               5
[3,] 3 2               7

[[3]]
         matrix_elements
[1,] 1 3               1
[2,] 2 2               9
[3,] 3 1               8