Algorithme hongrois

En informatique, plus précisément en algorithmique et en optimisation combinatoire, l'algorithme hongrois ou méthode hongroise, aussi appelé algorithme de Kuhn-Munkres, est un algorithme 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.

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).

Algorithme

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.

Description matricielle

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. A des fins d'illustrations, on suppose que l'on a 4 équipes a, b, c, d et 4 tâches numérotées 1, 2, 3 et 4. On illustre ici l'algorithme avec une matrice de taille 4×4 :

${\begin{bmatrix}a_{1}&a_{2}&a_{3}&a_{4}\\b_{1}&b_{2}&b_{3}&b_{4}\\c_{1}&c_{2}&c_{3}&c_{4}\\d_{1}&d_{2}&d_{3}&d_{4}\end{bmatrix}}$

où a₁, a₂, a₃, and a₄ sont respectivement les temps de travail pour l'équipe a pour faire les tâches 1, 2, 3 et 4 respectivement (et pareil pour les autres équipes).

La version présentée ici correspond essentiellement à la version de Munkres^{[réf. nécessaire]} en $O(n^{4})$.

Étape 0

Dans chaque ligne, on considère l'élément minimal. On le soustrait à chaque élément de la ligne. La matrice obtenue 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.

0	a2'	a3'	a4'
b1'	b2'	b3'	0
c1'	c2'	c3'	0
d1'	0	0	d4'

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é.

0	a2	a3	a4
b1	b2	b3	0
c1	c2	c3	0
d1	0	0	d4

Si l'on a sélectionné n zéros, alors on arrête l'algorithme.

Si l'on a sélectionné au moins un zéro supplémentaire au cours de cette étape, découvrez toutes les lignes et colonnes, retirez tous les primes (voir plus bas).

Étape 2

• Couvrir chaque colonne ayant un zéro sélectionné.

×	×		×
0	a2	a3	a4
b1	b2	b3	0
c1	c2	c3	0
d1	0	0	d4

• Choisissez successivement un zéro non couvert, marquez-le d'un prime, puis
  • S'il y a un zéro sélectionné sur sa ligne, alors découvrez la colonne de ce zéro-là et couvrez la ligne.
  • S'il n'y a pas de zéro sélectionné sur sa ligne, alors on n'a pas sélectionné le nombre maximal de zéros indépendants, passez à l'étape 2'

×			×
0	a2	a3	a4
b1	b2	b3	0
c1	c2	c3	0
d1	0	0'	d4	×

• S'il n'y a plus de zéro non couvert, alors d'après le théorème de König on a sélectionné le nombre maximal de zéros indépendants, et on a le nombre minimum de lignes et colonnes qui couvrent tous les zéros. Passez à l'étape 3.

Étape 2'

On est dans le cas où l'on n'a pas sélectionné le nombre maximal de zéros indépendants.

