问使用匈牙利算法求解分配问题的第二最佳解

EN

为了在赋值问题中找到最优解，使用匈牙利算法很容易。例如：

A |  3  4  2
B |  8  9  1
C |  7  9  5

当对此使用匈牙利算法时，您将变成：

A |  0  0  1
B |  5  5  0
C |  0  1  0

这意味着A被分配给' job‘2，B分配给作业3，C分配给作业1。然而，我想找到第二个最好的解决方案，这意味着我想要一个成本比最优解的成本更高的最佳解决方案。根据我的观点，我只需要在最后一个矩阵中找到最小和的赋值，而不是和最优一样。我只需在树中搜索(通过修剪)就可以做到这一点，但我担心复杂性(是O(n!))。我不知道有什么有效的方法吗？

我正在考虑一种搜索，首先对行进行排序，然后贪婪地首先选择最低的成本，假设最低成本中的大部分将弥补最小和+剪枝。但是假设匈牙利算法能产生一个大量的零矩阵，那么它的复杂度又是非常糟糕的。