0

我对分配问题并不精通，并试图找到一种替代 Munkres/匈牙利方法的替代方法，该方法适用于分配问题的变体，其中：

  1. 某些作业是不允许的
  2. 可能无法将每个人/行分配给一个分配/列（在这种情况下，我只想进行尽可能多的分配 - 也许通过找到并使用最大的可解矩阵）

我已经能够修改 Munkres 实现来处理 #1，但它在以下情况下会崩溃：

[  D,   D,   1,   D,   D,   D,   D,   D]
[  D,   D,   D,   D,   1,   D,   D,   D]
[  1,   D,   D,   D,   D,   1,   1,   1]
[  D,   D,   D,   D,   D,   2,   2,   2]
[  D,   1,   D,   D,   D,   3,   3,   3]
[  D,   D,   1,   2,   3,   D,   D,   D]
[  D,   D,   1,   2,   3,   D,   D,   D]
[  D,   D,   1,   2,   3,   D,   D,   D]

# ("D" = disallowed)

最终无法通过：

[  D,  D,  0,  D,  D,  D,  D,  D]
[  D,  D,  D,  D,  0,  D,  D,  D]
[  0,  D,  D,  D,  D,  0,  0,  0]
[  D,  D,  D,  D,  D,  0,  0,  0]
[  D,  0,  D,  D,  D,  0,  0,  0]
[  D,  D,  0,  0,  2,  D,  D,  D]
[  D,  D,  0,  0,  2,  D,  D,  D]
[  D,  D,  0,  0,  2,  D,  D,  D]

我应该使用另一种算法来处理这个问题吗？或者在将其传递给算法之前使用某种算法方法来检测上述无法解决的情况（如果我每次都首先运行算法来检测这些情况会变得相当昂贵）？

作为参考，这是我正在使用的代码（在 Python 中）： https ://github.com/knyte/munkres/blob/master/munkres.py

4

1 回答 1

1

假设您要最小化最大分配次数的成本，请修改 Munkres 的算法以使用(a, b)具有以下算术和顺序规则的数字对：

(a, b) + (c, d) = (a + c, b + d)
-(a, b) = (-a, -b)
(a, b) < (c, d) if and only if a < c or (a = c and b < d).

使用(0, 0)而不是0.

成本的解释(a, b)是a不允许分配的数量，b是允许分配的总成本。因此，每个成本c都映射到(0, c)，每个不允许的分配都映射到(1, 0)。

当你从 Munkres 的算法中得到答案时，扔掉所有不允许的分配。

于 2017-02-18T14:34:55.150 回答