algorithm - 非标准分配的 Munkres 算法问题

Question

我有一个分配问题的变体，通常的 Munkres/Hungarian 算法似乎无法解决。

在传统的分配问题中，有 n 个 worker 需要分配到 n 个工作，并且有一个矩阵包含将每个 worker 分配到每个工作的成本。

在这个变体中，我们只有 m (m < n) 个 worker 。由于 Munkres 算法需要相同数量的 worker 和工作，我们创建了 (n - m) 个可以分配给备用工作的“虚拟” worker 。此外，工作本身被组织成大量离散的类别。

我们想施加一个约束，即每个类别中至少有 1 个工作被分配给一个真实的(非虚拟的) worker 。这很难优雅地做到:例如，您可以从每个类别中随机选择一个工作，并人为地减少每个实际工作人员的相关成本，但这是一个非常粗略的解决方案，会严重损害最终分配的完整性。

我们目前所做的是多次运行该算法，每次都评估输出分配，然后修改成本矩阵，以便略微降低仅分配虚拟 worker 的任何类别中所有工作的成本。这已经足够了，但是对于中等大的数据集(n ~= 500)，这个过程可能需要一段时间(每个 Munkres 分配可能需要 10 秒来计算，并且有足够的类别可以有一个非平凡的迭代次数)。

是否有改进的 Munkres 算法或完全不同的算法可以更有效地解决这个问题？

Answer 1

类别是否不相交？每个工作只有一个类别？那么，最小成本流呢？

节点类型:

SRC - source
SNK - sink
C - a node or each category
J - a node for each job
W - a node for each worker

连接:

1) from SRC to C, capacity 1, cost 0
2) from SRC to C, capacity infinite, cost a high number
3) from C to J, capacity 1, cost 0
4) from J to W, capcity 1, the cost of job J done by worker W
5) from W to SNK, cost 0, capacity 1

然后算法将首先填充类型 1 的链接，这意味着每个类别将获得至少一个 worker (如果可能)。