Hungarian algorithm

The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry.

Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955. Kuhn's original publication.
Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistics Quarterly, 3: 253–258, 1956.

https://en.wikipedia.org/wiki/Hungarian_algorithm

James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial .[3] Since then the algorithm has been known also as the Kuhn–Munkres algorithm or Munkres assignment algorithm.

The Munkres module provides an implementation of the Munkres algorithm (also called the Hungarian algorithm or the Kuhn-Munkres algorithm), useful for solving the Assignment Problem.

https://pypi.python.org/pypi/munkres/1.0.5.4

https://github.com/bmc/munkres/blob/master/munkres.py



In [46]:

    
from munkres import Munkres, make_cost_matrix, print_matrix



In [43]:

    
matrix = [[12, 4, 2],
          [8, 7, 6],
          [7, 5, 2]]
print_matrix(matrix, msg='Profit Matrix')









    



Profit Matrix
[12,  4,  2]
[ 8,  7,  6]
[ 7,  5,  2]



In [44]:

    
cost_matrix = make_cost_matrix(matrix)
print_matrix(cost_matrix, msg='Cost Matrix')









    



Cost Matrix
[ 0,  8, 10]
[ 4,  5,  6]
[ 5,  7, 10]



In [45]:

    
m = Munkres()
indexes = m.compute(cost_matrix)

total = 0
for row, column in indexes:
    value = matrix[row][column]
    total += value
    print('(%d, %d) -> %d' % (row, column, value))

print('Total profit=%d' % total)









    



(0, 0) -> 12
(1, 2) -> 6
(2, 1) -> 5
Total profit=23



In [ ]: