二进制矩阵每行选1后列和最小方差的求解方法咨询

假设我们有一个二进制矩阵（元素仅为0或1），比如：

X = [[1, 1, 0, 0], [1, 0, 1, 1], [0, 0, 1, 1], [1, 1, 1, 1]]

要求每行只能保留一个1（其余置0），最终让各列的1的数量尽可能相同——也就是最小化列和的方差。比如上面的矩阵，最优结果可以是：

Y = [[1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0]]

每列恰好有1个1，方差为0，是完美的均匀分布。

下面分两种实用方案来实现这个需求：

方案一：贪心算法（高效易实现，适合大规模矩阵） #

贪心的核心逻辑是：每一步都选择能让当前列和最均匀的选项。具体步骤如下：

1. 初始化一个列和数组 col_sums，长度等于矩阵列数，初始值全为0，用来记录每列当前的1的数量。
2. 遍历矩阵的每一行：
   • 找出当前行中所有值为1的列的索引。
   • 在这些候选列中，选择col_sums值最小的那个列（如果有多个列和相同，随便选一个即可）。
   • 把当前行的这个列设为1，其余元素置0。
   • 更新col_sums，将选中列的值加1。

示例演示（用上面的X矩阵）： #

• 初始col_sums = [0,0,0,0]
• 第一行候选列是0、1，选列0 → col_sums = [1,0,0,0]，第一行变为[1,0,0,0]
• 第二行候选列是0、2、3，其中列2、3的col_sums最小（0），选列3 → col_sums = [1,0,0,1]，第二行变为[0,0,0,1]
• 第三行候选列是2、3，列2的col_sums最小（0），选列2 → col_sums = [1,0,1,1]，第三行变为[0,0,1,0]
• 第四行候选列是0、1、2、3，列1的col_sums最小（0），选列1 → col_sums = [1,1,1,1]，第四行变为[0,1,0,0]

最终得到的Y矩阵就是完美均匀的结果。

优缺点： #

• 优点：时间复杂度是O(rows*cols)，效率极高，适合处理超大矩阵；实现简单，不需要依赖复杂库。
• 缺点：不一定能得到全局最优解（极端情况下可能出现局部最优），但绝大多数场景下结果足够接近最优。

方案二：整数规划（精确最优解，适合中小规模矩阵） #

如果需要严格的全局最优解，可以把问题建模为整数线性规划（ILP），通过求解器找到精确解。

建模思路： #

• 定义变量y_ij：当第i行选择第j列的1时，y_ij=1，否则y_ij=0（且只有当X[i][j]=1时，y_ij才能为1）。
• 约束条件：
  1. 每行必须选一个1：sum(y_ij for j in 所有列) = 1（对每个i）。
  2. 只能选原矩阵中为1的位置：y_ij ≤ X[i][j]（对所有i,j）。
• 目标函数：最小化列和的方差。由于方差sum((c_j - avg)^2)等价于sum(c_j²) - n*avg²（其中c_j是第j列的和，avg是总行数/总列数，n是总行数），而n*avg²是常数，所以我们可以简化为最小化sum(c_j²)。

Python代码实现（使用pulp库）： #

首先安装pulp：

pip install pulp

然后编写代码：

import pulp

# 输入矩阵X
X = [[1, 1, 0, 0], [1, 0, 1, 1], [0, 0, 1, 1], [1, 1, 1, 1]]
rows = len(X)
cols = len(X[0])

# 创建ILP问题，目标是最小化
prob = pulp.LpProblem("Minimize_Column_Sum_Variance", pulp.LpMinimize)

# 定义变量：仅当X[i][j]为1时，创建二进制变量y_ij
y = []
for i in range(rows):
    row_vars = []
    for j in range(cols):
        if X[i][j] == 1:
            var = pulp.LpVariable(f"y_{i}_{j}", cat="Binary")
            row_vars.append(var)
        else:
            row_vars.append(None)
    y.append(row_vars)

# 计算每列的和c_j
c = []
for j in range(cols):
    col_sum = pulp.lpSum([y[i][j] for i in range(rows) if X[i][j] == 1])
    c.append(col_sum)

# 目标函数：最小化sum(c_j²)
prob += pulp.lpSum([cj ** 2 for cj in c])

# 添加约束：每行必须选一个1
for i in range(rows):
    prob += pulp.lpSum([var for var in y[i] if var is not None]) == 1

# 求解问题
prob.solve()

# 生成结果矩阵Y
Y = [[0]*cols for _ in range(rows)]
for i in range(rows):
    for j in range(cols):
        if X[i][j] == 1 and pulp.value(y[i][j]) == 1:
            Y[i][j] = 1

# 输出结果
print("最优结果矩阵Y：")
for row in Y:
    print(row)

优缺点： #

• 优点：能得到全局最优解，适合对结果精度要求高的场景。
• 缺点：时间复杂度较高，当矩阵规模很大（比如rows/cols超过100）时，求解时间会显著增加；需要依赖第三方求解库。

内容的提问来源于stack exchange，提问作者Tùng Dương Quang