Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme hongrois
Résumé
vignette|Exemple de graphe biparti pondéré (oublions l'agent 3). L'objectif de l'algorithme hongrois est de calculer un couplage parfait (chaque agent a une unique tâche, et chaque tâche est assignée à un agent) de poids minimum (somme des arêtes en rouge minimale).
L'algorithme hongrois ou méthode hongroise, aussi appelé algorithme de Kuhn-Munkres, est un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial. C'est donc un algorithme qui permet de trouver un couplage parfait de poids optimum (minimum ou maximum) dans un graphe biparti dont les arêtes sont valuées.
On peut présenter l'algorithme sous plusieurs formes. La première donnée est une présentation assez combinatoire utilisant des matrices, la seconde est une présentation dans le cadre de l'optimisation linéaire.
Soit n projets et n équipes, et une matrice n×n d'entiers positifs, contenant le temps nécessaire à chaque équipe pour réaliser chaque tâche. On souhaite affecter chaque tâche à une équipe afin de minimiser le temps total de réalisation, c'est-à-dire la somme des temps pris pour chaque tâche.
On illustre ici l'algorithme avec une matrice de la forme suivante :
La version présentée ici correspond essentiellement à la version de Munkres en .
Étape 0
Pour chaque ligne de la matrice, on soustrait à l'ensemble de la ligne la valeur minimale de celle-ci. La matrice a alors au moins un zéro par ligne.
On répète la même opération sur les colonnes. On obtient alors un problème équivalent avec une matrice ayant au moins un zéro par ligne et par colonne.
Les étapes 1 et 2 vont permettre de sélectionner le maximum de zéros indépendants, c'est-à-dire sélectionner un seul zéro par ligne et par colonne. La procédure pour trouver le nombre maximum de zéros indépendants est explicitée par Munkres, là où Kuhn n'apportait pas de méthode constructive pour réaliser cette étape.
Étape 1
On parcourt tous les zéros (non sélectionnés) et on sélectionne chaque zéro (en rouge ici) s'il n'est pas dans la même ligne ou colonne qu'un zéro déjà sélectionné.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.