Le premier algorithme à avoir valu à ses créateurs un prix Nobel - formulé à l'origine par deux mathématiciens, David Gale et Lloyd Shapley, en 1962 (Marcus du Sautoy)
(FLP) - Peux-tu m'expliquer simplement l’algorithme de David Gale et Lloyd Shapley ?
(Reflexity-ai) - L'algorithme de Gale-Shapley, également connu sous le nom d'algorithme des mariages stables, vise à résoudre le problème d'appariement stable entre deux groupes de taille égale, comme des hommes et des femmes. Voici une explication simplifiée :
1. Chaque personne dans les deux groupes classe tous les membres de l'autre groupe par ordre de préférence.
2. Le processus commence avec tous les membres non appariés.
3. Chaque homme non apparié fait une proposition à la femme qu'il préfère le plus et qui ne l'a pas encore rejeté.
4. Si la femme est libre, elle accepte provisoirement la proposition.
5. Si la femme est déjà engagée, elle compare le nouveau prétendant à son partenaire actuel. Elle reste avec celui qu'elle préfère et rejette l'autre.
6. Le processus se répète jusqu'à ce que tous les hommes soient appariés.L'algorithme garantit que :
- Tous les participants seront appariés.
- Les appariements sont stables, c'est-à-dire qu'il n'existe pas de paire qui préférerait être ensemble plutôt qu'avec leurs partenaires actuels.
Cet algorithme a des applications bien au-delà des mariages, notamment dans l'attribution des étudiants aux universités, des médecins résidents aux hôpitaux, et dans d'autres systèmes d'appariement.
Auteur:
Info: 24 juin 2024
Commentaires: 0