问题

给定两个元素数量均为n的集合A和B，AB各自拿出一个元素组成元素对，对于任意这样的元素对组合，都给定他们的损失（cost）。匈牙利算法能够基于这样的数据得到一个从A到B的一一映射，使得cost总和最小。

举个例子，三个工人A、B、C都能做任务1、任务2、任务3三件事情，但是不同人做不同事情的报酬不同，可以用一个矩阵表示

    1       2       3
A   108     125     150 
B   150     135     175 
C   122     148     250

现在的问题是，如何分配任务，使得总的报酬最小？

关键思想

匈牙利算法的关键思想是，对于一个cost矩阵，对任意一行或者一列加上或者减掉一个数值，最优分配不变。

如何理解这点呢？

举一个例子，在原问题中，我们假设最优解为（实际上也是）A3、B2、C1，用(*)来表示。

    1       2       3
A   108     125     150(*) 
B   150     135(*)  175 
C   122(*)  148     250

现在我们对第一行的每一个元素都减掉一个数，假设是10，那么可以得到

    1       2       3
A   98      115     140(*) 
B   150     135(*)  175 
C   122(*)  148     250

我们现在思考一个问题，对于第1列来说，它本来的选择是C，那么从C调整到A，那么总体的报酬会不会有可能增加呢？答案是不可能的，因为A行的所有元素都降低了10，所以即使第1列从C调整到A，获取了A行降低10的收益，但是第3列不用调整，也能获得相同的、因A行降低的收益。因为整体的cost函数是简单的求和，所以第A行的最优分配还是3，第1列的最优分配也没有理由从C调整到A。

算法步骤

有了上面的关键思想，我们可以描述具体的算法步骤，对于n阶分配问题。

Step 1：对于每一行中的每一个元素，减掉行中最小元素，结果一定至少有一个0
Step 2：对于每一列中的每一个元素，亦减掉其列上最小元素，结果同样至少有一个0。
Step 3：使用最少的横线+竖线，覆盖所有的0元素。
Step 4：如果横线+竖线的数量大于等于n，则找出分配，使得所有分配代价均为0；如果数量小于n，进行下一步。
Step 5：对于没有被覆盖的元素，标记最小元素，对于所有没覆盖的行，减掉最小元素，对于覆盖的列，加上该最小元素，然后重复Step 3。

然我们来对着本案例进行详解。

Step 1：对于每一行中的每一个元素，减掉行中最小元素，结果一定至少有一个0。结果为：

    1       2       3
A   0       17      42 
B   15      0       40 
C   0       26      128

Step 2：对于每一列中的每一个元素，亦减掉其列上最小元素，结果同样至少有一个0。结果为：

    1       2       3
A   0       17      2 
B   15      0       0 
C   0       26      88

Step 3：使用最少的横线+竖线，覆盖所有的0元素。结果是B行、1列被划线覆盖，数量为2。

    1       2       3
A   0       17      2
B   15      0       0   ------
C   0       26      88
    |
    |
    |

Step 4：如果横线+竖线的数量大于等于n，则找出分配，使得所有分配代价均为0；如果数量小于n，进行下一步。结果是划线数量小于3，进行下一步。

Step 5：对于没有被覆盖的元素，标记最小元素，对于所有没覆盖的行，减掉最小元素，对于覆盖的列，加上该最小元素，然后重复Step 3。

标记减掉未覆盖的最小元素，也就是A3的2。未覆盖的行减掉该最小元素2，得到

    1       2       3
A   -2      15      0   
B   15      0       0   ------
C   -2      24      86 
    |
    |
    |

已覆盖的列加上最小元素2，得到

    1       2       3
A   0      15       0  
B   17      0       0   ------ 
C   0      24       86
    |
    |
    |

重复第3步，得到A、B行以及第1列三条线，数量为3。

    1       2       3
A   0       15      0   ------
B   17      0       0   ------
C   0       24      86
    |       
    |       
    |       

重复步骤4，数量为3，则选择A3、B2以及C1为最优分配

    1       2       3
A   0       15      0*  ------
B   17      0*      0   ------
C   0*      24      86
    |       
    |       
    |       

对于MxN问题怎么办？

很简单，只要对维度小的行或列进行増广，增广成NxN或者MxM阶方阵即可，増广的元素内容全部填上极大值。

SciPy中的实现

在SciPy的实现中，匈牙利算法又被称为线性求和分配。

方法名称：scipy.optimize.linear_sum_assignment

调用语法：scipy.optimize.linear_sum_assignment(cost_matrix, maximize=False)

调用示例


>>> cost = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])
>>> from scipy.optimize import linear_sum_assignment
>>> row_ind, col_ind = linear_sum_assignment(cost)
>>> col_ind
>>> array([1, 0, 2])
>>> cost[row_ind, col_ind].sum()
>>> 5

参考：https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html