如何找到覆盖二维数组中所有零所需的最小行数？

Question

我正在尝试制作一个体面的匈牙利算法实现，但是我卡在了如何找到覆盖数组中所有零的最小行数上。

同时，我需要知道这些行以便稍后进行一些计算。

以下是说明：

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

在第三步中，它说：

尽可能使用较少的行来覆盖矩阵中的所有零。这没有简单的规则 - 基本上是试错。

就计算而言，“试错”是什么意思？例如，如果我有一个5行5列的2D数组，则：

第一行可以覆盖所有零，第一行和第二行，第一行和第一列等等，组合太多了。

难道没有比这更有效的方法吗？

提前感谢您。

- jan1

Answer 1

你需要在这里实现二分图匹配算法。在图中有两个部分-其中一个部分的顶点代表表格中的行，另一个部分的顶点代表表格中的列。如果单元格（i，j）中有1，则行_i和列_j之间存在一条边。然后创建最大匹配的二分图。在二分图匹配算法的最后一次迭代后，你需要找出哪些顶点通过增量路径与匹配源相连。增量路径是仅使用正容量边的路径。你应该有如下图片：

         row_1                  col_1
        /                             \
       / - row_2                col_2 -\
source  - ....     some_edges           \ sink
       \                                / 
        \ - row_n                col_n /
                                 .... /
                                 col_m

在找到最大二分匹配后，查找通过正容边从汇点可达的行和列。现在使用以下算法找到需要划掉的最小行数和列数 - 划掉所有不能从源点到达的行和所有可以到达的列，这是您的最优解。

希望这个答案对您有所帮助。

- Ivaylo Strandjev

---

虽然它会给出一组覆盖所有零的线，但这并不会给出最少的线数；尝试使用一个在第二行和第二列中有零的3x3矩阵来运行算法。你可以用2条线覆盖所有的零，但是这个算法会告诉你要用3条线。 - gwilkins

我打错了 - 你需要找到从源可达的顶点，而不是从汇点。在您的示例中，执行最大匹配（假设为r_1-> c_2，r_2-> c_1）后，源可达的顶点是r_1、r_3、c_2，因此您选择r_2和c_2，正如我所解释的那样。这个解决方案不仅仅是猜测 - 这就是匈牙利算法的实现方式，我已经用这种方法解决了一些问题（例如：http://acm.timus.ru/problem.aspx?space=1&num=1076）。 - Ivaylo Strandjev

我认为我对你所说的“可从源访问”有些误解。如果您的匹配关系是r_1->c_2，r_2->c_1，那么r_3如何可从源访问？ - gwilkins

哦，没关系，你说的是在剩余图中可达。 - gwilkins

Answer 2

我不太确定为什么他们告诉你要进行试错。然而，匈牙利算法并不需要指数时间。请查看维基百科，它会通过一个示例向您展示如何计算最小行数（请参阅第3步）：

http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

该文章还包括实现的链接以及一些在线课程笔记，这些笔记提供了比您使用的匈牙利算法更完整（尽管也更技术）的描述。

- gwilkins

Answer 3

试错法意味着O((n+m)!)的复杂度。

最多只需要选择min(n,m)行，因为选择所有行或列将覆盖所有0。

对于大问题，我会实现动态规划算法来解决这一步骤。

- Colin D