Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Hungarian algorithm - Last step of selecting 0s from such that each row and column has only one selected

I am trying to implement the Hungarian algorithm in Java. I have an NxN cost matrix. I am following this guide step by step and have reached step 9 -

"Select a matching by choosing a set of zeros so that each row or column has only one selected."

I already have the matrix with the 0s. I was trying to figure this out and the only thing that was working for me was a brute force method.

I also thought of choosing the first 0 I encounter, remove that column & row and repeat; But this method does not work.

Is there any trick or method? Something that's not too complex? Any suggestion would appreciated.

Thanks

like image 456
Ayrton Senna Avatar asked Oct 21 '22 15:10

Ayrton Senna


1 Answers

An answer from a Hungarian: :)

  • Calculate the number of 0 elements for each row and column. (call it row[] and column[])
  • Select the minimum positive value of the rows and columns. For example let it be column[3] (if the minimum value is found in a row, the same applies, only swap rows and columns) If you have more than one with the same value, select any.
  • Select a 0 element in that column, mark it. If you have more than one, select any, that has a positive row value. (Suppose it is row[1])
  • Set column[3] to 0 (next time we shouldn't select). Also set row[1] to 0.
  • Iterate in all elements in column[3], if you find a 0 element, decrease the corresponding row[i] value by 1
  • If you don't find a positive value in neither row or column, you are finished.
like image 128
gaborsch Avatar answered Oct 24 '22 11:10

gaborsch