Algorithmes de couplages parfaits et de mariages stables
Introduction
On a tous déjà connu ce moment où l’on rencontre un autre groupe. Pour favoriser les intéractions, on décide de faire des paires. Mais chacun a ses affinités, certains ne veulent pas être avec certains autres, ou ont des préférences de manière générale. Il faut donc former les paires de la manière la plus juste possible. C’est à cela que sert l’algorithme du mariage stable, il permet de créer des paires ou couples stables, en tenant compte des préférences. C'est un cas particulier ou une variante de l'algorithme des couplages parfaits.
Mariages Stable
Le problème
On a 2 groupes avec le même nombre d'individus par groupe. Chaque individu de chaque groupe note chaque individu de l'autre groupe par ordre de préférence. Le but: faire des couples en fonction des préférences pour que les couples soient stables.
Avec stable qui voudrait dire que si quelqu’un préfère un autre à son partenaire ce dernier ne le préfère pas en retour.
Algorithme en pseudo code
Entrée:
- GRP_1 avec n individus
- GRP_2 avec n individus
Tant que tout element dans GRP_1 n'est pas dans un couple:
X <- individu sans couple dans GRP_1
Pour i allant de 1 à n :
Y <- le i-ème individu dans la liste de préférences de X
Si Y n'est pas encore en couples:
Mettre en couple X avec Y
Sortir de la boucle pour X
Sinon:
Z <- individu en couple avec Y
Si Y préfère X à Z:
Enlève de couple Z et Y
Mettre en couple X avec Y
Sortir de la boucle
Fin Sinon
Fin Si
Fin Pour
Fin Tant que
Variante de l'algorithme
Couplages Parfaits
Le problème
Dans un graphe biparti quelconque, le but est de trouver un couplage parfait c'est à dire un couplage où chaque sommet de chaque groupe est couplé à un sommet de l'autre groupe.
Pour cela, on va utiliser des chemins augmentants pour ajouter un couple à chaque fois, jusqu'à ce que le couplage soit parfait, en partant du principe qu'un tel couplage existe.
Algorithme en pseudo code
Entrée:
- Graphe biparti G, où GRP_1 et GRP_2 sont les deux groupes de n sommets.
Fonction CouplageParfait(G):
C <- Créer Couplage Vide()
Tant que nombre des couplage dans C est différent de n:
S <- sommet_sans_couple(GRP_1)
P <- créer chemin vide()
mettre tout les sommets comme non visité()
ajoute couplage (C, Trouve_Chemin_Augmentant (G,C, P, S))
Fin tant que
renvoie C
Fonction Trouve_Chemin_Augmentant (G,C,P,S):
Mettre dans sommet visité(S)
Pour chaque voisin T, de S dans G :
Si T n'est pas visité et peut former un chemin augmentant et T non sommet visité:
Ajouter T à P
Marquer T comme visité
Si T est en couple avec un autre sommet Z dans C:
Si Trouve_Chemin_Augmentant(G, C, P, Z):
Retourner P
Sinon:
Retourner P
Retourner P
Implémentation
Mariages Stable Classique
Contexte
On a deux groupes de n individus, et chaque individu d’un groupe trie tous les individus de l’autre groupe.
Exemple en C
#include <stdio.h>
#include <stdlib.h>
typedef struct _noeuds
{
char nom[50];
struct _noeuds* voisin;
struct _noeuds** liste_pref;
}noeuds;
typedef struct
{
noeuds** grp1;
noeuds** grp2;
int len;
} liste_noeuds;
noeuds* get_noeuds_sans_voisins(liste_noeuds lst )
{
noeuds* voisin = 0;
int i = 0;
while(i < lst.len && voisin == 0)
{
if( lst.grp1[i]->voisin == 0)
{
voisin = lst.grp1[i];
}
i++;
}
return voisin;
}
int get_ordre_pref(noeuds* noeud, noeuds* voisin)
{
int i = 0;
int trouvee = 0;
while (! trouvee)
{
if (noeud->liste_pref[i] == voisin)
{
trouvee = 1;
}
else{
i++;
}
}
return i;
}
void create_couple(liste_noeuds lst)
{
noeuds* noeud = get_noeuds_sans_voisins( lst);
while( noeud != 0)
{
int i = 0;
while( noeud->voisin == 0)
{
noeuds* voisin_pref = noeud->liste_pref[i];
for (int i = 0; i < lst.len; i++)
{
printf("%s avec %s\n", lst.grp1[i]->nom, lst.grp1[i]->voisin->nom);
}
printf("\n");
if(voisin_pref->voisin == 0)
{
voisin_pref->voisin = noeud;
noeud->voisin = voisin_pref;
}
else
{
if (get_ordre_pref(voisin_pref,noeud)<get_ordre_pref(voisin_pref, voisin_pref->voisin) && 1)
{
==Mariages Stable adapté pour Parcoursup==
noeud->voisin = voisin_pref;
voisin_pref->voisin->voisin = 0;
voisin_pref->voisin = noeud;
}
else
{
i++;
}
}
}
noeud = get_noeuds_sans_voisins(lst);
}
}
int main()
{
liste_noeuds lst;
lst.grp1 = malloc(4*sizeof(noeuds));
lst.grp2 = malloc(4*sizeof(noeuds));
lst.len = 4;
noeuds** pref_A = malloc(4*sizeof(noeuds*));
noeuds A = {"A", 0, pref_A};
lst.grp1[0]= &A;
noeuds** pref_B = malloc(4*sizeof(noeuds*));
noeuds B = {"B", 0, pref_B};
lst.grp1[1]= &B;
noeuds** pref_C = malloc(4*sizeof(noeuds*));
noeuds C = {"C", 0, pref_C};
lst.grp1[2] = &C;
noeuds** pref_D= malloc(4*sizeof(noeuds*));
noeuds D = {"D", 0, pref_D};
lst.grp1[3] = &D;
noeuds** pref_E= malloc(4*sizeof(noeuds*));
noeuds E = {"E", 0, pref_E};
lst.grp2[0] = &E;
noeuds** pref_F= malloc(4*sizeof(noeuds*));
noeuds F = {"F", 0, pref_F};
lst.grp2[1] = &F;
noeuds** pref_I= malloc(4*sizeof(noeuds*));
noeuds I = {"I", 0, pref_I};
lst.grp2[2] = &I;
noeuds** pref_H= malloc(4*sizeof(noeuds*));
noeuds H = {"H", 0, pref_H};
lst.grp2[3] = &H;
pref_A[0] = &E;
pref_A[1] = &F;
pref_A[2] = &H;
pref_A[3] = &I;
pref_B[0] = &H;
pref_B[1] = &F;
pref_B[2] = &I;
pref_B[3] = &E;
pref_C[0] = &I;
pref_C[1] = &H;
pref_C[2] = &E;
pref_C[3] = &F;
pref_D[0] = &E;
pref_D[1] = &I;
pref_D[2] = &H;
pref_D[3] = &F;
pref_E[0] = &B;
pref_E[1] = &C;
pref_E[2] = &A;
pref_E[3] = &D;
pref_F[0] = &B;
pref_F[1] = &A;
pref_F[2] = &D;
pref_F[3] = &C;
pref_H[0] = &C;
pref_H[1] = &A;
pref_H[2] = &B;
pref_H[3] = &D;
pref_I[0] = &A;
pref_I[1] = &B;
pref_I[2] = &D;
pref_I[3] = &C;
create_couple(lst);
printf("%s avec %s\n", A.nom, A.voisin->nom);
printf("%s avec %s\n", B.nom, B.voisin->nom);
printf("%s avec %s\n", C.nom, C.voisin->nom);
printf("%s avec %s\n", D.nom, D.voisin->nom);
free(lst.grp1);
free(lst.grp2);
free(pref_A);
free(pref_B);
free(pref_C);
free(pref_D);
free(pref_E);
==Mariages Stable adapté pour Parcoursup==
free(pref_F);
free(pref_H);
free(pref_I);
}