非标准分配

Question

的Munkres算法问题，我有一个平常的Munkres /匈牙利算法似乎没有能力解决分配问题的变化。

在传统的分配问题，有n个工人需要被分配到n个工件谁，以及包含每个工人分配给每个作业的成本矩阵。

在这种变化中，我们只有M（< n）的工人。由于Munkres算法需要相同数量的工人和工作，因此我们创建了可以分配到备用工作的（虚拟）“虚拟”工人。此外，这些工作本身是组织在大量离散的类别中。

我们想强加从每个类别至少1个任务被分配到一个真正的（非虚拟）工人的约束。这很难做到优雅：例如，您可以从每个类别中随机选择一个作业，并人工缩减每个实际工作人员的相关成本，但这是一个非常粗糙的解决方案，严重影响最终作业的完整性。

我们做什么目前运行的算法多次，每次评估输出的分配，并修改成本矩阵使得对所有工作在任何类别被分配的成本只有虚拟工人略有下降。这适用，但对于中等规模的数据集（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的链接第一，这意味着每个类别将得到的至少一个工人（如果可能）。