Ouais, il y a. Comme t'es en école d'ing' si je me rapelle bien, tu devrais avoir un cours sur ça à un moment ou un autre.

Il s'agit d'un problème de recherche opérationnelle (ou décision multicritère ou d'autres noms du même genre). Je crois que la solution est ce qu'on appelle l'algo hongrois.

J'ai eu de très mauvaises notes dans ces matières. Donc je peux t'aider, mais pas trop.

Recherche déjà sur google & co avec ces termes : algorithme hongrois, recherche opérationnelle, aide à la décision multicritère

Je surveille le post pour t'aider si je peux (j'ai ressorti mon cours).

Malheureusement mon école n'a pas prévu de me former à la recherche opérationnelle...

J'avais déjà commencé à me renseigner sur l'algorithme hongrois, mais je n'ai rien pu en tirer du fait de mon faible bagage mathématique :/

Je vais essayer de continuer ma recherche avec les mots-clef que tu viens de me proposer !

Merci de ton aide en tout cas :)

Y'avait un article sur zeste de savoir (ou un poste de forum)

https://zestedesavoir.com/forums/sujet/3998/devez-vous-quitter-votre-femme-pour-celle-du-voisin/

Ah, tu n'auras pas de cours dessus ? Pas terribl' d'un coup.

bon alors un peu d'aide (ce que je me souviens) :

Tu ranges les choix de projets des équipes par ordre (1: celui qu'on veut le plus, 2: un peu moins... jusqu'à la fin...).

Tu fais une matrice avec ça.

La suite c'est là : https://www.youtube.com/watch?v=mwsaZ18caaM

Si tu suis bien, chaque équipe se retrouvera avec le choix le plus bas possible pour elle. Il s'agit donc d'un problème de minimisation.

Ça demande de l'abstraction hein. Je reviens bientôt si t'as un soucis.

Merci à tous pour vos liens ! Je n'ai pas utilisé la méthode de Condorcet, ni l'algorithme de Gale-Shapley, mais ça me fera deux lectures intéressantes pour cette semaine :)

J'ai bien utilisé la méthode hongroise, qui s'avère simple à comprendre en fin de compte, avec un solveur en ligne !

Comme tu l'as dit Stéphane, pour chaque groupe d'élèves on associe un poids de 0 à n-1 en fonction de la liste de vœux qu'ils ont demandés.
Pour les projets qu'ils n'ont pas demandés, on associe un poids de n (le nombre de vœux dans leur liste).

Au final le résultat est plutôt propre : avec 32 projets à répartir entre 29 groupes, chacun à reçu en moyenne sont premier ou son deuxième vœux, et seule deux groupes n'ont pas pu être affectés à un projet. Pour ces deux cas particuliers, je vais devoir leur redemander une liste de vœux sur les projets restants.

Génial. Ce que tu décris correspond parfaitement à la description faite par le prof que j'avais.

Alors que si tu fais les choses sans méthode, ça peut très vite déraper.

J'ai pas compris comment ça fonctionne.

Ça veut dire que t'es un être humain à peu près normal !

J'ai mal expliqué aussi :P

En gros tu veux résoudre un problème où tu dois affecter une ressource A à une autre ressource B tout en faisant le meilleur couplage possible, c'est à dire en minimisant le coût total de toutes les combinaisons de A et B.

Si on prend exemple avec des enfants et des bonbons, le problème est le suivant : il y a 4 enfants (A, B, C, D) et 4 bonbons différents (Fraise, Pomme, Banane, Mûre) et on va chercher à donner un bonbon à chaque enfant tout en faisant en sorte que ce soit son bonbon préféré.

On va demander à chaque enfant de lister par ordre de préférence les 4 bonbons précédents.

Enfant A aime : [Fraise, Pomme, Banane, Mûre]
Enfant B aime : [Pomme, Fraise, Banane, Mûre]
Enfant C aime : [Fraise, Banane, Pomme, Mûre]
Enfant D aime : [Pomme, Fraise, Mûre, Banane]

On va donc pour chaque couple Enfant-Bonbon déterminer un coût en fonction de la préférence qu'il aura exprimé : 0 pour son 1er choix, 1 pour son 2ème, 2 pour son 3ème et 3 pour son 4ème. Ce qui donne la matrice suivante (tableau à 2 dimensions) :

Couples | Fraise | Pomme | Banane | Mûre |
......... A | 0 | 1 | 2 | 3 |
......... B | 1 | 0 | 2 | 3 |

......... C | 0 | 2 | 1 | 3 |

......... D | 1 | 0 | 3 | 2 |

L'algorithme hongrois va donc chercher à minimiser le coût total des couples Enfant-Bonbon, ce qui revient à dire dans ce cas précis que l'algorithme va nous permettre de maximiser le contentement des enfants !

Si tu inscrits cet matrice dans ce solveur (juste les chiffres), tu pourras voir toutes les étapes effectuées par l'algorithme ou arriver directement au résultat.

Dans le cas présent tu pourras voir que l'algorithme a sélectionné la meilleure combinaison possible :

Enfant A obtient Fraise
Enfant B obtient Pomme
Enfant C obtient Banane
Enfant D obtient Mûre

Si on fait la moyenne des valeurs cela donne :
coût moyen = (0 + 0 + 1 + 2) / 4 = 0.75
En moyenne les enfants ont donc obtenu le premier (0) ou leur deuxième choix (1) !

J'espère que c'est un peu plus clair :)

Et Giome vient d'apprendre (tout seul) et de résoudre (presque tout seul) un problème d'ingénierie (qu'il devrait avoir en cours mais qu'il aura pas en fait) !

Chapeau !

Cool merci :+) pratique.

Je vais rougir :3

Je me suis permis de copier/coller ton explication pour le mettre dans mon shaarli :-)