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

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