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

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