L'algorithme hongrois est un algorithme d'optimisation combinatoire qui résout le problème d'appariement bipartite de poids maximum en temps polynomial et a anticipé le développement ultérieur de l'importante méthode primal-dual . L'algorithme a été développé et publié par Harold Kuhn en 1955, qui a donné le nom "algorithme hongrois" parce que l'algorithme était basé sur les travaux antérieurs de deux mathématiciens hongrois: Dénes Kőnig et Jenő Egerváry. Munkres a passé en revue l'algorithme en 1957 et a observé qu'il s'agit bien de la polytime. Depuis lors, l'algorithme est également connu sous le nom d'algorithme de Kuhn-Munkres.
Bien que le hongrois contienne l'idée de base de la méthode primal-dual, il résout directement le problème de correspondance bipartite de poids maximum sans utiliser de machinerie de programmation linéaire (LP). Ainsi, en réponse à la question suivante , Jukka Suomela a commenté
Bien sûr, vous pouvez résoudre n'importe quel LP en utilisant un solveur LP à usage général, mais les algorithmes spécialisés ont généralement de bien meilleures performances. [...] Vous pouvez également souvent éviter des problèmes comme l'utilisation de nombres rationnels exacts par rapport à des nombres à virgule flottante; tout peut être fait facilement avec des entiers.
En d'autres termes, vous n'avez pas à vous soucier de l'arrondi d'une solution rationnelle / virgule flottante du solveur LP pour obtenir une correspondance parfaite de poids maximum d'un graphe biparti donné.
Ma question est la suivante:
Y a-t-il une généralisation de l'algorithme hongrois qui fonctionne pour le graphe général non orienté sans l'utilisation de machines LP de manière similaire à l'esprit de l'algorithme hongrois d'origine?
Je préférerais une exposition moderne et facile à lire plutôt qu'un papier original compliqué. Mais tout pointeur sera très apprécié!
Merci d'avance et joyeux Noël !!!
Mise à jour: Arman répond joliment à la question ci-dessous. Je veux juste souligner qu'une autre belle source pour étudier l'algorithme de la fleur d'Edmonds (pour le cas pondéré) est le chapitre 11 de l' optimisation combinatoire de Korte et Vygen . Le livre Google montre en fait presque toutes les parties dont j'ai besoin pour comprendre l'algorithme.
Réponses:
L'algorithme de correspondance d'Edmonds (également appelé algorithme Blossom) résout la correspondance maximale sur les graphiques généraux. Il s'agit en fait d'une méthode de généralisation des chemins alternés. (Je ne suis pas sûr du nom de la méthode mais qui devraient être la méthode König-Hall.) Il trouve essentiellement des chemins augmenter (voir wikipedia page: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ) pour étendre la correspondance actuelle et s'arrête s'il n'y a plus de chemins d'augmentation. Dans les graphiques généraux, le seul problème se produit dans les cycles impairs. Dans l'algorithme d'appariement d'Edmonds, les cycles impairs sont contractés (fleurs) et dépensés pour avoir une solution.
Il existe également une correspondance entre l'algorithme Blossom et la méthode Primal Dual. Les cycles impairs provoquent des points extrêmes fractionnaires. Par conséquent, nous ajoutons des inégalités dites de fleur pour chaque cycle impair.
Des problèmes d'appariement parfait pondéré minimum et d'appariement de poids maximum pourraient également être traités avec cette approche.
Pour plus de détails sur l'algorithme, voir http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
Pour la formulation mathématique et la méthode primale-dual correspondante, voir http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf
la source
Il y a deux ans, en recherchant l'algorithme de floraison (non pondéré), j'ai trouvé deux grands ensembles de notes, l'un par Tarjan et l'autre par Zwick. Ils ont rendu le cas non pondéré assez simple et j'ai pu l'implémenter dans Mathematica en utilisant la récursivité. Cela fonctionne plutôt bien.
Les notes que j’ai trouvées utiles sont
http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf et http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf
Ils distillent tout cela en termes très simples qui permettent de penser de manière récursive puis, comme indiqué, de programmer récursivement.
Je pense que tout devrait fonctionner dans le cas pondéré, que j'essaie de mettre en œuvre maintenant.
la source