修改分配问题（任务多于代理）

Question

假设 N 是代理的数量，M 是任务的数量。任务数量大于智能体数量，即M>N。每个智能体必须至少有一个任务。给定成本矩形矩阵，找到最佳解决方案（即，将每项任务恰好分配给一个代理，以便每个代理至少有一项任务，并且成本最小化）。

有什么有效的算法可以解决这个问题呢？

我尝试过通过记忆实现朴素的递归算法，但是对于超过 1000 的 M 值来说太慢了。我了解匈牙利方法，但我无法在我的约束下使用该算法（每个代理必须至少有一项任务）。

Answer 1

这可以表述为最小成本最大流问题。

从水槽开始。它沿着成本 0 和流 1 的通道连接到任务。每个任务沿着矩阵和流 1 的成本通道连接到代理。每个代理通过流 1 和成本 0 的通道连接到接收器。代理还连接到水池有流量通道M-N，成本高。而且水池与水槽相连有水流通道M-N，成本同样较高。

M以最小的成本获得最大的流量，即从源到任务的流量。M然后它将具有从源头到代理的流程。一股流N将廉价而狭窄的管道直接从代理商处带到水槽。其余的M-N将走昂贵的路线到游泳池，并从游泳池到水槽。由于从代理到池并再次返回的流量非常昂贵，因此只有最少的流到池，并且没有从池返回到代理的流量。

因此，最大流量将是您问题的答案，每个代理至少从一项任务中获取流量。