Soit $z_{0}$ le seul 0' qui n'est pas couvert. Soit $z_{1}$ le zéro sélectionné sur la colonne de $z_{0}$ (qui existe sinon $z_{0}$ serait sélectionné à l'étape 1). Soit alors, $z_{i}$, i pair, le 0' sur la ligne de $z_{i-1}$ qui existe nécessairement; et $z_{i}$, i impair, le zéro sélectionné sur la colonne de $z_{i-1}$ s'il existe (sinon on arrête la suite).

La suite $z_{i}$ comprend alors un 0' de plus que de zéro sélectionné. On peut alors directement substituer ces 0' aux zéros sélectionnés de la suite. On a alors un ensemble avec un zéro indépendant de plus que précédemment. On retourne à l'étape 1, en gardant les nouveaux zéros sélectionnés, mais en effaçant les primes, et les couvertures de colonnes et lignes.

Étape 3

Trouvez $\Lambda$, la valeur minimum de la sous-matrice des éléments non couverts trouvée à l'étape 2. Il faut alors ajouter $\Lambda$ à toutes les lignes couvertes, et la retirer à toutes les colonnes non couvertes.

Retournez à l'étape 1, en conservant la sélection des zéros, et les primes.

Optimalité de la solution trouvée

On remarque que les seules modifications réalisées sur la matrice au cours de cet algorithme sont l'addition et la soustraction d'une valeur à l'ensemble d'une ligne ou d'une colonne. Une telle modification n’altère pas la ou les affectations optimales, mais uniquement le coût optimal. L'algorithme navigue donc entre des matrices correspondant à des problèmes équivalents.

De plus les valeurs de la matrice étant, et restant positives, l'algorithme ne peut s’arrêter, en étape 1, que sur une solution optimale pour la matrice modifiée (car de coût nul), et donc pour le problème original.

Démonstration du temps d’exécution polynomial

On peut montrer que l'algorithme, tel que présenté ici, s’arrête nécessairement en moins de $O(n^{4})$ opérations. Cependant, une amélioration proposée par Edmonds et Karp, (et Tomizawa indépendamment), permet de réduire le temps d’exécution à $O(n^{3})$^{[réf. souhaitée]}. On remarquera que n est en réalité la dimension de la matrice, et non la taille de l'entrée qui est elle de $n^{2}$. On considère ici que l'addition, la soustraction, et la comparaison d'entiers sont des opérations de base et nécessitent $O(1)$. Cela dit, dans le cas contraire où l'on effectuerait les calculs sur des entiers longs (arithmétique multiprécision), cela ne changerait en rien l'aspect polynomial de l'algorithme par rapport à la taille de l'entrée du problème. En effet, la taille des entiers manipulés au fur et à mesure de l'algorithme reste forcément polynomiale, car seules les étapes 0 et 3 modifient la matrice et toutes deux ne peuvent faire augmenter la somme de tous les entiers de la matrice.

Complexité de l'algorithme original

Listons le nombre d'opérations nécessaires pour l’exécution de chacune des étapes.

• Étape 0 : $O(n^{2})$. Pour chaque ligne et chaque colonne, n opérations pour calculer le minimum, puis n opérations pour le soustraire à chaque élément.
• Étape 1 : $O(n^{2})$. En gardant en mémoire pour chaque ligne et chaque colonne un booléen disant si elle contient déjà un zéro sélectionné, il suffit de parcourir tous les éléments de la matrice, en vérifiant si c'est un zéro et si sa ligne et sa colonne contiennent un zéro sélectionné.
• Étape 2 : $O(n^{2})$. Lister les zéros non couverts, et ajouter à cette liste les zéros nouvellement découverts lorsque l'on découvre une colonne. On suit alors la liste des zéros non couverts en vérifiant qu'ils le sont toujours. On couvre au plus n lignes, et, à chaque couverture de ligne, il est nécessaire de parcourir une ligne et une colonne, soit 2n cases.
• Étape 2' : $O(n^{2})$.
• Étape 3 : $O(n^{2})$.

Soit $n_{k}$ le nombre maximal de zéros indépendants dans la matrice au début de l’exécution de l'étape 3 pour la k-ième fois. On remarque facilement que, si $n_{k}=n_{k+1}$, alors il n'y aura pas d'étape 2' entre la (k)ème et la (k+1)ème étape 3, car dans ce cas après la (k)ème étape 3 on a toujours sélectionné le nombre maximal de zéros indépendants. On peut de plus démontrer que, sous cette même hypothèse, au début de la (k+1)ème étape 3 on aura strictement plus de lignes couvertes qu'au début de la (k)ème étape 3. En effet, on remarque d'abord facilement que les zéros sélectionnés et primes sont conservés par l'étape 3. Étant donné que l'on a déjà sélectionné le nombre maximal de zéros indépendants après la (k)ème étape 3, on démontre aisément que les seules opérations qui peuvent être réalisées entre la (k)ème étape 3 et la (k+1)ème étape3 sont des couvertures de ligne. Il y aura au moins une couverture de ligne, car l'étape 3 fait apparaitre un zéro non couvert à l'endroit du minimum des éléments non couverts.

On en déduit qu'il ne peut y avoir que n successions d'étapes 1, 2 et 3 avant d'obtenir un zéro indépendant supplémentaire. L'algorithme se poursuit jusqu'à obtenir une matrice avec n zéros indépendants. Lors de l'obtention de x zéros indépendants supplémentaires à l'étape 3, au plus x étapes 2' se trouveront exécutées.

On en déduit que l'algorithme s’arrête, après l’exécution d'au plus $O(n^{2})$ des étapes présentées ci-dessus. Donc la complexité totale est $O(n^{4})$.

On peut de plus démontrer que l'étape 3 ne peut augmenter la somme totale des entiers dans la matrice, et donc ne pose aucun problème en arithmétique multiprécision. En effet, après l'étape 2, et donc en début d'étape 3, le nombre de colonnes non couvertes est supérieur ou égal au nombre de lignes couvertes. Donc dans l'étape 3 on retire $\Lambda$ au moins autant de fois qu'on l'ajoute.

Description par l'optimisation linéaire

On présente maintenant l'algorithme depuis un autre point de vue. L'algorithme est le même, mais on utilise les résultats d'optimisation linéaire pour l'étudier. On se place dans un graphe biparti dont les sommets sont divisés en deux groupes A et B de même cardinal, et où l'arête entre $a\in A$ et $b\in B$ est de poids $c_{ab}$.

Représentation par l'optimisation linéaire

Le programme d'optimisation linéaire en nombres entiers pour le problème du couplage parfait de poids minimum est le suivant, où la variable  :

minimiser	$\sum _{a\in A,b\in B}c_{ab}x_{ab}$			(minimiser le coût total)
tel que	$\sum _{b\in B}x_{ab}=1$	pour tout $a\in A$		(chaque sommet de $A$ est adjacent à une arête sélectionnée)
et	$\sum _{a\in A}x_{ab}=1$	pour tout $b\in B$		(chaque sommet de $B$ est adjacent à une arête sélectionnée)
	$x_{ab}\in \{0,1\}$	pour tout $a\in A,b\in B$.		(la variable $x_{ab}$ vaut 1 si l'arête ab est sélectionnée, et 0 sinon)

On le relâche en un problème d'optimisation linéaire en nombres réels, en remplaçant $x_{ab}\in \{0,1\}$ par $x_{ab}\geq 0$. Le dual de ce nouveau programme peut être écrit de la façon suivante :

maximiser	$\sum _{a\in A}u_{a}+\sum _{b\in B}v_{b}$
tel que	$u_{a}+v_{b}\leq c_{ab}$	pour tout $a\in A$.

La condition d'optimalité dans ce cas est la suivante. Une solution x est optimale pour le primal (c.-à-d. pour le premier problème) s'il existe une solution (u,v) optimale pour le dual telle que : $x_{ab}\neq 0\Rightarrow u_{a}+v_{b}=c_{ab}\forall a\in A,b\in B.$

Algorithme

Le principe de l'algorithme est de transformer peu à peu une solution (u,v) pour le dual, en respectant les contraintes, pour construire une solution primale satisfaisant les contraintes d'optimalité.

L'algorithme est le suivant :

1. Initialisation : $v_{b}=0,u_{a}=min_{b\in B}c_{ab}$
2. Boucle : Tant que le graphe G constitué des arêtes (a,b) telles que $u_{a}+v_{b}=c_{ab}$ ne contient pas de couplage parfait, faire :
   1. Chercher un ensemble S de A tel que S a plus de sommets que son voisinage N(S).
   2. Fixer : $\epsilon =\min _{a\in S,b\notin N(S)}c_{ab}-u_{a}-v_{b}$.
   3. Modifier (u,v) de la manière suivante :
      • Si a est dans S, $u_{a}:=u_{a}+\epsilon$
      • Si b est dans le voisinage de S, $v_{b}:=v_{b}-\epsilon$
3. Retourner un couplage parfait de G.

Correction et complexité

L'algorithme a une complexité en temps cubique.

Historique

Il a été proposé en 1955 par le mathématicien américain Harold Kuhn, qui l'a baptisé « méthode hongroise » parce qu'il s'appuyait sur des travaux antérieurs de deux mathématiciens hongrois : Dénes Kőnig et Jenő Egerváry (en). L'article a été publié dans la revue Naval Research Logistic Quarterly car le projet de recherche était financé par l'Office of Naval Research Logistics Branch. James Munkres a revu l'algorithme en 1957, et a prouvé qu'il s'exécutait en temps polynomial.

En 2006, il a été découvert que le mathématicien allemand Charles Gustave Jacob Jacobi avait décrit l'algorithme dans un article posthume, au XIX^e siècle.

L'algorithme est vu comme une des premières apparitions de l'idée de schéma primal-dual.

Liens avec d'autres algorithmes

L'algorithme d'Edmonds pour les couplages généralise l'algorithme hongrois et traite le problème du couplage maximum dans tous les graphes en temps polynomial.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hungarian algorithm » (voir la liste des auteurs).