非方阵中类最大团的最大全1稠密区域如何求解？

给定0-1非方阵，目标是找到可通过重排行列得到的内部全为1的最大矩形块（接受局部最优解）。比如示例矩阵：

1    1    0
1    1    0
1    1    0
1    0    1

预期返回结果为rows=c(1, 2, 3), columns=c(1,2)。

问题本质 #

这个问题等价于寻找最大的行子集和列子集，使得该子集中的每个行在对应列子集上的元素全为1——重排行列后就能形成规整的全1矩形。这和二分图的最大二分团问题完全对应：将行、列分别作为二分图的两个顶点集，矩阵中元素为1则对应行、列顶点间连边，最大全1矩形就是二分图中两两相连的行、列顶点子集。

解法思路 #

1. 二分图工具精确求解（R语言） #

利用igraph库的二分图最大二分团功能，直接转化求解：

library(igraph)

# 示例矩阵
mat <- matrix(c(1,1,0,
                1,1,0,
                1,1,0,
                1,0,1), nrow=4, byrow=TRUE)

# 构建二分图
row_nodes <- paste0("R", 1:nrow(mat))
col_nodes <- paste0("C", 1:ncol(mat))
edges <- which(mat == 1, arr.ind = TRUE)
edges <- cbind(row_nodes[edges[,1]], col_nodes[edges[,2]])
g <- graph_from_edgelist(edges, directed = FALSE)
V(g)$type <- c(rep(FALSE, nrow(mat)), rep(TRUE, ncol(mat))) # 标记二分图顶点类型

# 查找最大二分团
biclique <- max_biclique(g)
# 提取行、列索引
selected_rows <- as.integer(sub("R", "", names(biclique$left)))
selected_cols <- as.integer(sub("C", "", names(biclique$right)))

# 输出结果
cat("rows=c(", paste(selected_rows, collapse=", "), "), columns=c(", paste(selected_cols, collapse=", "), ")\n")

运行后会得到预期的rows=c(1, 2, 3), columns=c(1, 2)。

2. 启发式贪心解法（适合大规模矩阵） #

如果矩阵规模较大，精确解效率不足，可采用贪心策略快速获取局部最优解：

find_max_dense_region <- function(mat) {
  max_size <- 0
  best_rows <- c()
  best_cols <- c()
  
  # 从列出发遍历扩展
  for (col in 1:ncol(mat)) {
    current_rows <- which(mat[, col] == 1)
    if (length(current_rows) == 0) next
    current_cols <- which(colSums(mat[current_rows, , drop=FALSE]) == length(current_rows))
    current_size <- length(current_rows) * length(current_cols)
    
    if (current_size > max_size) {
      max_size <- current_size
      best_rows <- current_rows
      best_cols <- current_cols
    }
  }
  
  # 从行出发遍历扩展，避免遗漏
  for (row in 1:nrow(mat)) {
    current_cols <- which(mat[row, ] == 1)
    if (length(current_cols) == 0) next
    current_rows <- which(rowSums(mat[, current_cols, drop=FALSE]) == length(current_cols))
    current_size <- length(current_rows) * length(current_cols)
    
    if (current_size > max_size) {
      max_size <- current_size
      best_rows <- current_rows
      best_cols <- current_cols
    }
  }
  
  list(rows = best_rows, columns = best_cols)
}

# 测试示例
result <- find_max_dense_region(mat)
cat("rows=c(", paste(result$rows, collapse=", "), "), columns=c(", paste(result$columns, collapse=", "), ")\n")

该方法通过从单个1元素出发，逐步扩展行/列集合，保持矩形内全1，快速得到近似最优解。

内容的提问来源于stack exchange，提问作者R Greg Stacey