IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

f-leb

[Python] Problèmes d'affectation - la méthode hongroise

Noter ce billet
par , 24/10/2014 à 17h07 (4346 Affichages)
Ce qu'il y a de bien avec Python, c'est que le module miracle qui résout votre problème existe forcément quelque part. Il faut juste mettre le doigt dessus...

J'ai été récemment confronté au problème d'affectation du genre du tableau ci-dessous :
P1 P2 P3 P4 P5
e1 17 15 9 5 12
e2 16 16 10 5 10
e3 12 15 14 11 5
e4 4 8 14 17 13
e5 13 9 8 12 17

J'ai 5 postes (P1 à P5) qui doivent être attribués à 5 élèves (e1 à e5), évidemment 1 poste=1 élève, ni plus, ni moins.
Attribuer un poste à un élève a un « coût ». Par exemple, attribuer le poste P1 à l'élève e1 a un « coût » qui vaut 17 alors qu'attribuer ce même poste P1 à l'élève e2 aurait un « coût » moindre égal à 16, etc. D'où la représentation matricielle ci-dessus qui définit les « coûts » pour chaque combinaison (Pi, ei).

Le problème : comment attribuer « au mieux » les postes, c'est-à-dire en minimisant le coût global .

La solution peut être obtenue par la fameuse « méthode hongroise » ou algorithme de Kuhn-Munkres (j'aurais mis le temps à mettre un nom dessus).

Par cette méthode on montre que le « coût minimal » est égal à 32 et dont voici les affectations possibles :
P1 P2 P3 P4 P5
e1 17 15 [9] 5 12
e2 16 16 10 [5] 10
e3 12 15 14 11 [5]
e4 [4] 8 14 17 13
e5 13 [9] 8 12 17
9 + 5 + 5 + 4 + 9 = 32

L'implantation de cet algorithme pour Python 2 et 3 est sur PyPi : Index of Packages Matching 'munkres'.

Exemple d'utilisation dans une console IPython :
Code python : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
In [1]: from munkres import Munkres, print_matrix
 
In [2]: matrix = [[17, 15, 9, 5, 12],
                  [16, 16, 10, 5, 10],
                  [12, 15, 14, 11, 5],
                  [4, 8, 14, 17, 13],
                  [13, 9, 8, 12, 17]]
 
In [3]: m = Munkres()
 
In [4]: indexes = m.compute(matrix)
 
In [5]: print_matrix(matrix)
[17, 15,  9,  5, 12]
[16, 16, 10,  5, 10]
[12, 15, 14, 11,  5]
[ 4,  8, 14, 17, 13]
[13,  9,  8, 12, 17]
 
In [6]: indexes
Out[6]: [(0, 2), (1, 3), (2, 4), (3, 0), (4, 1)]
 
In [7]: print ('coût=', sum([matrix[i[0]][i[1]] for i in indexes]))
Out[7]: coût= 32

La liste indexes retourne pour chaque ligne de la matrice entre 0=e1 et 4=e5 (c'est-à-dire pour chaque élève), le numéro du poste d'affectation entre 0=P1 et 4=P5.

Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Viadeo Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Twitter Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Google Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Facebook Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Digg Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Delicious Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog MySpace Envoyer le billet « [Python] Problèmes d'affectation - la méthode hongroise » dans le blog Yahoo

Mis à jour 25/01/2015 à 23h08 par f-leb

Tags: python
Catégories
Programmation , Python

Commentaires

  1. Avatar de Spike_Spiegel
    • |
    • permalink
    J'adore ! Je ne vais pas avoir besoin de ça tout de suite, tout de suite mais savoir que ça existe c'est le pied. Merci et n'hésite pas à continuer ^^