匈牙利算法(Hungarian Algorithm)是一种组合优化算法(combinatorial optimization algorithm)，用于求解指派问题(assignment problem)，算法时间复杂度为O(N^3)。Harold Kuhn发表于1955年，由于该算法基于两位匈牙利数学家的早期研究成果，所以被称作“匈牙利算法”。

       Python中的scipy.optimize.linear_sum_assignment可以很好的解决这个问题，这里用官方给的例子来讲一下对匈牙利算法的理解

       假设有三位工人A,B和C，需要分配他们每人完成一件工作；对于不同的工作他们所需要花费的时间不同，如下表所示。问题就是要找到一套耗时最小的指派方案。用矩阵表示如下：

	擦桌	拖地	扫厕所
A	4	1	3
B	2	0	5
C	3	2	2

匈牙利算法包含四步。前两步一次执行完，第三步和第三步会重复执行直到最优分配出现。算法的输入是n*n的矩阵，只有非负数。

Step 1: Subtract row minima （减去行最小值）

对于每一行，找到该行的最小值，然后该行的数都减去这个最小值

Step 2: Subtract column minima（减去列最小值）

同样的，对于每一列，找到该列的最小值，然后该列的数都减去这个最小值

Step 3: Cover all zeros with a minimum number of lines（用最少的线覆盖所有的0）

用最少的水平线和垂直线覆盖掉矩阵的所有0元素。如果需要n条线，那么在这些0中就存在最优解。算法结束

如果需要的线<n，继续第四步

Step 4: Create additional zeros（创建额外的0元素）

在第三步的的矩阵中，找到没被线覆盖的行列中的最小的元素，记作k。所有没被覆盖的元素都减去k，被覆盖两次的元素加上k

第一步，找出每一行中值最小的元素，然后把该行所有元素都减去这一最小值

 第二步，对于每一列，找到该列的最小值，然后该列的数都减去这个最小值

 第三步，用最少的水平线和垂直线覆盖掉矩阵的所有0元素。如果需要n条线，那么在这些0中就存在最优解。算法结束

 可以看到当前的覆盖所有的0需要两条线，<n，继续第四步

第四步，找到没被线覆盖的行列中的最小的元素，记作k。所有没被覆盖的元素都减去k，被覆盖两次的元素加上k

此时刚好用3条线即可覆盖所有的0，算法结束

即最后指派A拖地，B擦桌，C扫厕所

再来看代码的实现：

from scipy.optimize import linear_sum_assignment
 
cost =np.array([[4,1,3],[2,0,5],[3,2,2]])
row_ind,col_ind=linear_sum_assignment(cost)
print(row_ind)#开销矩阵对应的行索引
print(col_ind)#对应行索引的最优指派的列索引
print(cost[row_ind,col_ind])#提取每个行索引的最优指派列索引所在的元素，形成数组
print(cost[row_ind,col_ind].sum())#数组求和

输出结果：

[0 1 2]
[1 0 2]
[1 2 2]
5

输出的结果符合推导

有个英文网站感兴趣的可以看看：Steps of the Hungarian Algorithm - HungarianAlgorithm.com