I'm trying to implement a Hungarian Algorithm in C.
I have the matrix:
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
And I'm up to the stage where I have to find the minimum amount of lines to cover all zeroes (making as many assignments as possible). Obviously, by inspection this is columns 1 and 3 and row 1.
Wikipedia suggests the following method:
If I follow this for my matrix above, I get:
35 0' 0 0
0' 30 0 5
55 5 0' 10
0 45 30 45
Where zero prime is the assigned zero. Then, following Wikipedia's instructions below, I mark row 4 (unassigned zero), column 1 (col with the unassigned zero), then row 2 (row with a zero in a marked col).
So that would suggest that the min lines to hit all zeroes are:
+--------
|
+--------
|
But this doesn't hit the zero at (2, 3). Relevant C code:
for (i = 0; i < M->size; i++) {
for (j = 0; j < M->size; j++) {
if (M->values[i][j] == 0) {
if (assigned_cols[j] == 0) {
assigned_cols[j] = 1; // We've assigned something in this col
assigned_rows[i] = 1; // We've assigned something in this row.
marked_rows[i] = 0;
total--;
break; // Go to the next row
} else {
marked_cols[j] = 1; // Then there exists a zero in this col in an unassigned row
mark_col(M, j); // marks all elements in column j
total++;
}
}
}
}
This code chooses which zeroes are zero prime (assigns zeroes).
Then this code marks all rows having assignments in newly-marked columns:
for (i = 0; i < M->size; i++) {
if (marked_cols[i] == 1) {
for (j = 0; j < M->size; j++) {
//iterating through rows
if (M->values[j][i] == 0) {
// then (j,i) is a zero in a marked col
// mark the row
if (marked_rows[j] != 1) {
total++;
marked_rows[j] = 1;
}
break; // no need to continue more
}
}
}
}
But this (and the wikipedia explanation) fails for my matrix above. How come?
Wikipedia is lacking explanation on the algorithm, the assignments will be done in the last step!
STEP 0
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
STEP 1-2 all rows-columns have at least one 0 so step 1 leaves array the same
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
STEP 3
All zeros in the matrix must be covered by marking as few rows and/or columns as possible
- - - -
| |
| |
| |
Note that no assignments are done thus far and you need to cover all zeros. Your cover left zero (2,3) uncovered!!
Now take min element that is not covered e.g 5 (take the 5 at position (2,4))
-Reduce (by 5) all elements that where not covered.
-Increase (by 5) all elements crossed by two lines.
-Rest remain same
So the array:
40 0 5 0
0 25 0 0
55 0 0 5
0 40 30 40
Now check again for min required lines: now you need 4 lines (equal to size n=4 of rows of array, so we stop).
Finally assignment: Start from lines with only one zero this will surely be assigned:
40 0 5 _
0 25 _ 0
55 _ 0 5
_ 40 30 40
Multiple assignments exist (I use _ for assignment).
More specifically two assignments we get: (one stated above with total cost 5) and:
40 _ 5 0
0 25 0 _
55 0 _ 5
_ 40 30 40
With also cost 5!
Based on comment it seems that I didn't get the exact part that op was asking so I will answer this specific part keeping the general description of the algorithm above.
The mistake (due to bad Wikipedia description) is here:
Where zero prime is the assigned zero. Then, following Wikipedia's instructions below, I mark row 4 (unassigned zero), column 1 (col with the unassigned zero), then row 2 (row with a zero in a marked col).
Totally agree till now but...it's not complete!!!
When correctly marking row2 you need to go to step 2 (of Wikipedia) and check again for columns with zeros in this case column 3 should also been marked, this also causes the row 3 to be marked as well (due to assigned zero in the newly marked column 3) and there you stop (no other rows or columns should be marked)!!
So overall the marked columns and rows:
+ +
35 0' 0 0
0' 30 0 5 +
55 5 0' 10 +
0 45 30 45 +
And the lines you get by choosing the marked columns and unmarked lines:
- - - -
| |
| |
| |
which is the right one as described in the first part of answer and leads to right results in next stages (also explained above).
One very similar post that states literally same thing can be found on mathstackexchange:
finding the minimum number of lines to cover all zeros in an assignment probem