Bonjour,
Je suis en MP et dans le cadre de cette 2ème année de prépa, je dois réaliser un TIPE. Le sujet que j'ai choisi est le suivant :
"Comment obtenir le meilleur plan de classe ?"
Plus précisément, supposons que l'ont ait une classe de n élèves, qui ont tous de plus ou moins bonnes affinités entre eux (par exemple, deux élèves qui sont amis auront une bonne affinité, disons, pour le chiffrer, qu'elle sera de 16/20=0.8, alors que deux élèves qui se détestent auront une affinité de 3/20=0.015). La question est de savoir comment répartir les élèves sur les tables, de telle manière que les élèves soient le plus contents possible de ce plan de classe ?
Pour évaluer un plan de classe, je lui associe un coût U(Plan de classe), qui correspond à la somme des affinités entre les élèves divisées par la distance au carré.
Le but serait alors de trouver le plan de classe P qui maximise U(P).
J'ai choisi U(P) de manière arbitraire, en souhaitant qu'elle vérifie une propriété : quand deux élèves qui s'aiment se rapprochent, U(P) augmente, quand deux élèves qui se détestent s'éloignent, U(P) augmente (car du coup deux élèves qui ne se détestent pas seront plus proches, donc globalement U(P) va augmenter).
Une autre approche pourrait être de non pas chercher un maximum de U(P), mais plutôt chercher un plan de classe "stable", c'est-à-dire un plan de classe où deux élèves quelconques préferont toujours rester à la place qui leur est assignée plutôt que d'échanger. (Je me demande d'ailleurs si ce n'est pas en fait un maximum local de U(P)...)
L'intérêt du problème réside dans le fait qu'en pratique, si l'on a n élèves à placer, cela représente n! plans de classe possibles, et tous les tester (même informatiquement) devient pratiquement impossible quand on dépasse n = 25. Il faut donc trouver une méthode plus rapide (même en O(exp(n)), ça serait génial lol), ou à défaut trouver une méthode approchée.
J'en suis au début de mes recherches, et j'essaie de faire l'état de l'art sur ce sujet. Le problème, c'est que je ne sais pas où chercher, et surtout, quoi chercher !
Est-ce que vous sauriez où je pourrais orienter mes recherches ?
A ce stade de la réflexion, je me permets des hypothèses techniques, telles que par exemple supposer que si A aime B avec une affinité de 0.8 (soit Aff(A,B) = 0.8 = 16/20), B aimera aussi A avec une affinité de 0.8 (donc Aff(A,B) = Aff(B,A)). (Ce qui n'est pas forcément le cas dans la réalité, une personne peut en aimer une autre sans que cela ne soit réciproque).
Je sais aussi, après discussion avec mon prof d'informatique théorique, que la programmation dynamique ne semble pas adaptée au problème (à première vue en tout cas). En effet, rien ne dit que si un plan de classe P1 de taille n est maximisé, alors la meilleure façon de maximiser un plan de classe P2 de taille n+1 dépende de celle de maximiser P1.
Enfin, la dernière idée que j'ai eue, ça serait de m'inspirer de l'algorithme d'Irving (https://fr.wikipedia.org/wiki/Probl%...s_colocataires) couplé à un peu de force brute : l'idée serait de faire dans un premier temps des paires d'élèves, puis des paires de paires d'élèves, etc.
Voilà, donc si vous avez des idées qui pourraient m'aider à avancer, je suis preneur !
PS : j'ai cru comprendre que le forum dédié au TIPE est clos, donc je suis venu ici.
-----