匈牙利算法步骤
作用
解决指派问题。所谓的指派问题就比如：甲乙丙三个人去做ABC三件事情。每个人做每件事情所花的时间可能不一样。每个人只能安排一件事情，问怎样安排才能使三个人所工作的时间之和最小？ 扩展成 n 个人 n 件事也可以，但要求是：
事情数和人数一样多 每人只能做一件事 这样的问题就称作指派问题 匈牙利算法就是解决这样的问题的。
实例
甲乙丙中第i (i=1,2,3)个人做ABC中第j (j=1,2,3)件事的时间为 Aij。矩阵 A 如下
2 3 4
3 4 6
5 6 1
就是说甲做A事情要2分钟，做B事情要3分钟； 乙做C事情要6分钟，以此类推。问怎样安排才能使甲乙丙三人所用的时间最少？ 下面用匈牙利算法来解。
算法目标
让矩阵中出现 n 个满足不同行不同列的 0。 上述问题就是要3个不同行不同列的0.
步骤概括
- 每行减去此行最小数
- 判断是否达到算法目标,如未达到算法目标,继续下一步,否则结束.
- 横纵交替,从行开始.找出所有还没有选中0的行,在此行后面打钩;把此行中有0的列全打钩.在打钩的列中,如果有零,又在有0的行打钩,如此交替,直到不能再打钩.
- 在没有打钩的行和打钩的列上划线,会得到发现所有的0已经被划去,如果没有划去,请检查前面的步骤.此时剩下的所有元素中,找到最小值,就记为min.
- 在第四步未画线的行减去min(此时原来的0变成-min),再在画线的列加上min(此时矩阵中没有了负数).回到第二步.
步骤实例
# 0)初始矩阵
2 3 4
3 4 6
5 6 1
# 1)每行减去此行最小值
0 1 2
0 1 3
4 5 0
# 2)检查发现没有达到算法目标
只有两个不同行不同列的0 ,没有达到算法目标
# 3)找出没有选中0的行,在后面打钩
此行的0在第一列,在第一列画勾;发现第一列有两个0,其中第一行的0还没画勾;于是第一行后画勾.
0 1 2 √
0 1 3 √
4 5 0
√
# 4)在没有打钩的行,即第三行,和打钩的列,即第一列,划线.会得到发现所有的0已经被划到.然后找到最小值min,此处min=1
|0| 1 2
|0| 1 3 min=1
+-+--------
|4| 5 0
-----------
# 5)在第四步未画线的行减去min,再在画线的列上加min,最后得到
0 0 1
0 0 2
5 5 0
结果可以是
O 0 1 0 O 1
0 O 2 也可以是 O 0 2
5 5 0 5 5 0
也就是甲2乙1丙3或者甲1乙2丙3:
带入初始矩阵:
2 3 4
3 4 6
5 6 1
3+3+1 或 2+4+1
最小代价都是7
例子和思路
四个工作（W1，W2，W3和W4）需要执行四个作业（J1，J2，J3和J4）
82 83 69 92
77 37 49 92
11 69 5 86
8 9 98 23
# 1)减去行最小值
我们首先从每行中减去行最小值。例如，第一行中的最小元素是69.因此，我们从第一行中的每个元素中减去69。得到的矩阵是：
12 14 0 23
40 0 12 55
6 64 0 81
0 1 90 15
# 2)减去列最小值
同样，我们从每列中减去列最小值，给出以下矩阵：
13 14 0 8
40 0 12 40
6 64 0 66
0 1 90 0
# 3)用最少的行数覆盖全零
我们现在将确定覆盖矩阵中所有零所需的最小行/列数（水平或垂直）。可以使用2行+1列（第二行，第四行，第三列）覆盖所有零：
13 14 0 8
40 0 12 40 X
6 64 0 66 X
0 1 90 0
X
因为所需的行数（3）低于矩阵的大小（n = 4），所以继续步骤4.
# 4)创建其他零
首先，我们发现最小的未覆盖数是6.我们从所有未覆盖的元素中减去这个数字，并将其添加到所有被覆盖两次的元素中。这导致以下矩阵：
7 8 0 2
40 0 18 40
0 58 0 60
0 1 96 0
获得方法可参见上部:
1. 横减
2. 竖加
7 8 0 2
40 0 18 40
0 58 0 60
0 1 96 0
最佳匹配 [3,2,1,4]
69+37+11+23 = 140
代价最小