Algorithme hongrois en Python : résoudre un problème d’affectation optimale

L’algorithme hongrois, aussi appelé méthode hongroise ou algorithme de Kuhn-Munkres, sert à résoudre un problème d’affectation optimale. Le cas typique : vous avez plusieurs agents, plusieurs tâches, et un coût pour chaque association possible. L’objectif est d’affecter chaque tâche à un agent avec le coût total minimal.

Exemple concret : trois techniciens doivent intervenir sur trois sites. Chaque technicien a un coût différent selon le site. Quelle combinaison minimise le coût total ?

En Python, la solution pratique est d’utiliser scipy.optimize.linear_sum_assignment.

import numpy as np
from scipy.optimize import linear_sum_assignment

couts = np.array([
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
])

lignes, colonnes = linear_sum_assignment(couts)

print(list(zip(lignes, colonnes)))
print(couts[lignes, colonnes].sum())

Résultat :

[(0, 1), (1, 0), (2, 2)]
9

Cela signifie :

• agent 0 vers tâche 1, coût 2 ;
• agent 1 vers tâche 0, coût 6 ;
• agent 2 vers tâche 2, coût 1 ;
• coût total : 9.

La réponse courte

Utilisez l’algorithme hongrois quand vous devez faire une affectation un-pour-un avec coût minimal.

from scipy.optimize import linear_sum_assignment

lignes, colonnes = linear_sum_assignment(matrice_de_couts)
cout_total = matrice_de_couts[lignes, colonnes].sum()

Le problème doit être exprimé comme une matrice :

L’algorithme renvoie les paires ligne-colonne qui minimisent la somme totale.

Comprendre le problème d’affectation

Supposons cette matrice :

couts = [
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
]

Chaque ligne représente un agent. Chaque colonne représente une tâche.

couts[0][1] = coût de l'agent 0 pour la tâche 1

Une affectation valide doit choisir une seule valeur par ligne et une seule valeur par colonne.

Par exemple :

[(0, 1), (1, 0), (2, 2)]

coûte :

couts[0][1] + couts[1][0] + couts[2][2]

soit :

2 + 6 + 1 = 9

Le but est de trouver l’affectation valide la moins chère.

Pourquoi ne pas tout essayer ?

Pour une matrice n x n, une recherche exhaustive doit tester toutes les permutations.

n!

Pour 3 tâches, cela reste facile. Pour 10, il y a déjà 3 628 800 affectations possibles. Pour 20, ce n’est plus réaliste.

L’algorithme hongrois résout ce problème de manière beaucoup plus efficace, souvent résumé en O(n^3) pour le cas carré classique.

Vérifier sur un petit cas avec brute force

Pour apprendre, on peut comparer SciPy avec une version brute force sur une petite matrice.

from itertools import permutations


def affectation_bruteforce(couts):
    n = len(couts)
    meilleur_cout = float("inf")
    meilleure_affectation = None

    for permutation in permutations(range(n)):
        cout = sum(couts[i][permutation[i]] for i in range(n))

        if cout < meilleur_cout:
            meilleur_cout = cout
            meilleure_affectation = list(enumerate(permutation))

    return meilleur_cout, meilleure_affectation

Test :

couts = [
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
]

cout, affectation = affectation_bruteforce(couts)

print(cout)
print(affectation)

Résultat :

9
[(0, 1), (1, 0), (2, 2)]

Cette version est utile pour comprendre et tester, pas pour de grands problèmes.

Utiliser SciPy en pratique

SciPy gère directement la matrice de coûts.

import numpy as np
from scipy.optimize import linear_sum_assignment


def affectation_optimale(couts):
    couts = np.asarray(couts)
    lignes, colonnes = linear_sum_assignment(couts)
    cout_total = couts[lignes, colonnes].sum()

    affectations = list(zip(lignes.tolist(), colonnes.tolist()))

    return cout_total, affectations

Utilisation :

cout_total, affectations = affectation_optimale([
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
])

print(cout_total)
print(affectations)

Matrice rectangulaire

Le nombre d’agents et le nombre de tâches ne sont pas toujours identiques. linear_sum_assignment accepte aussi les matrices rectangulaires.

couts = np.array([
    [4, 1, 3, 2],
    [2, 0, 5, 3],
    [3, 2, 2, 3],
])

lignes, colonnes = linear_sum_assignment(couts)

print(list(zip(lignes, colonnes)))
print(couts[lignes, colonnes].sum())

Dans ce cas, toutes les lignes ne couvrent pas forcément toutes les colonnes. L’algorithme choisit une affectation optimale pour le plus petit côté de la matrice.

