Algorithme d’Edmonds

L’objectif de l’algorithme d’Edmonds est de trouver un couplage parfait (de cardinal maximum) dans un problème d’affectation.

Le problème de couplage est le suivant :

Construire un graphe biparti (les éléments de gauche ne sont reliés qu’à des éléments de droite par des arcs, les éléments de droites n’ont pas de liaison sortante) tel que les éléments de gauche soient les machines et les éléments de droites soient les tâches à effectuer. Les arcs sont de capacité 1 et de coût en fonction du tableau d’affectation. Si un flot passe par une arête (i,j), cela revient à dire que la machine i effectue la tâche j.
Afin de compléter le graphe biparti pour en faire un problème de flot, chaque élément de gauche est lié en tant que sommet terminal à une source fictive.  Chaque élément de droite est lié en tant que sommet d’origine à un puits fictif. Tous ces arcs sont de capacité 1 et de coût 0. Afin de résoudre le problème d’affectation, on applique un algorithme de flot maximum à coût minimal au graphe biparti construit.

edmonds.png

Publicités