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.