Si votre problème exige que toutes les tâches soient couvertes, vérifiez la forme de la matrice et ajoutez des agents fictifs ou des tâches fictives avec un coût approprié.

Maximiser un gain au lieu de minimiser un coût

L’algorithme hongrois minimise une matrice de coûts. Si vous avez une matrice de gains à maximiser, transformez-la en coût.

gains = np.array([
    [10, 5, 8],
    [7, 9, 6],
    [6, 4, 12],
])

couts = gains.max() - gains

lignes, colonnes = linear_sum_assignment(couts)

gain_total = gains[lignes, colonnes].sum()

print(list(zip(lignes, colonnes)))
print(gain_total)

On peut aussi utiliser l’argument maximize=True si votre version de SciPy le supporte.

lignes, colonnes = linear_sum_assignment(gains, maximize=True)

Vérifiez la version de SciPy disponible dans votre environnement.

Étapes de la méthode hongroise

La méthode hongroise classique repose sur des transformations de matrice qui préservent les affectations optimales.

En simplifiant :

1. soustraire le minimum de chaque ligne ;
2. soustraire le minimum de chaque colonne ;
3. couvrir les zéros avec un nombre minimal de lignes ;
4. ajuster la matrice si l’affectation complète n’est pas encore possible ;
5. extraire une affectation optimale.

L’idée importante : on transforme la matrice pour faire apparaître des zéros exploitables, sans changer le problème d’optimisation.

Dans un code de production, il est préférable d’utiliser SciPy plutôt que de réimplémenter toute la méthode, sauf objectif pédagogique.

Cas d’usage

La méthode hongroise apparaît dans de nombreux problèmes :

• affecter des employés à des tâches ;
• assigner des livreurs à des courses ;
• associer des prédictions à des objets détectés ;
• répartir des machines sur des opérations ;
• minimiser un coût de transport ou de planning ;
• faire du matching dans un pipeline de vision ou de suivi d’objets.

Le point commun est toujours le même : une ressource ne doit être utilisée qu’une fois, et chaque affectation a un coût ou un gain.

Erreurs fréquentes

Mélanger coût et gain

Si la matrice contient des scores à maximiser, ne l’envoyez pas directement comme matrice de coûts sans transformation.

Oublier le sens lignes-colonnes

Documentez clairement ce que représentent les lignes et les colonnes. Sinon, le résultat est difficile à interpréter.

Croire que l’algorithme gère les contraintes métier complexes

L’algorithme hongrois résout une affectation un-pour-un. Si vous avez des capacités, des dépendances, des horaires, des contraintes multiples ou des affectations plusieurs-pour-un, vous entrez peut-être dans un problème d’optimisation plus général.

Utiliser brute force sur une grande matrice

La version avec permutations explose très vite. Gardez-la pour les tests ou les démonstrations.

Ignorer les valeurs interdites

Si une affectation est impossible, donnez-lui un coût très élevé, ou modélisez autrement le problème. Ne mettez pas un coût faible par accident.

Exercices rapides

Exercice 1

Trouvez l’affectation optimale :

couts = [
    [4, 2, 8],
    [2, 3, 7],
    [3, 1, 6],
]

Correction avec brute force :

print(affectation_bruteforce(couts))

Exercice 2

Transformez cette matrice de gains en problème de minimisation :

gains = np.array([
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
])

Correction :

couts = gains.max() - gains

Exercice 3

Ajoutez des noms lisibles aux lignes et colonnes.

agents = ["Amina", "Yanis", "Lea"]
taches = ["Audit", "Support", "Migration"]

Correction :

cout_total, affectations = affectation_optimale(couts)

for i, j in affectations:
    print(agents[i], "->", taches[j])

Pour aller plus loin

L’algorithme hongrois est un excellent exemple d’optimisation combinatoire : on part d’un problème très concret, mais une recherche exhaustive devient vite impossible. La bonne modélisation, matrice de coûts, sens des lignes, sens des colonnes et gestion des contraintes, compte autant que l’algorithme lui-même.

À lire ensuite :

• Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
• Algorithmes de graphes en Python : le guide pour bien démarrer
• Méthode de Monte Carlo en Python

La règle à retenir : exprimez votre problème comme une matrice de coûts, puis utilisez linear_sum_assignment pour obtenir l’affectation optimale.

Références

• Documentation SciPy : scipy.optimize.linear_sum_assignment
• Wikipedia : Hungarian algorithm
• Wikipedia : Assignment problem