针对非标准分配的Munkres算法问题

Question

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

在传统的分配问题中,需要将n个工作人员分配到n个工作,并且矩阵包含为每个工作分配每个工作人员的成本.

在这种变化中,我们只有m(m <n)个工人.由于Munkres算法需要相同数量的工人和工作,我们创建(n - m)"虚拟"工人,他们可以分配到备用工作.此外,作业本身也按大量离散类别进行组织.

我们想要施加约束,即每个类别中至少有一个作业被分配给真实(非虚拟)工作者.这很难做得很优雅:例如,您可以从每个类别中挑选一个随机工作,并以人为方式确定每个实际工作人员的相关成本,但这是一个非常粗略的解决方案,会严重损害最终任务的完整性.

我们目前所做的是多次运行算法,每次评估输出分配,然后修改成本矩阵,使得仅分配给虚拟工作者的任何类别中的所有作业的成本略有降低.这适用,但对于中等大的数据集(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 的链接，这意味着每个类别将获得至少一个工人（如果可能）。