Possibilités de diviser une classe en groupes avec plusieurs critères

Question

Je dois diviser une classe de 50 étudiants en rédigeant une dissertation dans 10 groupes de discussion différents de 5 membres chacun. En théorie, il y a 1,35363x10^37 façons possibles de faire cela, qui est juste le résultat de {50!}/{(5!^10) * 10!)}, S'il est déjà décidé que les groupes seront constitués de 5.

Cependant, chaque groupe doit être dirigé par un facilitateur. Cela réduit considérablement le nombre de combinaisons possibles, car chaque animateur dispose d'un domaine d'expertise parmi 5 possibles, qui doit correspondre autant que possible aux sujets abordés par les étudiants. S'il y a trois facilitateurs de compétence A, trois de compétence B, deux de compétence C, un de compétence D et un de compétence E, et 15 étudiants sont affectés à A, 15 à B, 10 à C, 5 à D et 5 À E, le nombre de combinaisons possibles descend à 252 505.

Mais les étudiants et les animateurs continuent à plaider pour l'utilisation de plus de critères, au lieu de se concentrer uniquement sur le domaine d'expertise. Par exemple, vouloir faire partie d'un groupe d'étudiants qui se connaissent, ou faire partie d'un groupe avec un facilitateur qui a une connaissance particulière d'une méthode de recherche spécifique. J'essaye d'illustrer mon raisonnement intuitif, qui me dit que chaque nouveau critère augmente la complexité/l'impossibilité de la tâche, si l'objectif est une solution complètement efficace. Mais je n'arrive pas à exprimer mon esprit de manière satisfaisante d'un point de vue analytique. Est-ce que mon raisonnement est correct, que l'ajout de critères réduirait la quantité de possibilités qui peuvent être rejetées selon le principe d'inclusion-exclusion, rendant ainsi la tâche plus complexe, en ajoutant des combinaisons possibles? Je pense aussi que si les critères ne sont pas compatibles (par exemple si des étudiants qui se connaissent écrivent sur des sujets différents, et qu'il n'y a pas assez de facilitateurs compétents), certaines contraintes deviennent inviables.

Answer 1

Vous devez faire la distinction entre complexité algorithmique et complexité humaine. L'ajout de contraintes augmente presque automatiquement la complexité humaine du problème, dans la mesure où cela signifie qu'il y a plus à faire pour envelopper votre esprit. Mais - il n'est pas vrai que la complexité de calcul augmente. Au moins, parfois, il diminue. Par exemple, disons que vous avez un ensemble de 200 éléments et que vous voulez déterminer s'il y a un sous-ensemble de ceux-ci qui satisfont certaines contraintes. Par exemple, disons que vous avez un ensemble de 200 éléments. Selon la contrainte, il n'y a peut-être pas de moyen possible de le faire. Après tout, 2^200 est beaucoup trop grand pour la force brute. Ajoutez maintenant la contrainte que le sous-ensemble doit avoir exactement 3 éléments. Maintenant, tout d'un coup, il est possible de forcer la force brute (il suffit de parcourir les 1.313.400 éléments à trois éléments jusqu'à ce que vous trouviez une solution ou déterminiez qu'il n'y en a pas). Cela suffit à montrer qu'il n'est pas vrai que l'ajout d'une contrainte rend toujours un problème intrinsèquement plus difficile. Dans le cas discret, une nouvelle contrainte peut réduire la taille de l'espace de recherche d'une manière qui peut être exploitée. Dans les cas continus, il peut réduire les degrés de liberté et ainsi réduire la dimension du problème. Cela ne veut pas dire que cela le rend toujours plus facile. Probablement, en règle générale, les contraintes supplémentaires tendent pour rendre un problème plus difficile.

Votre problème actuel n'est pas suffisamment expliqué pour donner des conseils concrets. Une possibilité (et une façon de gérer une prolifération de contraintes quelque peu étrangères) est de diviser les contraintes en contraintes dures qui doivent être satisfaites et en contraintes douces qui sont simplement souhaitées mais pas strictement nécessaires. Transformez-le en un problème d'optimisation: trouvez la solution qui maximise le nombre de contraintes souples qui sont satisfaites, à la condition qu'il satisfasse les contraintes dures. Peut-être que vous pouvez formuler comme un problème integer programming et espérons trouver une solution exacte.Ou, s'il est facile de générer des solutions qui satisfont les contraintes dures et qu'il est facile de muter une telle solution pour en obtenir une autre (par exemple échanger deux étudiants qui sont dans des groupes différents), alors une evolutionary algorithm serait une heuristique raisonnable.