The Algoritm takes its name due to Hungarian mathematicians König and Egervary who where key developing a solution who enters in the realm of combinatorial optimization problems.
Recommended Readings:
König D. " Theorie der Endlichen und Unendlichen Graphen " 1912
Egervary J. " Matrixok Kombinatorious Tulajdosagairol " 1931.
The problem is balanced so that rows=columns . But if this is not the case you can always balance the problem in the same fashion that we did in transportation algorithms.
The zeroes shown at the end of algorithm mark the possible solutions whenever they can be assimilated to a unitary permutation matrix P .
When you can find more than one Permutation matrixes then multiple solutions appear.
The matching is done by means of this expression.
Job[i] === employee j .
Enjoy the example, I've chosen job assignment because it is very straight , but there are numerous
instances on wich this method may be employed.
0 Yorumlar