时间戳

首页 > 解决方案 > 从矩阵中提取总和最大的元素而不重复行或列的算法？

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

问题描述

我有一个数字矩阵，我需要提取具有最大可能总和的元素集，但必须遵守不能有 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。

补充说明：

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

标签： ralgorithmmatrix

解决方案

这里有 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

但这不会导致多种解决方案，因此不会进一步发展以提取索引。

推荐阅读