I am trying to implement the Hungarian algorithm in Java. I am able to solve it for maticies that have a single optimum solution. However, when there is more than one optimum solution I am at a loss on how to solve it (proramatically speaking).
Take the example matrix.
3 1 1 4
4 2 2 5
5 3 4 8
4 2 5 9
After performing row and column reductions. The matrix will look like.
0 0 0 0
0 0 0 0
0 0 1 2
0 0 3 4
Now there are clearly multiple solutions to this, such as
0 0 0 0*
0 0 0* 0
0 0* 1 2
0* 0 3 4
and
0 0 0* 0
0 0 0 0*
0* 0 1 2
0 0* 3 4
How does one go about programming a method that finds at least one of these solutions? Arbitrarily assigning an initial 0 will often force you into a dead end. e.g. if the 0 at position 0,0 was assigned, the following would happen.
0* 0- 0- 0-
0- 0- 0* 0-
0- 0* 1- 2-
0- 0- 3- 4-
So how do I intelligently pick optimum solution locations?
If you hit a "dead end" you need to look for an augmenting path, as in unweighted maximum matching algorithms. See e.g. these lecture notes.