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

Question

为了找到分配问题的最佳解决方案，可以轻松使用匈牙利算法。例如：

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 被分配到“作业”2，B 被分配到作业 3，C 被分配到作业 1。但是，我想找到第二个最佳解决方案，这意味着我想要最佳解决方案，其成本严格大于最佳解决方案的成本。根据我的说法，我只需要找到最后一个矩阵中总和最小的分配，而不需要与最优分配相同。我可以通过在树中搜索（通过修剪）来做到这一点，但我担心复杂性（O(n!)）。有什么我不知道的有效方法吗？

我正在考虑一种搜索，其中我首先对行进行排序，然后首先贪婪地选择最低成本，假设大部分最低成本将弥补最小总和+修剪。但是假设匈牙利算法可以产生一个带有大量零的矩阵，那么复杂性又是可怕的......

Answer 1

您所描述的是K 最佳分配问题的一个特例- 事实上，Katta G. Murty 在下面的 1968 年论文“按递增成本顺序排列所有分配的算法”中提出了该问题的解决方案。运筹学 16(3)：682-687。

看起来实际上有相当数量的实现，至少在 Java 和 Matlab 中，可以在网络上找到（参见例如这里。）