ALGORITHME HONGROIS PROPOSÉ PAR KUHN
nosferaltu0
Messages postés
36
Date d'inscription
mardi 6 mai 2008
Statut
Membre
Dernière intervention
6 juin 2008
-
14 mai 2008 à 16:10
lwapet Messages postés 1 Date d'inscription vendredi 22 juillet 2016 Statut Membre Dernière intervention 22 juillet 2016 - 22 juil. 2016 à 20:58
lwapet Messages postés 1 Date d'inscription vendredi 22 juillet 2016 Statut Membre Dernière intervention 22 juillet 2016 - 22 juil. 2016 à 20:58
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/46664-algorithme-hongrois-propose-par-kuhn
https://codes-sources.commentcamarche.net/source/46664-algorithme-hongrois-propose-par-kuhn
Modifié par lwapet le 22/07/2016 à 21:02
Cependant l'algo boucle indéfiniment pour la matrice suivante en entrée
dans le fichier des données;(exemple.txt)
10
0 2 8 8 12 5 2 5 2 2
1 1 7 1 2 7 0 8 2 5
5 2 3 9 6 12 5 3 2 5
13 9 9 3 0 4 9 3 45 5
5 2 3 6 12 5 2 3 24 4
13 9 3 0 4 13 9 3 0 4
5 2 3 6 12 5 2 3 9 3
5 2 3 12 5 3 6 12 3 2
1 3 9 3 0 4 13 9 3 4
5 2 3 12 5 2 3 6 1 2
6 mai 2014 à 22:25
16 févr. 2013 à 12:34
17 mai 2010 à 19:13
La méthode est très bien décrite mais à la fin il y a marqué qu'on doit recommencer la procédure jusqu'à ce que la solution soit optimale. Or, quand l'est-elle ?
Merci d'avance.
18 août 2009 à 08:26
Avez vous un code en JAVA pour le problème d'affectation.
Cordialement
23 juin 2009 à 00:35
J'ai essayé d'exécuter le programme avec la matrice suivante :
10
4 9 90 8 65 7 18 3 42 19
4 8 5 76 5 2 15 4 7 15
54 8 4 9 9 9 2 8 9 65
6 1 3 1 2 7 12 9 44 17
65 98 5 4 11 8 13 17 32 9
16 15 10 25 30 7 12 18 32 18
87 56 6 76 25 11 9 14 22 19
9 10 16 17 75 16 8 11 9 4
61 18 11 23 45 34 7 12 20 18
90 81 23 6 7 4 8 10 4 7
ca cycle indéfiniment....vous connaissez la raison?
merci
28 mars 2009 à 11:49
21 mars 2009 à 15:47
svp je veut savoir pk votre pgm ne marche pas correctement quand j'ai mis une matrice carré :
1 2 3 4 5 6 7
A 1000 4 1 3 7 1000 2
B 1 6 4 3 1000 2 4
C 6 1 4 6 3 12 1000
D 10 1000 3 4 7 8 3
E 3 7 1000 2 16 3 8
F 14 9 4 1000 3 7 6
G 5 3 9 10 4 1000 3
2 févr. 2009 à 16:59
et dans le fichier affec.cpp écrire le nom de votre instance dans la ligne
#define data "instance.txt"//instance
19 janv. 2009 à 11:51
j'ai voulu voir ce que ça mais eu un problème en l'éxécutant en borland c++, il m'affiche toujours "erreur!!! impossible d\'ouvrir le fichier voulu", quand j'ai lu attentivement la code source j'ai réaliser qu'il y a un problème dans l'ouverture de fichier ftp, comment faire pour que ça marche?
merci :)
30 juil. 2008 à 11:01
30 juil. 2008 à 10:54
j'ai une matrice non carré de ce type:
10
2 12 10 16 4 18 8 18 18 12
6 36 30 48 12 54 24 54 54 36
l'algoritme ne fonctionne pas pourrai je connaitre la cause. il m'afficehe des valeur -842150451
-842150451 de ce types comment je pourrai le faire fonctionner.
merci
20 mai 2008 à 17:18
20 mai 2008 à 13:00
Désolé mais des il y a des caractères non reconnus par l'éditeur texte ce qui justifie les ? mal placés. Voilà donc le texte intégrale.
Etant donné n tâches à réaliser sur m machines et sachant que l'on connaît le coût de réalisation Cij de la tâche ti par la machine mj (pour tous les couples (ti,mj) possibles, si la tâche ti ne peut être effectuée par la machine mj, on pose Cij=infini), on cherche une permutation 's' de {1,2,.,n} conduisant à un coût total :
somme(Ci,s(i)) minimum. Ceci est obtenu en cherchant une solution à coût nul (un seul zéro dans chaque colonne et dans chaque ligne).
si on pose I=infini
La matrice ci-dessous illustre ce que je viens de dire :
1 2 3 4 5
A 7 3 5 7 10
B 6 I I 8 7
C 6 5 1 5 I
D 11 4 I 11 15
E I 4 5 2 10
La solution optimale est alors obtenue grâce aux éléments :
C2,A1= C2,B5= C2,C3= C2,D2= C2,E4=0
Si l'on revient aux données initials, on obtient:
CA1+ CB5+ CC3+ CD2+ CE4=7+7+1+4+2=21
Bon un problème d'affectation est un cas particulier du problème de transport sans capacité.
15 mai 2008 à 13:34
Merci.
15 mai 2008 à 12:46
somme(Ci,d(i)) minimum. Ceci est obtenu en cherchant une solution à coût nul (un seul zéro dans chaque colonne et dans chaque ligne).
La matrice ci-dessous illustre ce que je viens de dire :
1 2 3 4 5
A 7 3 5 7 10
B 6 8 8 8 7
C 6 5 1 5 8
D 11 4 8 11 15
E 8 4 5 2 10
La solution optimale est alors obtenue grâce aux éléments :
C2,A1= C2,B5= C2,C3= C2,D2= C2,E4=0
Si l’on revient aux données initials, on obtient:
CA1+ CB5+ CC3+ CD2+ CE4=7+7+1+4+2=21
14 mai 2008 à 16:10
Merci.
PS : La note que je met ne correspond à rien puisque je n'ai pas regardé les sources.
Un peu plus d'information sur l'algo (en anglais)