Algorithme hongrois

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme hongrois ou méthode hongroise (parfois appelé aussi algorithme de Kuhn-Munkres) est un algorithme d'optimisation combinatoire, qui résout le problème d'affectation en temps polynomial. Il a été proposé en 1955 par le mathématicien américain Harold Kuhn[1], 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).

James Munkres (en) a revu l'algorithme en 1957 et a prouvé qu'il s'exécutait en temps polynomial[2].

Description de l'algorithme[modifier | modifier le code]

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

\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 O(n^4).

Étape 0

Pour chaque ligne de la matrice, on retire à 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 un zéro par ligne et par colonne.

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

Il faut à ce moment sélectionner le maximum possible de zéros indépendants, c'est-à-dire de façon à ce qu'il n'y ait qu'un zéro sélectionné 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. Les étapes 1 et 2 vont permettre de sélectionner le maximum de zéros indépendants.


É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 court 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 et couvrez la ligne.
× ×
0 a2 a3 a4
b1 b2 b3 0
c1 c2 c3 0
d1 0 0' d4 ×
    • 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'
  • 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, la couverture les lignes et colonnes, et les primes.

Optimalité de la solution trouvée[modifier | modifier le code]

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 correspondantes à 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[modifier | modifier le code]

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 ou l'on effectuerai 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; la taille des entiers manipulés au fur et à mesure de l'algorithme restant forcement polynomial (car seule les étapes 0 et 3, modifient la matrice et toute deux ne peuvent faire augmenter la somme de tous les entiers de la matrice).

Complexité de l'algorithme original[modifier | modifier le code]

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 si elle contient déjà un zéro sélectionné, il suffit de parcourir tous les éléments de la matrice, vérifier si c'est un zéro et si sa ligne et sa colonne contiennent un zéro sélectionné.
  • Étape 2 : O(n^2). En listant les zéros non-couverts, et en ajoutant à 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'il le sont toujours. On couvre au plus n ligne, à 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épendant dans la matrice au début de l’exécution de l'étape 3 pour la k-ième fois. On remarque facilement 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 ligne couverte qu'au début de la (k)ème étape 3: Tout d'abord on remarque facilement que les zéros sélectionnés et primes son 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 remarque aisément que les seules opérations qui peuvent être réalisé 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 aucune problème en arithmétique multiprécision. On remarque facilement que après l'étape 2, et donc en début d'étape 3, le nombre de colonne non-converte est supérieur ou égale au nombre de ligne converte. Donc dans l'étape 3 on va retirer \Lambda au moins autant de fois que l'on ne va l'ajouter.

Présentation de l'amélioration en O(n^3)[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) « Harold W. Kuhn, in his celebrated paper entitled The Hungarian Method for the assignment problem, [Naval Research Logistic Quarterly, 2 (1955), pp. 83-97] described an algorithm for constructing a maximum weight perfect matching in a bipartite graph » dans András Frank (en), On Kuhn’s Hungarian Method – A tribute from Hungary
  2. (en) James Munkres, Algorithms for the assignement and transportation Problem