匈牙利匹配原理和实现
匈牙利匹配概述
分配问题是组合优化领域中的一个基本问题，其目标是确定最佳分配，如使总成本最小化或使团队效率最大化。匈牙利匹配是求解二分图最大匹配的经典算法，算法的核心是根据一个初始匹配不停的找增广路径，直到没有增广路径为止。
二分图
图中所有顶点可以划分两个子集，任取一条边，边的两个顶点不在同一个子集中。
最大匹配
一个图的所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。最大匹配数，就是最大匹配时边的数目。
交替路径
给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径。
增广路径
从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路径称为增广路径。
增广路径的特点：路径长度为奇数（因为起点和终点必须分属两个集合）
匈牙利匹配原理
通过寻找增广路径，把增广路径中的匹配边和非匹配边的相互交换，这样就会多出一条匹配边，直到找不到增广路径为止。
匈牙利匹配实现
实现思路
步骤1：减去行最小值
找到邻接矩阵中每一行的最小元素，并且将每一行中的元素都减去该行中的最小元素。
步骤2：减去列最小值
在剩下的矩阵中找到每一列的最小元素，并且将每一列中的元素都减去该列中的最小元素。
步骤3：用最少的横线/竖线覆盖所有零
使用最少数量的水平和垂直线覆盖结果矩阵中的所有零。如果需要n行，则零之间存在最佳分配。执行步骤5。
如果少于n行，继续执行步骤4。
步骤4：生成额外的零
在没有被覆盖的元素中找到最小值，并且将没有被覆盖的元素减去这个最小值，同时将不同线条交叉位置上的元素加上这个最小值。回到步骤3。
步骤5：得到结果
最后从剩余的矩阵元素中找到最合适的零元素作为匹配结果。这里每个零元素对应筛选后的两个节点之间的边。
Python实现
scipy提供了linear_sum_assignment函数可以直接调用求解匈牙利匹配问题。
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)参考
这里有一个比较清楚的图示讲解：https://zhuanlan.zhihu.com/p/459758723
