我将以您问题中的这个矩阵为例:
2 7 1
0 0 10
8 2 0
首先,匈牙利算法找到最小值,而不是最大值,因此我们需要将所有值乘以 -1,这样当您运行算法并找到最小值时,它实际上是原始矩阵的最大值。
-2 -7 -1
-0 -0 -10
-8 -2 -0
匈牙利算法仅适用于非负数,虽然您使用的代码应该能够处理它们,但您可以通过减去矩阵中的最小数字(在这种情况下为 -10)自己摆脱它们从矩阵中的每个值。
8 3 9
10 10 0
2 8 10
现在我们在这个矩阵上运行匈牙利算法并得到算法找到的最小匹配的索引列表。我们想按 x 索引对该列表进行排序。
[(0,2), (1,0), (2,1)]
这个最小匹配也是我们原始矩阵的最大匹配。由于这种匹配是按 x 索引排序的,我们可以使用 y 索引作为原始矩阵的索引。也就是说,第一个索引对是(0,2)
,所以我们最终矩阵的第一行将是原始矩阵的第三行。
(0,2)
->
(1,0)
最终矩阵的第一行是原始矩阵的
(2,1)
第三行 -> 最终矩阵的第二行是原始矩阵的第一行 -> 最终矩阵的第三行是原始矩阵的第二行
8 2 0
2 7 1
0 0 10
这与您在问题中给出的排列不完全匹配,但它仍然是有效的排列。