3

为了在分配问题中找到最佳解决方案，使用匈牙利算法很容易。例如：

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！））。有什么我不知道的有效方法吗？

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

4

2 回答 2

4

您所描述的是K 最佳分配问题的一个特例——实际上 Katta G. Murty 在以下 1968 年的论文“ An Algorithm for Ranking all the assignments in order of increasing Cost ”中提出了该问题的解决方案。运筹学 16（3）：682-687。

看起来实际上有相当数量的实现，至少在 Java 和 Matlab 中，可在网络上获得（参见例如此处。）

于 2013-12-02T17:34:49.653 回答
0

在包中现在有一个 Murty 算法的实现muRty。

克兰

GitHub

它涵盖：

  • 最小和最大方向的优化；
  • 按等级输出（类似于 SQL 中的密集等级），以及
  • 使用匈牙利算法（如在 中实现clue）或线性规划（如在 中实现lpSolve）来求解初始分配。

免责声明：我是包的作者。

于 2019-05-26T09:01:12.290 回答