如何寻找覆盖n×n矩阵所有零元素的最少直线数量？求对应算法

问题描述 #

给定一个n×n矩阵，需要确定覆盖所有零元素所需的最少水平线与垂直线数量，本质是找到最优的直线分配方式以最小化总覆盖数。

示例矩阵 #

(0, 1, 0, 1, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 0, 1)
(1, 1, 0, 1, 1)
(1, 0, 0, 1, 0)

最优解 #

(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)
(1, 1, x, 1, 1)
(x, x, x, x, x)

此时所需最少直线数量为4。

我的尝试 #

我曾尝试统计每行、每列的零元素数量，选择零元素最多的行/列进行覆盖并标记为不可重复选择，累加直线数量，但该方法对部分情况无效。比如覆盖零元素最多的列后，得到如下数组：

{ 
  [0, 1, 2, 0, 1, 1]
  [1, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0]
  [2, 0, 0, 0, 0, 0]
  [0, 0, 0, 0, 0, 0]
  [2, 0, 0, 0, 0, 0]
}

可行算法解决方案 #

这个问题可以通过二分图匹配结合Konig定理解决，具体步骤如下：

1. 构建二分图：将矩阵的所有行作为左顶点集合，所有列作为右顶点集合。对于矩阵中每个值为0的位置(i,j)，在左顶点i和右顶点j之间添加一条边。
2. 计算最大匹配数：使用二分图匹配算法（比如匈牙利算法）求出该二分图的最大匹配数。
3. 推导最少直线数：根据Konig定理，二分图的最小顶点覆盖数等于其最大匹配数。这里的最小顶点覆盖数，就对应覆盖所有零元素所需的最少直线数量——选中的顶点即为需要覆盖的行或列。

以你给出的示例矩阵为例，对应的二分图最大匹配数为4，因此最少需要4条直线，和示例的最优解完全一致。

为什么贪心方法无效？ #

贪心策略（每次选零最多的行/列）只能保证局部最优，无法确保全局最优。比如某些场景下，选择零元素较少的行/列，反而能让后续用更少的直线覆盖剩余的零元素，贪心会错过这种全局最优的组合。

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