Discussion :

[bmw13fr]

Bonjour,

Je viens de coder l'algo des Hongrois (affectation du chemin le moins couteux)

Cet algo marche uniquement avec des matrices symétrique ...
il me semble qu'il y a une modification a faire pour le faire fonctionner avec desd matrice quelquonque, si quelqu'un à une idée ...


merci a vous !!!

[FrancisSourd]

Pourrais-tu préciser? L'algorithme hongrois résoud le problème d'affectation. Il n'est pas question de chemin dans le problème d'affectation.

De plus, les coûts d'affectation correspondent à l'affectation de i à j. La matrice n'est pas supposée symétrique et cela n'a d'ailleurs pas de sens de la considérer symétrique: pourquoi affecter le travail 3 à la personne 2 aurait-il le même coût qu'affecter le travail 2 à la personne 3?

[bmw13fr]

oups je me suis mal exprimé dsl !

Je voulais dire que les matrices devait être carré

lien wiki

[FrancisSourd]

Dans ce cas, tu peux la rendre carré et tu complètes en mettant des coûts de non affectation (nuls si tu maximises et élevés si tu minimises).

[bmw13fr]

j'y ai pensé mais ca ne fonctionne pas !
car à la premiere etape on soustrait la plus petite valeur sur les lignes
et ensuite la plus petite sur les colonnes

donc les grandes valeurs seront annulé

je viens de faire l'essai sur la matrice suivante

1 ; 4 ; 3 ; 2
4 ; 3 ; 6 ; 7
9 ; 1 ; 3 ; 4
99;99;99;99

je passe les calcules intermédiaire ...

et au final ca me donne

0 ; 4 ; 1 ; 0
0 ; 0 ; 1 ; 2
7 ; 0 ; 0 ; 1
1 ; 2 ; 0 ; 0

soit le "chemin" de cout mini représenté par les 'x'

x ; 4 ; 1 ; 0
0 ; x ; 1 ; 2
7 ; 0 ; x ; 1
1 ; 2 ; 0 ; x

ou

0 ; 4 ; 1 ; x
x ; 0 ; 1 ; 2
7 ; x ; 0 ; 1
1 ; 2 ; x ; 0

avec un cout mini dans les deux cas de 106

donc la derniere ligne n'est pas ignoré non ?
j'ai un peu du mal (bon faut dire, c'est vendredi soir )

merci de l'aide

A+++

[FrancisSourd]

Tout marche bien

Dans le problème, il y a trois affectations faites (coût 3+3+1=7) et une non-affectation (nécessaire) de coût 99.

Le coût total est 7+99=106.

[bmw13fr]

bonjour,

j'ai codé ca comme ca et ca marche


merci beaucoup !!!

[FrancisSourd]

Il faut déjà bien poser le problème avant de savoir quel algorithme utiliser. L'algorithme hongrois répond à l'affectation 1-1 (1 personne à un poste mais chaque poste ne peut recevoir qu'une personne) avec un coût d'affectation à minimiser (ou un gain à maximiser).

J'imagine que le nombre maximal de place dans chaque filière est connu. Une filière peut recevoir a priori plusieurs étudiants. Si on veut utiliser l'algorithme hongrois, il faut donc considérer individuellement les x_i places disponibles dans la filière i et faire une affectation entre les étudiants et les places disponibles.

Une meilleure approche est de travailler sur les flots dans les graphes (il y a des algorithmes très efficaces qui généralisent l'algorithme hongrois).

Mais, dans tous les cas, il faut définir une fonction à minimiser (pour évaluer ce qu'est une bonne affectation). Par exemple, on peut fixer une pénalité 0 si l'étudiant est affecté à sa filière préférée, la pénalité 1 s'il est affecté à son second choix, 4 si c'est son troisième, 16 si c'est son quatrième...