hungarian-algorithm - 如何找到覆盖二维数组中所有零点所需的最少行数？

Question

我正在努力实现匈牙利算法的一个不错的实现，但是我被困在如何找到覆盖数组中所有零的最小行数

我还需要知道这些行以便稍后进行一些计算

这里是解释:

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

在第 3 步中它说

Use as few lines as possible to cover all the zeros in the matrix. There is no easy rule to do this - basically trial and error.

试错法在计算方面意味着什么？例如，如果我有一个 5 行 5 列的二维数组，那么

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

还有比这更高效的吗？

提前致谢

Answer 1

这里需要实现二分匹配算法。您在图中有两个分区 - 其中一个中的顶点代表行，另一个中的顶点代表表中的列。 row_i 和 column_j 之间有一条边当且仅当单元格 (i,j) 中有一个 1。然后创建最大二分匹配。在二分匹配算法的最后一次迭代之后，您需要找出哪些顶点通过增量路径与匹配源连接。增量路径是仅使用具有正容量的边的路径。你应该有这样的图片:

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

找到最大二分匹配后，找出哪些行和列可以通过来自汇的正容量边到达。现在使用以下算法找到您需要划痕的最小行数和列数 - 您划掉所有无法从源访问的行和所有可访问的列，这是您的最佳解决方案。

希望这个回答对你有帮助。