逻辑向量配对最大化：如何借助算法/库实现最大配对数量？

问题描述 #

我有一个由逻辑向量构成的数据框DF，定义如下：

DF <- data.frame(c(T,T,F), c(T,F,T), c(F,T,F))

需要找到满足对应位置值为TRUE的行-列配对，配对后的行和列不能再参与后续配对。目标是最大化配对数量，上述示例的最优配对方案为：

DF[3,2]
DF[2,3]
DF[1,1]

解法思路 #

这本质是二分图最大匹配问题：把所有行作为二分图的一个顶点集合，所有列作为另一个顶点集合，当DF[i,j]为TRUE时，在行顶点i和列顶点j之间连一条边。我们要找的就是这个二分图的最大匹配——每个顶点最多被匹配一次，同时匹配的边数最多。

R中的实现方法 #

方法1：用igraph包（简单直接） #

igraph专门提供了二分图最大匹配的函数，步骤如下：

1. 将数据框转为邻接矩阵：

adj_matrix <- as.matrix(DF)

2. 构建二分图对象：

library(igraph)
g <- graph_from_incidence_matrix(adj_matrix, directed = FALSE)

3. 计算最大匹配：

match_result <- max_bipartite_match(g)

4. 提取配对结果：
   从match_result$matching中可以拿到配对关系，示例中会得到行1匹配列1、行2匹配列3、行3匹配列2，和预期的最优方案完全一致。

方法2：用lpSolve包（线性规划思路） #

如果更倾向于用线性规划的逻辑求解，也可以用lpSolve实现：

library(lpSolve)
n_rows <- nrow(DF)
n_cols <- ncol(DF)
adj_matrix <- as.matrix(DF)

# 目标：最大化配对数量，所以每个可能配对的权重都是1
obj <- rep(1, n_rows * n_cols)

# 约束条件：每行、每列最多只能有一个配对
constraint_matrix <- rbind(
  kronecker(diag(n_rows), rep(1, n_cols)),  # 行约束：每行的配对变量和≤1
  kronecker(rep(1, n_rows), diag(n_cols))   # 列约束：每列的配对变量和≤1
)
constraint_dir <- rep("<=", n_rows + n_cols)
constraint_rhs <- rep(1, n_rows + n_cols)

# 限制：只有DF[i,j]为TRUE的配对才允许被选中
var_bounds <- matrix(c(0, 1), nrow = n_rows * n_cols, ncol = 2, byrow = TRUE)
var_bounds[as.vector(!adj_matrix), ] <- c(0, 0)  # 不满足条件的配对强制设为0

# 求解线性规划
lp_result <- lp("max", obj, constraint_matrix, constraint_dir, constraint_rhs,
                all.bin = TRUE, bounds = var_bounds)

# 提取最终的配对索引
matches <- which(matrix(lp_result$solution, n_rows, n_cols) == 1, arr.ind = TRUE)

运行后matches会输出所有行-列配对的位置，和示例的最优结果一致。

内容的提问来源于stack exchange，提问作者Fidel Alencar