“团队”的最大数量 [英] Maximum Number Of "Teams"

问题描述

我对团队成员有一个定义。考虑到一旦一个人被用来占用一个人，就无法再使用它们。我需要根据一列人（及其适用的位置）找到我能得到的最多的团队。

I have a definition for a team of people. I need to find the largest number of teams that I can get based on a list of people (and their applicable slots) given that once a person is "used" for a slot, they cannot be used again.

简化示例：

**Team Requirements**
Slot A: 2 People
Slot B: 1 Person
Slot C: 1 Person

**People And Which Slots Are Applicable**
Person 1: A
Person 2: A,C
Person 3: A,B
Person 4: B
Person 5: A,B
Person 6: C
Person 7: C
Person 8: A

可能的答案

Team 1
A: P1, P8
B: P4
C: P6

Team 2
A: P2, P3
B: P5
C: P7

我的现实问题是，我有多个位置（每个团队1-10个），并且1-1000人每个位置最多可以有20个位置。

For my real-world problem, I have multiple slots (1-10 per team) and 1-1000 people that can have up to 20 slots each.

有人可以推荐一个这类分组优化问题的最佳算法？

Can anyone recommend an algorithm that fits this type of group optimization problem?

推荐答案

这可以通过找到最大基数双向匹配在一系列图形中的每个图形中，总时间为O（n ^ 2.5 log n）。

This can be solved by finding a Maximum Cardinality Bipartite Matching in each of a series of graphs, in O(n^2.5 log n) time overall.

为此，请首先转换每个插槽 type 到一组适当数量的不同位置，以便我们最终获得位置A1，A2，B，C。最后的解决方案是将一个人分配到特定团队中的特定位置（例如第3人在第1队的A2位置），但是我们可以简单地忘记 2（以及各队的排序，这同样是纯人工的）。

To do this, first convert each slot type to a set of the appropriate number of distinct slots, so that we wind up with slots A1, A2, B, C. The final solution will assign a person to a specific slot in a specific team (e.g. Person 3 to slot A2 in Team 1), but we can simply forget the "2" (and also the ordering of the teams, which is likewise purely artificial).

从计算团队数量的乐观估计值开始：RoundDown（n / 4）会这样做，因为每个团队使用4个人，所以我们不能拥有比这更多的团队。现在在二部图的一个部分中制作4k顶点-即，在k个潜在团队中的每个4个插槽中的每个顶点：A1_1，A2_1，B_1，C_1，A1_2，A2_2，B_2，C_2等。 。，A1_k，A2_k，B_k，C_k。在二部图的另一部分中，为每个人创建一个顶点。最后，将每个人顶点与允许其填充的所有插槽顶点连接起来：如果某人x可以占用插槽A或C，则应通过一条边将其连接到以 A或 C开头的每个插槽（例如，如果有8个人，则为6个边缘）。

Start by calculating an optimistic estimate k of the number of teams: RoundDown(n/4) will do, since each team uses 4 people, so we can't have more teams than this. Now make 4k vertices in one part of the bipartite graph -- that is, a vertex for each of the 4 slots in each of the k potential teams: A1_1, A2_1, B_1, C_1, A1_2, A2_2, B_2, C_2, ..., A1_k, A2_k, B_k, C_k. In the other part of the bipartite graph, make a vertex for each person. Finally, connect up each person-vertex with all the slot-vertices that they are permitted to fill: So e.g. if a person x can occupy slots A or C, they should be connected by an edge to every slot that begins with "A" or "C" (which would be 6 edges for the example with 8 people).

然后，解决该图中的MCBM问题，例如通过使用 Hopcroft-Karp算法，在O（n ^ 2.5）时间内。结果将是边缘的子集，这些边缘可以解释为将每个人分配到一个团队中最多一个位置，并用一个人最多填充一个团队中的每个位置。如果这导致每个插槽都被占用，万岁！我们有最多的团队。否则，如果任何人都无法填补一些队伍空缺，请减少队伍数量，然后重试。 （您可以每次将团队数量减少1个，这导致需要解决的线性MCBM问题数量-但您可以通过二分查找来节省时间。这意味着首先将团队数量减半，然后此后，将团队数量减少或增加以前数量的一半，当某个团队的职位空缺时减少团队数量，如果没有空缺则增加团队数量，直到收敛。）

Then, solve the MCBM problem on this graph, e.g. in O(n^2.5) time by using the Hopcroft-Karp algorithm. The result will be a subset of the edges that can be interpreted as assigning each person to at most one slot in a team, and filling each slot in a team with at most one person. If this results in every slot being filled, hooray! We have a largest-possible number of teams. Otherwise, if there are some team slots left unfilled by any person, reduce the number of teams and try again. (You can reduce the number of teams by 1 each time, which results in a linear number of MCBM problems that need to be solved -- but you can save time by binary-searching. That means starting by halving the number of teams, and thereafter reducing or increasing the number of teams by half the previous amount, reducing when some team has an unfilled position and increasing when none do, until convergence.)

这篇关于“团队”的最大数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！