如何找到覆盖二维数组中所有零的最小行数? [英] How can I find the minimum number of lines needed to cover all the zeros in a 2 dimensional array?

问题描述

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

I'm trying to make a decent implementation of the hungarian algorithm however I'm stuck at how to find the minimum number of lines that cover all the zeros in an array

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

also I need to know these lines to make some computations later

这是说明:

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列的二维数组，那么

what does trial and error mean in terms of computation? If I have for example an 2d array of 5 rows and 5 columns then

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

The first row can cover all the zeros, the first and second, the first row and first column, etc etc too many combinations

没有比这更有效的东西了吗?

isn't there something more efficient than this?

预先感谢

推荐答案

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

You need to implement bipartite matching algorithm here. You have two partitions in the graph- the vertices in one of them represent the rows and the vertices in the other one represent the columns in the table. There is an edge between row_i and column_j iff there is a 1 in cell (i,j). Then you create maximum bipartite matching. After the last iteration of the bipartite matching algorithm you need to figure out which vertices are connected via a incremental path with the source for your matching. An incremental path is path using only edges with positive capacity. You should have picture like:

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

找到最大的两部分匹配之后，找到可通过接收器的正容量边缘到达哪些行和列.现在，可以使用以下算法找到需要暂存的最小行和列数-将源中无法访问的所有行和所有可访问的列都划掉，这是您的最佳解决方案.

After you find the maximum bipartite matching, find which rows and columns are reachable via positive-capacity edges from sink. Now the minimum number of rows and columns you need to scratch is found using the following algorithm - you cross out all the rows that are not reachable from the source and all the columns that are reachable and this is your optimal solution.

希望这个答案对您有帮助.

Hope this answer helps you.

这篇关于如何找到覆盖二维数组中所有零的最小行数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！