0

经典的分配问题涉及将 N 个代理分配给 M 个工作，同时最小化每个工作所花费的时间。该问题在多项式时间内有一个解决方案，称为匈牙利算法，它以成本矩阵 C 作为输入并返回最佳分配列表。

就我而言，我遇到了同样的问题，但有一点不同。每个工作都需要分配给它的两个工作。选择代理的数量，使得 N 是偶数，以便使这成为可能。

我对分配问题相关的问题相当陌生，所以我不确定如何解决这个问题。

如何解决这个问题？

编辑：请注意，一个代理最多可以分配给一个任务，它不能分配给多个任务。可以假设 M(jobs) = 2N(agents)，否则会引入虚拟代理或任务。

4

1 回答 1

1

由于任务数量是工人的两倍，因此您需要将任务数量增加一倍。由于每个任务需要两个工作人员，因此您可以通过复制每个任务来使任务数量加倍（例如，任务 1 变为任务 1a 和任务 1b）。然后，您将拥有相同数量的工人和任务，并且在运行匈牙利算法之后，您可以通过查看每个任务的每个拆分分配给谁来找到您的工人对。

于 2017-08-22T01:00:01.790 回答