How do I find the minimum number of rows needed to cover all zeros in a 2-D array?
I am trying to make a decent implementation of the Hungarian algorithm, but I am stuck on how to find the minimum number of rows that cover all zeros in an array
Also I need to know these lines in order to do some calculations later
here is the explanation:
http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf
in step 3 he says
Use as few rows as possible to cover all zeros in the matrix. There is no simple rule for this - mostly trial and error.
what does trial and error mean in terms of computation? If I have, for example, a 2d array of 5 rows and 5 columns, then
The first row can span all zeros, first and second, first row and first column, etc. etc. too many combinations
isn't there something more efficient than that?
early
source to share
You need to implement a two-way matching algorithm. You have two sections in a graph: the vertices in one represent rows, and the vertices in the other represent columns in the table. There is a line between the line i and column jif cell (i, j) has 1. Then you create the maximum two-way match. After the last iteration of the two-way matching algorithm, you need to figure out which vertices are connected via an incremental path to the source for your match. An incremental path is a path that uses only edges with positive capacitance. You should have an image like:
row_1 col_1
/ \
/ - row_2 col_2 -\
source - .... some_edges \ sink
\ /
\ - row_n col_n /
.... /
col_m
After you find the maximum two-way match, find which rows and columns are reachable through the edges of the positive container from the sink. Now the minimum number of rows and columns to be scratched can be found by the following algorithm: you cross out all rows that are inaccessible from the source and all available columns, and this is your optimal solution.
Hope this answer helps you.
source to share
I'm not really sure why they told you to do trial and error. However, the Hungarian algorithm does not require exponential time. Take a look at wikipedia for an example of how to determine the minimum number of lines (see Step 3):
http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation
The article also contains implementation links and some online notes that provide a fuller (albeit more technical) description of the Hungarian algorithm than the one you are using.
source to share