从矩阵中提取元素最大的算法，且不重复选择行或列？

Question

我有一个数值矩阵，需要提取最大可能总和的元素集，但限制为不能选择同一行或列中的任意两个元素。是否有适用于此问题的高效算法，并且是否有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

然后有三个同等好的解决方案：1,8,9；3,6,9；和5,6,7。它们总和为18。

额外注意事项：

- 如果有多个同样好的解决方案，我需要找到所有的解决方案。（能够找到几乎同样好的额外解决方案也很有用，但不是必要的。） - 矩阵元素都是非负数，其中许多将为零。每行和每列至少包含一个非零元素。 - 矩阵可以包含重复元素。 - 矩阵不一定是方阵。它可能有更多的行而不是列，或反之，但约束始终相同：不能重复使用任何行或列。 - 这个问题也可以重新制定为在不重复使用任何节点的情况下，在二分图的两个部分之间找到一组最大得分的边集合。 - 如果有帮助的话，您可以假设存在某个小的固定k，使得没有行或列包含超过k个非零值。

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

- Ryan C. Thompson

---

@AaronMontgomery 还要注意，您可以假定 m <= n 而不失一般性，因为如果您转置矩阵，则问题仍然相同。 - Ryan C. Thompson

如果矩阵的所有元素都相同，那么 n! 种方式会产生相同的结果。由于在平局情况下您想要全部结果，因此最好的方法是指数级的蛮力计算。 - user58697

这将把最坏情况减少到k!种方式。如果这是可以接受的，那么再次尝试暴力破解它，也许会有所帮助。 - user58697

@RyanC.Thompson 你需要更详细地说明用例吗？还是你只是对这个通用算法感兴趣？ - Allan Cameron

以下是一些可能对您有帮助的帖子：最大化表格总和，其中每个数字必须来自唯一的行和列; 在不同的行和列中查找矩阵元素之和的最大值; 从矩阵中最大化“非重叠”数字的总和。 - Henrik

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

- Xiang

---

这看起来像是一个可行的解决方案，Xiang，但它并不是非常可扩展的。即使是一个相当小的10 * 10矩阵，也有360万个长度为10的排列向量需要查找和适配到内存中。除非您有少于100个元素的矩阵，否则穷举搜索可能不是正确的方法。 - Allan Cameron

@AllanCameron 注意上面的评论指出，绝对最坏情况总是需要进行详尽搜索。因此，在一般情况下可能没有更好的解决方案。 - Ryan C. Thompson

@RyanC.Thompson 这是一个聪明的观察，但它并不意味着需要进行详尽的搜索，只需要生成所有排列即可。实际上，仅需检查所有元素是否相等，然后返回算法生成的排列集合，根本不需要进行任何搜索，这可能是您函数顶部有用的保护措施。同样，您希望将单位矩阵视为特殊情况，而不使用详尽的搜索。也许最好的解决方案是将蛮力算法作为最后的手段？ - Allan Cameron

@AllanCameron 我对典型矩阵的期望有一些想法，可以用来实现一些启发式快捷方式，但数据“嘈杂”得足以使我不能依赖一组启发式方法来覆盖每种情况，因此，如果我想要一个完全通用的解决方案，最坏情况似乎总是需要进行详尽的搜索（或更可能的是，如果问题规模变得太大并且启发式方法失败，则放弃）。 - Ryan C. Thompson

Answer 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

但这并不会导致多个解决方案，因此无法进一步提取指数。

- chinsoon12