原址:https://blog.csdn.net/siss0siss/article/details/51325656
资料写的不完善,本篇文章较详细友善。
匈牙利解法:
解释.png
总的来说,以下解法就是利用了上面的算法,得到一个可以在每一行找到独立的0系数。
过程
一、做减法(归约):
行归约:每行元素减去该行最小元素。
列归约:每行元素减去该行最小元素。
归约顺序无所谓,目的就是把所有的数尽可能化的很小,但最小的数不能为负数
图片.png
二、圈零划零
找到含零元素最少的行,对零元素打圈,划去打圈零元素所在行和列存在的零元素,重复这个步骤,直到矩阵中所有的零元素都被处理完。
图片.png
三、打勾划线
图片.png
图片.png
四、调整量的加减
图片.png
五、圈零画零,检查圈零元素数量
图片.png
如果仍然不是最优解,再重复上述步骤。