Algorithme hongrois proposé par kuhn

Soyez le premier à donner votre avis sur cette source.

Vue 16 885 fois - Téléchargée 1 952 fois

Description

Il s'agit de l'algorithme Hongrois proposé par Kuhn.
Il s'agit d'une matrice carré, là où les valeurs infinies restent inchangées.
L'algorithme procède en trois étapes successives.
1- éliminer le plus petit élément de chacune des colonnes puis celui de chacune des lignes de la matrice des coûts.
2- Si, cette solution n'est pas optimale, on considère la ligne ayant un nombre minimal de zéros. On encadre l'un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne ou la même colonne que le zéro encadré. On procède de même pour toutes les lignes.
3- On marque toutes les lignes qui ne contiennent aucun zéro encadré
On marque les lignes qui ont un zéro encadré dans une colonne marqué
On marque les colonnes qui ont un ou plusieurs zéros barrés dans une ligne marquée.
On répète ces trois marquages successifs jusqu'à ce que l'on ne puisse plus affecter de nouveaux marquages.
On barre ensuite, les lignes non marquées ainsi que les colonnes marquées.
Dans le tableau réduit obtenu, on retranche la valeur de l'élément le plus petit aux colonnes non barrées et on l'ajoute aux lignes barrées.
On poursuit la procédure de traitement sur la matrice résultante en reprenant à la seconde phase jusqu'à l'obtention d'une solution optimale.

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
1
Date d'inscription
vendredi 22 juillet 2016
Statut
Membre
Dernière intervention
22 juillet 2016

pour la compilation sous ubuntu avec g++, j'ai dû modifier le type void du main en int, et caster la variable data en char* lors de l'appel de la fonction lecture ligne 17 du fichier Affect.cpp


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
bonjour , il veut pas ce compiler :(
Messages postés
1
Date d'inscription
samedi 9 février 2013
Statut
Membre
Dernière intervention
16 février 2013

merci
Messages postés
1
Date d'inscription
lundi 17 mai 2010
Statut
Membre
Dernière intervention
17 mai 2010

Bonjour,
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.
Messages postés
2
Date d'inscription
samedi 29 septembre 2007
Statut
Membre
Dernière intervention
18 août 2009

Bonjour,
Avez vous un code en JAVA pour le problème d'affectation.
Cordialement
Afficher les 17 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.