如何找到覆盖矩阵中所有零的最少行数？

Question

我正在解决一个问题，我有一个 n x 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, 5, 1, 1]
  [2, 0, 0, 0, 0, 0]
  [1, 0, 0, 0, 0, 0]
  [3, 0, 0, 0, 0, 0]
  [1, 0, 0, 0, 0, 0]
  [3, 0, 0, 0, 0, 0]
}

在我的算法中，我选择了数组中最大的一个并覆盖了该行（将它们设置为 false），因此我无法再次访问它们。并将 Linelength 加 1。但它不适用于较长的线路和线路。

用大数字覆盖栏后：

{ 
  [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]
}

Answer 1

想象一下二分图，其中左侧部分包含列号 Xi，右侧部分包含行号 Yi，矩阵中的每个零定义相应行和列之间的边缘。

Kőnig 定理 表示最大匹配（蓝色边）等于最小顶点覆盖（红色列或行），因此每条边（矩阵中的零）都被一些红色顶点（列或行）覆盖。

因此，应用最大二分匹配算法的任何合适实现（例如Python networkx库中的maximum_matching）