python - 具有不允许分配和不可解矩阵的匈牙利方法

Question

我不太精通分配问题，并试图找到一种替代 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

Answer 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 cost (a, b)的解释是，a是不允许赋值的次数，b是总成本允许的分配。因此，每个成本 c 都映射到 (0, c)，每个不允许的赋值都映射到 (1, 0)。

当您从 Munkres 的算法中得到答案时，丢弃所有不允许的赋值。