El algoritmo húngaro es un algoritmo de optimización combinatoria que resuelve el problema de coincidencia bipartita de peso máximo en tiempo polinómico y anticipa el desarrollo posterior del importante método primal-dual . El algoritmo fue desarrollado y publicado por Harold Kuhn en 1955, quien dio el nombre de "algoritmo húngaro" porque el algoritmo se basó en los trabajos anteriores de dos matemáticos húngaros: Dénes Kőnig y Jenő Egerváry. Munkres revisó el algoritmo en 1957 y observó que, de hecho, es polytime. Desde entonces, el algoritmo también se conoce como algoritmo Kuhn-Munkres.
Aunque el húngaro contiene la idea básica del método primal-dual, resuelve el problema de coincidencia bipartita de peso máximo directamente sin utilizar ninguna maquinaria de programación lineal (LP). Por lo tanto, en respuesta a la siguiente pregunta , Jukka Suomela comentó
Por supuesto, puede resolver cualquier LP utilizando un solucionador de LP de uso general, pero los algoritmos especializados generalmente tienen un rendimiento mucho mejor. [...] También puede evitar problemas como el uso de números racionales exactos versus números de coma flotante; todo se puede hacer fácilmente con enteros.
En otras palabras, no tiene que preocuparse sobre cómo redondear una solución de punto racional / flotante del solucionador de LP para recuperar una coincidencia perfecta de peso máximo de un gráfico bipartito dado.
Mi pregunta es la siguiente:
¿Existe una generalización del algoritmo húngaro que funcione para un gráfico general no dirigido sin el uso de maquinaria LP similar al espíritu del algoritmo húngaro original?
Preferiría una exposición moderna y fácil de leer en lugar de un papel complicado original. ¡Pero cualquier puntero será muy apreciado!
Muchas gracias de antemano y Feliz Navidad !!!
Actualización: Arman responde muy bien la pregunta a continuación. Solo quiero señalar que otra buena fuente para estudiar el Algoritmo de la Flor de Edmonds (para el caso ponderado) es el Capítulo 11 de Optimización combinatoria de Korte y Vygen . El libro de Google en realidad muestra casi todas las partes que necesito para comprender el algoritmo.
Respuestas:
El algoritmo de coincidencia de Edmonds (también llamado Algoritmo de flor) resuelve la coincidencia máxima en gráficos generales. En realidad es una generalización del método de caminos alternos. (No estoy seguro del nombre del método, pero debería ser el método König-Hall). Básicamente, encuentra rutas de aumento (consulte la página de wikipedia: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm ) para extender el coincidencia actual y se detiene si no hay más rutas de aumento. En gráficos generales, el único problema ocurre en ciclos impares. En el algoritmo de coincidencia de Edmonds, los ciclos impares se contraen (florecen) y se gastan de nuevo para tener una solución.
También existe una correspondencia entre el Algoritmo de Flor y el método Primal Dual. Los ciclos impares causan puntos extremos fraccionarios. Por lo tanto, agregamos las llamadas desigualdades en flor para cada ciclo impar.
Con este enfoque también se podrían manejar los problemas de coincidencia perfecta ponderada mínima y de coincidencia de peso máximo.
Para obtener detalles del algoritmo, consulte http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf
Para la formulación matemática y el método primal-dual correspondiente, consulte http://webdocs.cs.ualberta.ca/~mreza/courses/CombOpt09/lecture4.pdf
fuente
Hace dos años, cuando investigaba el algoritmo de floración (no ponderado), encontré dos excelentes conjuntos de notas, una de Tarjan y otra de Zwick. Hicieron que el caso no ponderado pareciera bastante sencillo y pude implementarlo en Mathematica usando la recursividad. Funciona bastante bien
Las notas que encontré útiles son
http://www.cs.tau.ac.il/~zwick/grad-algo-06/match.pdf y http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/ tarjan-blossom.pdf
Lo resumen todo en términos muy simples que le permiten a uno pensar recursivamente y luego, como se señaló, programar recursivamente.
Creo que todo debería funcionar en el caso ponderado, que estoy tratando de implementar ahora.
fuente