Menu
I'm trying to implement the Hungarian algorithm. Everything is fine except for when the matrix isn't square. All the methods I've searched are saying that I should make it square by adding dummy rows/columns, and filling the dummy row/column with the maximum number in the matrix. My question is that won't this affect the final result? Shouldn't the dummy row/column be filled with at least max+1?
381
How is the Hungarian method applied for obtaining a solution if the matrix is a rectangle? You would first add "dummy" row(s) or column(s) to make it square, with the "dummy" value being the highest value from that column or row, respectively.
No, we cannot square a non-square matrix. This is because of the fact that the number of columns of a matrix A must be equal to the number of rows of matrix B in order to calculate AB.
The dummy values should all be zero. The point is that it doesn't matter which one you choose, you're going to ignore those choices in the end because they weren't in the original data. By making them zero (at the start), your algorithm won't have to work as hard to find a value you're not going to use.
182
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
