javarowscalculated-columnshungarian-algorithm

Hungarian algorithm dead end

I am following the tutorial on Youtube of the Indian guy about the Hungarian problem. I stack in the point where he decides which rows and columns are going to be selected for the next step. His example do not have the problem I am facing. Here is the table of my example:

2 1 0 0 0 3
2 0 4 5 2 7
0 7 0 0 0 5
3 2 3 1 2 0
0 0 6 3 3 5
3 4 5 2 0 3

So let's start the rows and columns selection step by step:

  1. first row contains >1 zeros => go to next row
  2. select (2,1) zero and add (5,1) to suspended zeros
  3. third row contains >1 zeros => go to next row
  4. select (4,6) zero
  5. select (5,1) zero and add (3,1) to suspended zeros
  6. select (6,5) zero and add (3,5), (1,5) to suspended zeros

Now, the zeros that are left are (1,3), (1,4), (3,3), (3,4)

I cannot find a way to deal with them nor with column wise or row wise. What should I do with them?

Here is the table in the end:

2     1     0?    0?    0(su) 3
3     0(se) 4     5     2     7
0(su) 7     0?    0?    0(su) 5
3     2     3     1     2     0(se)
0(se) 0(su) 6     3     3     5
3     4     5     2     0(se) 3

where

Solution

  • In this particular example, we can just arbitrarily select a 0. Selecting the top left one gives us

    2     1     0(se) 0(su) 0(su) 3
3     0(se) 4     5     2     7
0(su) 7     0(su) 0?    0(su) 5
3     2     3     1     2     0(se)
0(se) 0(su) 6     3     3     5
3     4     5     2     0(se) 3

    We can then select the final free 0 and be done.

    This doesn't always work though. Consider

    0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4

    (If you'd prefer a video, I'm using the same problem as here, though I'll actually solve it.)

    We can't select anything from the start, so we arbitrarily select the first 0.

    0(se) 0(su) 0(su) 0(su)
0(su) 0     0     0
0(su) 0     1     2
0(su) 0     3     4

    Now we can select (1,3) because it's the only free 0 in its row.

    0(se) 0(su) 0(su) 0(su)
0(su) 0(su) 0     0
0(su) 0(se) 1     2
0(su) 0(su) 3     4

    and then (3,1) because it's the only free 0 in its column.

    0(se) 0(su) 0(su) 0(su)
0(su) 0(su) 0(se) 0(su)
0(su) 0(se) 1     2
0(su) 0(su) 3     4

    This gives us 3 total assignments, but we need 4 for a solution, and there are no more available 0's to assign. It's possible that there isn't a solution at this point, and so we need to continue on in the Hungarian Algorithm to the line drawing step.

    Professor G. Srinivasan walks through this in the video I linked, so I'll skip to the result. If the number of lines drawn is more than the number of assignments we are looking for, we continue on with the rest of the Hungarian Algorithm appropriately; if it's less, something went wrong in a previous step and you should go back and check your work; but if it's equal (as it is in this example), then we know that there is an optimal solution here that we haven't found.

    My solution to problematic arbitrary assignments, is more arbitrary assignments. The 4th row is the only one at this point without an assignment, so we'll start there and assign its first 0 (suspended 0s don't matter now so I've not marked them).

    0(se) 0     0     0
0     0     0(se) 0
0     0(se) 1     2
0(se) 0     3     4

    This is obviously problematic as we'd already made an assignment in the first column. To fix this, we need to move one of them somewhere else. Fortunately the 4th row still doesn't have an assignment, and (1,4) is a zero, so we can move the assignment in (1,1) to (1,4).

    0     0     0     0(se)
0     0     0(se) 0
0     0(se) 1     2
0(se) 0     3     4

    There are now no conflicts, and we have 4 assignments, so this is our solution.