从矩阵中提取总和最大的元素而不重复行或列的算法？

Question

我有一个数字矩阵，我需要提取具有最大可能总和的元素集，但受到任何 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

我的建议是（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