问题：

我有一组代理尺寸 A A ，一组任务牛逼尺寸 T   实现利润函数 P（代理，任务）。每个代理也只能是   分配一个任务，每个任务只能由一个代理来处理。

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.

我已经开始了一个天真的解决方案，这将递归找到（代理，任务）对最高的利润。结果竟然是不理想的。然后，我尝试了大集合的所有排列 - 从来没有完成计划。 ：）

I've started out with a naive solution that would recursively find the (agent, task) pair with the highest profit. The result turned out to be suboptimal. I then tried all permutations of the larger set - the program never finished. :)

我觉得这是某种形式的分配问题但我至今只找到解决方案对于线性分配问题，其中的代理和任务的数目是相等的。

I think this is some kind of assignment problem but I've so far only found solutions for linear assignment problems where the number of agents and tasks is equal.

您可以点我一个高效的算法对于这个问题或建议针对此问题的方法？

Can you point me to an efficient algorithm for this problem or suggest an approach for this problem?

推荐答案

许多推迟，但您的解决方案终于来了！虽然 DasKrumelmonster 是部分正确的，你正在试图解决的线性分配问题，你是特别是试图解决一个二分图

Much delayed, but your solution is finally here! While DasKrumelmonster is partially right in that you are trying to solve the linear assignment problem, you are specifically attempting to solve a bipartite graph.

看看这个GitHub的库恰当地命名为二分求解。它不仅提供了一个Java实现的琼克-Volgenant 算法在对方的回答表明，有4算法选择。

Take a look at this GitHub repository aptly named Bipartite Solver. It not only provides you with a java implementation of the Jonker-Volgenant algorithm suggested in the other answer, there are 4 algorithms to choose from.

首先是贪婪搜索，这是你提到的正是你第一次实现 - 它反复地找到最佳匹配。虽然它可能提供一种次优解，大部分的时间，它是接近优化。这是最快的一群。

The first is greedy search, which is exactly what you mentioned you first implemented - it iteratively finds the best match. While it may provide a sub-optimal solution, the majority of the time it is near-optimal. It is the fastest of the bunch.

二是蛮力搜索。就像你所提到的，该方案需要一个loooong时间做任何多于一个9x9的映射，但对于小的数字，这是足够的，和最优

The second is brute force search. Just like you mentioned, the program takes a loooong time to do any more than a 9x9 mapping, but for small numbers, this is sufficient, and optimal.

三是蛮力的变体，但与α-β树修剪。你得到的平均约20％的速度递增，但任何超过13x13，您运行内存不足。

The third is a variant of brute force, but with alpha-beta tree-pruning. You get a ~20% speed increase on average, but anything more than 13x13, you run out of memory.

第四是 LAPJV ，这是最佳的，快疯了。我的意思是在1秒的 2000×2000 快！这就是你应该走了，倒手。

The fourth is LAPJV, which is optimal and crazy fast. I mean 2000x2000 in 1s fast! This is what you should go with, hands down.

图书馆有一大堆的可执行的，如果你想试用算法，而不从源代码进行编译。

The library has a whole bunch of executables if you wish to try out the algorithms without building it from source.

该库看起来正是你所要求的，只用了一年为时已晚。迟到总比不到好，我猜。

This library looks like exactly what you were asking for, only a year too late. Better late than never, I guess.