Hungarian Algorithm: determining the minimum number of lines to cover all zeros

702 Views Asked by At

I am trying to implement the Hungarian Algorithm. Check the Wikipedia steps: https://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

Consider the following input (10 x 10):

x x 0 x 0 x 0 x x x
x x 0 x x x x x x x
0 0 x x x x x 0 x x
x x x x x 0 x x x x
x x x x x 0 x x x x
x x x 0 0 x x x x x
0 x x x x x x x x x
x x x x x x x x 0 0
x x x x x x x x x 0
x x x x x x x x 0 x

It requires 8 lines to cover all zeros (rows and cols indexed from 0): R0 R1 R2 R5 C0 C5 C8 C9.

However, follow the steps given in Wikepedia:

  1. Tag the zeros as 'assigned' or 'cross-out'. Assigned: (0, 2), Crossed-out: (0, 4) (0, 6) (1, 2); Assigned: (2, 0), Crossed-out: (2, 1) (2, 7) (6, 0); Assigned: (3, 5), Crossed-out: (4, 5); Assigned: (5, 3), Crossed-out: (5, 4); Assigned: (7, 8), Crossed-out: (7, 9) (9, 8); Assigned: (8, 9).
  2. Mark all rows having no assignments: R1 R4 R6 R9; mark all columns having zeros in newly marked rows: C2 C5 C0 C8; mark all rows having assignments in newly marked columns: R0 R3 R2 R7.
  3. Repeat the last two steps in 2 until no row or column could be marked: mark all columns having zeros in newly marked rows: R0->C4 C6, R3->none, R2->C1 C7, R7->C9; mark all rows having assignments in newly marked columns: C4 C6 C1 C7->none, C9->R8.

Now all rows except for R5 have been marked; all columns except for C3 have been marked. The number of lines required to cover all zeros would be 9 vertical + 1 horizontal = 10, which is incorrect.

Could anyone tell where I have made a mistake? Or the algorithm to obtain minimum lines itself is inperfect?

0

There are 0 best solutions below