Le blog de f-leb

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.