Nombre maximum d '"équipes"

Question

J'ai une définition pour une équipe de personnes. J'ai besoin de trouver le plus grand nombre d'équipes possible en fonction d'une liste de personnes (et de leurs emplacements applicables) étant donné qu'une fois qu'une personne est "utilisée" pour une machine à sous, elle ne peut plus être utilisée.

Exemple simplifié:

**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 

Réponse possible

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

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

Pour mon problème dans le monde réel, j'ai plusieurs emplacements (1-10 par équipe) et 1-1000 personnes qui peuvent avoir jusqu'à à 20 emplacements chacun.

Quelqu'un peut-il recommander un algorithme qui correspond à ce type de problème d'optimisation de groupe?

Answer 1

Cela peut être résolu en recherchant un Maximum Cardinality Bipartite Matching dans chacune des séries de graphiques, en général O (n^2,5 log n). Pour cela, commencez par convertir chaque emplacement du type en un ensemble du nombre approprié d'emplacements distincts, de sorte que nous obtenions les emplacements A1, A2, B, C. La solution finale affectera une personne à un Fente spécifique dans une équipe spécifique (ex: Personne 3 à l'emplacement A2 dans l'Equipe 1), mais nous pouvons simplement oublier le "2" (et aussi l'ordre des équipes, qui est également purement artificiel). Commencez par calculer une estimation optimiste k du nombre d'équipes: RoundDown (n/4) fera, puisque chaque équipe utilise 4 personnes, donc nous ne pouvons pas avoir plus d'équipes que cela. Faites maintenant 4k sommets dans une partie du graphe bipartite - c'est-à-dire un sommet pour chacun des 4 emplacements dans chacune des k équipes potentielles: A1_1, A2_1, B_1, C_1, A1_2, A2_2, B_2, C_2, .. ., A1_k, A2_k, B_k, C_k. Dans l'autre partie du graphique bipartite, faites un sommet pour chaque personne. Enfin, connectez chaque sommet de personne à tous les sommets de fentes qu'ils sont autorisés à remplir: Donc, par exemple. Si une personne x peut occuper les slots A ou C, ils doivent être connectés par un bord à chaque slot qui commence par "A" ou "C" (ce qui aurait 6 bords pour l'exemple avec 8 personnes).

Ensuite, résolvez le problème MCBM sur ce graphique, par ex. en O (n^2.5) heure en utilisant le Hopcroft-Karp algorithm. Le résultat sera un sous-ensemble des bords qui peuvent être interprétés comme assignant à chaque personne au plus un emplacement dans une équipe, et remplissant chaque emplacement dans une équipe avec au plus une personne. Si cela se traduit par le remplissage de chaque slot, hourra! Nous avons le plus grand nombre possible d'équipes. Sinon, s'il reste des places d'équipe non remplies, réduisez le nombre d'équipes et réessayez. (Vous pouvez réduire le nombre d'équipes de 1 à chaque fois, ce qui entraîne un nombre linéaire de problèmes MCBM à résoudre, mais vous pouvez gagner du temps en effectuant une recherche binaire, ce qui signifie commencer par réduire de moitié le nombre d'équipes. par la suite, réduire ou augmenter le nombre d'équipes de la moitié du montant précédent, en réduisant quand une équipe a une position non comblée et augmenter en l'absence de convergence.)