匈牙利算法的原理是啥?

Question

我从最大流问题看到二部图，从二部图有权最大匹配问题看到匈牙利算法，觉得匈牙利算法好神奇，好奇它的原理，有没有友友知道这个算法原理，或者知道哪里有资源的？比如课程视频啥的，能不能分享一下，感谢!

Answer 1

该算法的基本原理是通过在二部图中寻找最大匹配，将原问题转化为另一图的最大匹配问题，然后采用匈牙利算法求解。具体来说，该算法可以分为以下几个步骤：
1、对指派问题的系数矩阵进行变换，使每行每列至少有一个元素为“0”。可以通过让系数矩阵的每行元素去减去该行的最小元素，再让系数矩阵的每列元素减去该列的最小元素来实现。
2、从第一行开始，若该行只有一个零元素，就对这个零元素加括号，对加括号的零元素所在的列画一条线覆盖该列，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。
3、从第一列开始，若该列只有一个零元素，就对这个零元素加括号（同样不考虑已划去的零元素），再对加括号的零元素所在行画一条直线覆盖该列，若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。
4、矩阵中所有零元素或被划去，或加上括号。但加括号的零元素少于m，这时转入第五步。
5、按定理进行如下变换：从矩阵未被直线覆盖的数字中找出一个最小的k；当矩阵中的第i行有直线覆盖时 ，无直线覆盖时；第j列有直线覆盖时 ，无直线覆盖时 。