algorithm - 不同大小的代理和任务集之间的最佳匹配

Question

问题:

I have a set of agents A of size a, a set of tasks Tof size t and a profit function p(agent, task). Each agent can only be assigned one task and each task can only be handled by one agent.

I need to find a set of (agent, task) pairs for which the total profit is maximal.

我从一个天真的解决方案开始，该解决方案将递归地找到具有最高利润的(代理，任务)对。结果证明是次优的。然后我尝试了更大集合的所有排列——程序从未完成。 :)

我认为这是某种 assignment problem但到目前为止，我只找到了代理和任务数量相等的线性分配问题的解决方案。

你能指出一个解决这个问题的有效算法或建议一个解决这个问题的方法吗？

Answer 1

延迟很长时间，但您的解决方案终于来了!同时DasKrumelmonster是部分正确的，因为您正在尝试解决线性分配问题，您正在专门尝试解决二分图。

看看这个名为 Bipartite Solver 的 GitHub 存储库.它不仅为您提供了另一个答案中建议的 Jonker-Volgenant 算法的 java 实现，还有 4 种算法可供选择。

第一个是贪婪搜索，这正是您提到的您首先实现的 - 它迭代地找到最佳匹配。虽然它可能提供次优解决方案，但在大多数情况下它接近最优。它是同类产品中最快的。

第二个是暴力搜索。就像您提到的那样，该程序需要很长时间才能完成 9x9 映射，但对于小数字来说，这就足够了，而且是最佳的。

第三种是暴力破解的变体，但带有alpha-beta 树修剪。平均速度提高约 20%，但超过 13x13 时，内存就会耗尽。

第四个是LAPJV，它是最优的并且速度非常快。我的意思是 2000x2000 in 1s 很快!放下手，这就是您应该做的。

图书馆有一大堆 executables如果您希望在不从源代码构建算法的情况下试用这些算法。

这个图书馆看起来正是您所要求的，只是晚了一年。我猜，迟到总比不到好。