Algorithme hongrois

L'algorithme hongrois ou méthode hongroise (parfois appelé aussi algorithme de Kuhn) 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

Soit n projets et n équipes, et une matrice n×n 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.

La matrice est de la forme suivante

$\begin{bmatrix} a1 & a2 & a3 & a4\\ b1 & b2 & b3 & b4\\ c1 & c2 & c3 & c4\\ d1 & d2 & d3 & d4\end{bmatrix}$

Étape 0

Pour chaque ligne de la matrice, on retire l'ensemble de la ligne la valeur minimale de celle-ci. On obtient alors un problème équivalent au problème initial. La matrice a 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'

Étape 1

Sélectionnez le maximum de zéros possible de façon à ce qu'il n'y ait qu'un zéro sélectionné par ligne et par colonne. Si l'on a sélectionné n zéros alors on a trouvé l’affectation optimale, on arrête l'algorithme.

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

Étape 2

Marquez chaque ligne n'ayant pas de zéro sélectionné. Marquez chaque colonne ayant un zéro sur une ligne marquée. Marquez chaque ligne ayant un zéro marqué dans une colonne marquée. Répétez cette opération jusqu'à un état stable.

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

Sélectionnez alors la sous-matrice formée par les lignes marquées et par les colonnes non marquées.

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

Cette étape permet de sélectionner la plus grande sous-matrice n'ayant aucun zéro.

Étape 3

Trouvez la valeur minimum de la sous-matrice trouvée à l'étape 2. Il faut alors soustraire cette valeur à toutes les lignes marquées, et l'ajouter à toutes les colonnes marquées.

Retournez à l'étape 1.

Références

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

• (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)