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

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

补充笔记：

• 如果有多个同样好的解决方案，我需要找到all其中。 （能够找到额外的解决方案almost同样好也很有用，但不是必需的。）
• 矩阵元素都是非负的，其中许多元素为零。每行和每列将包含至少 1 个非零元素。
• 矩阵可以包含重复的元素。
• 矩阵不必是方形的。它的行数可能多于列数或反之亦然，但约束始终相同：任何行或列都不能使用两次。
• 这个问题也可以重新表述为在二分图的两半之间找到最大得分的边集，而无需重新使用任何节点。
• 如果有帮助，您可以假设有一些小的固定 k，这样没有行或列包含超过 k 个非零值。

如果有人好奇，矩阵的行代表要标记的项目，列代表标签，每个矩阵元素代表为项目分配标签的“一致性分数”。我想以最大化总体一致性的方式将每个标签恰好分配给一个项目。

我的建议是（1）找到以下元素的所有组合rule在每个组合中，没有两个来自同一行或同一列的元素 (2) 计算每个组合中元素的和 (3) 找到最大和以及相应的组合。

这里我只展示方阵的情况，非方阵也遵循类似的想法。

(1)假设矩阵是n*n，行序保持为1到n，我需要做的就是找到列索引的所有排列(1:n)，将行索引和一个列排列组合起来索引，然后我将获得遵循以下的一个组合中元素的位置rule，这样我就可以识别出所有组合中元素的位置。

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