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

Question

我不太精通赋值问题，并试图找到 Munkres/the 匈牙利方法的替代方法，适用于赋值问题的变体，其中：

有些分配是不允许的
可能无法将每个 person/row 分配给一个 assignment/column（在这种情况下，我只想尽可能多地分配 - 也许通过查找和使用最大可解矩阵)

我已经能够修改 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, b)的解释是a是不允许分配的数量，b是允许分配的总成本。因此，每个成本 c 都映射到 (0, c)，每个不允许的分配都映射到 (1, 0).

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

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

Hungarian method with disallowed assignments and unsolvable matrices

python

algorithm

matrix

hungarian-algorithm