为了找到赋值问题的最佳解决方案，使用匈牙利算法很容易。例如：
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！有没有我不知道的有效方法？
我正在考虑一个搜索，首先对行进行排序，然后贪婪地选择最低成本，首先假设大多数最低成本将弥补最小金额+修剪。但是假设匈牙利算法可以生成一个有很多零的矩阵，复杂性又是可怕的......
你描述的是K最佳赋值问题的一个特例——事实上，Katta G. Murty在1968年的论文"一种算法"按成本增加顺序对所有赋值进行排名"中提出了这个问题的解决方案。运筹学 16(3(：682-687。
看起来实际上有相当数量的实现，至少在Java和Matlab中，可以在网络上找到(参见此处(。
在 r 中，现在在 muRty 包中实现了 Murty 算法。
克兰
GitHub
它涵盖：
- 最小和最大方向的优化;
- 按秩输出(类似于 SQL 中的密集秩(，以及
- 使用匈牙利算法(如
clue年实现(或线性规划(如lpSolve年实现(来解决初始任务。
免责声明：我是该软件包的作者。