3

我正在尝试对匈牙利算法进行体面的实现，但是我被困在如何找到覆盖数组中所有零的最小行数

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

这是解释：

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

在第 3 步中它说

使用尽可能少的行来覆盖矩阵中的所有零。没有简单的规则可以做到这一点 - 基本上是反复试验。

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

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

没有比这更有效的吗？

提前致谢

4

3 回答 3

2

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

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

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

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

于 2012-04-09T14:30:03.183 回答
1

我不太清楚他们为什么告诉你要反复试验。然而，匈牙利算法不需要指数时间。看看 wikipedia，它会引导您了解如何计算最小行数的示例（查看第 3 步）：

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

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

于 2012-04-09T16:54:57.297 回答
0

反复试验意味着 O((n+m)!) 复杂度。

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

我会实现一个动态规划算法来解决大问题的这一步。

于 2012-04-09T14:19:41.610 回答