Algorithme hongrois

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 :

${\displaystyle {\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}}}$

La version présentée ici correspond essentiellement à la version de Munkres en ${\displaystyle O(n^{4})}$.

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

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

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

La suite ${\displaystyle 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 ${\displaystyle \Lambda }$, la valeur minimum de la sous-matrice des éléments non couverts trouvée à l'étape 2. Il faut alors ajouter ${\displaystyle \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, la couverture les lignes et colonnes, et les primes.

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.

On peut montrer que l'algorithme, tel que présenté ici, s’arrête nécessairement en moins de ${\displaystyle 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 à ${\displaystyle O(n^{3})}$. 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 ${\displaystyle 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 ${\displaystyle 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.

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

• Étape 0 : ${\displaystyle 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 : ${\displaystyle 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 : ${\displaystyle 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' : ${\displaystyle O(n^{2})}$.
• Étape 3 : ${\displaystyle O(n^{2})}$.

Soit ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(n^{2})}$ des étapes présentées ci-dessus. Donc la complexité totale est ${\displaystyle 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 ${\displaystyle \Lambda }$ au moins autant de fois qu'on l'ajoute.

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[1]. 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 ${\displaystyle a\in A}$ et ${\displaystyle b\in B}$ est de poids ${\displaystyle c_{ab}}$.

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	${\displaystyle \sum _{a\in A,b\in B}c_{ab}x_{ab}}$			(minimiser le coût total)
tel que	${\displaystyle \sum _{b\in B}x_{ab}=1}$	pour tout ${\displaystyle a\in A}$		(chaque sommet de ${\displaystyle A}$ est adjacent à une arête sélectionnée)
et	${\displaystyle \sum _{a\in A}x_{ab}=1}$	pour tout ${\displaystyle b\in B}$		(chaque sommet de ${\displaystyle B}$ est adjacent à une arête sélectionnée)
	${\displaystyle x_{ab}\in \{0,1\}}$	pour tout ${\displaystyle a\in A,b\in B}$.		(la variable ${\displaystyle 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 ${\displaystyle x_{ab}\in \{0,1\}}$ par ${\displaystyle x_{ab}\geq 0}$. Le dual de ce nouveau programme peut être écrit de la façon suivante :

maximiser	${\displaystyle \sum _{a\in A}u_{a}+\sum _{b\in B}v_{b}}$
tel que	${\displaystyle u_{a}+v_{b}\leq c_{ab}}$	pour tout ${\displaystyle 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 : ${\displaystyle x_{ab}\neq 0\Rightarrow u_{a}+v_{b}=c_{ab}\forall a\in A,b\in B.}$

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 : ${\displaystyle 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 ${\displaystyle 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].
   2. Fixer : ${\displaystyle \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, ${\displaystyle u_{a}:=u_{a}+\epsilon }$
      • Si b est dans le voisinage de S, ${\displaystyle v_{b}:=v_{b}-\epsilon }$
3. Retourner un couplage parfait de G.

L'algorithme a une complexité en temps cubique[1].