Algorithme pour faire correspondre les partenaires préférés en groupes de trois
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Qu'est-ce qu'un bon algorithme pour résoudre ce problème?
J'ai trois groupes de personnes: le groupe A, le groupe B et le groupe C. Il y a le même nombre de personnes dans chaque groupe. Ils ont chacun une liste de personnes dans les autres groupes avec lesquels ils sont disposés à travailler. Je souhaite regrouper toutes ces personnes en groupes de 3 (un de A, un de B et un de C), de manière à ce que tous les membres d'un groupe veuillent travailler avec les autres membres de leur groupe.
Comment puis-je trouver ces groupes rapidement? S'il n'y a aucun moyen de contenter tout le monde, alors l'algorithme devrait d'abord faire en sorte que plusieurs groupes aient trois personnes qui souhaitent travailler ensemble, puis pour que autant de personnes dans les autres groupes soient heureuses.
Un dernier point: les gens s’entendent sur les personnes avec lesquelles ils veulent travailler (si la personne x veut travailler avec la personne y, alors y veut également travailler avec x). Si vous pouviez aussi donner un gros-O du temps d'exécution de votre algorithme, ce serait génial!
La solution
Cela ressemble au problème du mariage stable, mais avec trois parties au lieu de deux.
Découvrez des solutions efficaces au problème précédent (correspondance de graphes bipartites) et adaptez-les à vos besoins.
http://fr.wikipedia.org/wiki/Stable_marriage_problem
Une adaptation pourrait être de commencer par construire des paires de travail des groupes A et B uniquement. Ensuite, ces paires doivent être jumelées à un travailleur du groupe C chacune. Laissons les couples préférer les travailleurs sur lesquels les deux membres du couple sont d’accord (compte tenu de leurs listes). Notez que cela ne donnera qu’un optimum local.
Une solution optimale pour la correspondance k-partite est NP-difficile à trouver:
http://www.math.tau.ac .il / ~ safra / PapersAndTalks / k-DM.ps
Voir ce document pour une solution non optimale au problème de k-partite matching:
Je suis sûr que vous pouvez trouver d'autres personnes sur Google vous-même, maintenant que vous connaissez les termes à rechercher. Je ne sais pas s’il existe un algorithme efficace donnant la solution optimale pour k = 3.
Autres conseils
Cela diffère d'une extension du problème du mariage stable, car si je comprends bien la question du PO, les membres de chaque groupe ne disposent pas d'une liste ordonnée des personnes avec lesquelles ils souhaitent travailler, du plus au moins; c'est une relation binaire (vouloir / ne pas vouloir).
Ceci peut être formulé comme un problème de programmation d’entier qui peut être résolu assez rapidement. Je donne la formulation mathématique du problème ci-dessous; vous pouvez utiliser un paquet tel que glpk ou AMPL / CPLEX pour traiter les données.
Définissez les matrices suivantes:
M1 = |A| x |B| matrice, où
M1(a,b) = 1 si un (membre donné de A) est disposé à travailler avec b (membre donné de B) et 0 sinon
M2 = |A| x |C| matrice, où M2(a,c) = 1 si un (membre donné de A) souhaite travailler avec c (membre donné de C) et 0 sinon
M2 = |B| x |C| matrice, où
M3(b,c) = 1 si b (membre donné de B) accepte de travailler avec c (membre donné de C) et 0 sinon
Définissez maintenant une nouvelle matrice que nous utiliserons pour notre maximisation:
X = |A| x |B| x |C| matrice, où
X(a,b,c) = 1 si nous faisons travailler ensemble a, b et c.
Définissez maintenant notre fonction objectif:
// Maximiser le nombre de groupes
maximiser Sum[(all a, all b, all c) X(a,b,c)]
sous réserve des contraintes suivantes:
// Pour que personne ne soit placé dans deux groupes
Pour toutes les valeurs de a: Sum[(all j, k) X(a, j, k)] <= 1
Pour toutes les valeurs de b: Sum[(all i, k) X(i, b, k)] <= 1
Pour toutes les valeurs de c: Sum[(all i, j) X(i, j, c)] <= 1
// Pour que tous les groupes soient composés d'individus compatibles
Pour tous a, b, c: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
Juste une note rapide à ce problème. Premièrement, ce n’est pas un exemple du problème du mariage stable, ni en fait une extension de celui-ci (c’est-à-dire le problème de correspondance 3D stable). Quoi qu’il en soit, il s’agit d’un problème d’appariement 3D qui est connu pour être NP-difficile (voir Garey et Johnson). Pour résoudre un tel problème de manière raisonnable, il est probable que vous devrez utiliser une forme de programmation contrainte, un nombre entier ou linéaire (d'autres méthodes existent). La nouvelle solution Microsoft Solver Foundation est peut-être utile. Vérifiez-la.
Pour commencer, vous pouvez éliminer tous les faits pour lesquels les deux parties disposent de listes disjointes des personnes avec lesquelles travailler dans le troisième groupe. Commencez ensuite une recherche en force brute et en profondeur, en choisissant toujours de plus en plus populaire.
Sinon, comme pour l’élimination ci-dessus, créez une liste de tous les trios possibles et travaillez à partir de cela.
J'ai rencontré un problème similaire et je viens juste d'écrire un script qui le force brutalement ... http: // grouper. owoga.com/
Mes pensées initiales étaient les suivantes: pour un groupe plus important trop important pour la force brute, un type d’algorithme génétique? Faire N échanges aléatoires M fois. Marquez chaque nouvel arrangement par une fonction de «bonheur». Prenez les meilleurs, reproduisez, répétez.
Pour les petits groupes, j’ai obtenu de meilleurs résultats en bouclant plusieurs groupes, en trouvant le "meilleur" échange (celui qui a généré le gain de bonheur le plus élevé au monde), ce qui a permis de répéter, puis de répéter.
