En ciencias de la computación , el algoritmo Hopcroft-Karp (a veces llamado con mayor precisión el algoritmo Hopcroft-Karp-Karzanov ) [1] es un algoritmo que toma como entrada un gráfico bipartito y produce como salida una coincidencia máxima de cardinalidad - un conjunto de tantos bordes como sea posible con la propiedad de que no hay dos bordes que compartan un punto final. Corre entiempo en el peor de los casos , donde es un conjunto de aristas en el gráfico, es un conjunto de vértices del gráfico, y se supone que . En el caso de gráficos densos, el límite de tiempo se convierte en, y para gráficos aleatorios dispersos se ejecuta en el tiempocon alta probabilidad. [2]
Clase | Algoritmo gráfico |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | |
Complejidad espacial en el peor de los casos |
El algoritmo fue encontrado por John Hopcroft y Richard Karp ( 1973 ) e independientemente por Alexander Karzanov ( 1973 ). [3] Como en los métodos anteriores para emparejar, como el algoritmo húngaro y el trabajo de Edmonds (1965) , el algoritmo Hopcroft-Karp aumenta repetidamente el tamaño de un emparejamiento parcial al encontrar rutas de aumento . Estas rutas son secuencias de bordes del gráfico, que alternan entre bordes en la coincidencia y bordes fuera de la coincidencia parcial, y donde el borde inicial y final no están en la coincidencia parcial. Encontrar una ruta de aumento nos permite incrementar el tamaño de la coincidencia parcial, simplemente alternando los bordes de la ruta de aumento (poniendo en la coincidencia parcial los que no lo fueron, y viceversa). Los algoritmos más simples para la coincidencia bipartita, como el algoritmo Ford-Fulkerson , encuentran una ruta de aumento por iteración: el algoritmo de Hopkroft-Karp, en cambio, encuentra un conjunto máximo de rutas de aumento más cortas, para garantizar que se necesitan iteraciones en lugar de iteraciones. La misma actuación dese puede lograr para encontrar coincidencias de cardinalidad máxima en gráficos arbitrarios, con el algoritmo más complicado de Micali y Vazirani. [4]
El algoritmo Hopcroft-Karp puede verse como un caso especial del algoritmo de Dinic para el problema de flujo máximo . [5]
Aumento de caminos
Un vértice que no es el punto final de una arista en alguna coincidencia parcial se llama vértice libre . El concepto básico en el que se basa el algoritmo es el de una ruta de aumento , una ruta que comienza en un vértice libre, termina en un vértice libre y alterna entre bordes coincidentes y no coincidentes dentro de la ruta. De esta definición se deduce que, a excepción de los puntos finales, todos los demás vértices (si los hay) en la ruta de aumento deben ser vértices no libres. Una ruta de aumento podría constar de solo dos vértices (ambos libres) y un solo borde no coincidente entre ellos.
Si es una coincidencia, y es un camino de aumento relativo a , entonces la diferencia simétrica de los dos conjuntos de aristas,, formaría una coincidencia con el tamaño . Por lo tanto, al encontrar rutas de aumento, un algoritmo puede aumentar el tamaño de la coincidencia.
Por el contrario, suponga que una coincidencia no es óptimo, y deja ser la diferencia simétrica dónde es una combinación óptima. Porque y son coincidencias, cada vértice tiene un grado como máximo 2 en . Entonces debe formar una colección de ciclos disjuntos, de caminos con un número igual de bordes coincidentes y no coincidentes en , de aumentar caminos para , y de aumentar los caminos para ; pero esto último es imposible porquees óptimo. Ahora, los ciclos y las rutas con el mismo número de vértices coincidentes y no coincidentes no contribuyen a la diferencia de tamaño entre y , por lo que esta diferencia es igual al número de rutas de aumento para en . Por tanto, siempre que exista una coincidencia más grande que la coincidencia actual , también debe existir un camino de aumento. Si no se puede encontrar una ruta de aumento, un algoritmo puede terminar con seguridad, ya que en este caso debe ser óptimo.
Una ruta de aumento en un problema de coincidencia está estrechamente relacionada con las rutas de aumento que surgen en los problemas de flujo máximo , rutas a lo largo de las cuales se puede aumentar la cantidad de flujo entre las terminales del flujo. Es posible transformar el problema de emparejamiento bipartito en una instancia de flujo máximo, de modo que los caminos alternos del problema de emparejamiento se conviertan en caminos de aumento del problema de flujo. Basta insertar dos vértices, fuente y sumidero, e insertar bordes de capacidad unitaria desde la fuente a cada vértice en, y de cada vértice en al fregadero; y deja los bordes de a Tiene capacidad unitaria. [6] Una generalización de la técnica utilizada en el algoritmo Hopcroft-Karp para encontrar el flujo máximo en una red arbitraria se conoce como algoritmo de Dinic .
Algoritmo
El algoritmo puede expresarse en el siguiente pseudocódigo .
- Entrada : gráfico bipartito
- Salida : Coincidencia
- repetir
- conjunto máximo de rutas de aumento más cortas disjuntas de vértice
- Hasta que
Más detalladamente, dejemos y ser los dos conjuntos en la bipartición de y deja que la coincidencia de a en cualquier momento ser representado como el conjunto . El algoritmo se ejecuta en fases. Cada fase consta de los siguientes pasos.
- Una búsqueda de amplitud primero divide los vértices del gráfico en capas. Los vértices libres ense utilizan como vértices iniciales de esta búsqueda y forman la primera capa de la partición. En el primer nivel de la búsqueda, solo hay aristas que no coinciden, ya que los vértices libres enpor definición, no son adyacentes a ningún borde emparejado. En los niveles posteriores de la búsqueda, se requiere que los bordes atravesados alternen entre emparejados y no emparejados. Es decir, cuando se buscan sucesores desde un vértice en, solo se pueden atravesar los bordes no coincidentes, mientras que desde un vértice en sólo se pueden atravesar los bordes emparejados. La búsqueda termina en la primera capa. donde uno o más vértices libres en se alcanzan.
- Todos los vértices libres en en la capa se recogen en un conjunto . Es decir, un vértice se pone en si y solo si termina un camino de aumento más corto.
- El algoritmo encuentra un conjunto máximo de caminos de longitud de aumento disjuntos de vértices. ( Máximo significa que no se pueden agregar más caminos de este tipo. Esto es diferente de encontrar el número máximo de esos caminos, lo que sería más difícil de hacer. Afortunadamente, aquí es suficiente para encontrar un conjunto máximo de caminos). Este conjunto puede ser calculado por la primera búsqueda en profundidad (DFS) de a los vértices libres en , utilizando la primera capa de amplitud para guiar la búsqueda: el DFS solo puede seguir los bordes que conducen a un vértice no utilizado en la capa anterior, y las rutas en el árbol DFS deben alternar entre los bordes coincidentes y no coincidentes. Una vez que se encuentra una ruta de aumento que involucra uno de los vértices en, la DFS continúa desde el siguiente vértice inicial. Cualquier vértice encontrado durante el DFS se puede marcar inmediatamente como usado, ya que si no hay una ruta desde en el punto actual en el DFS, entonces ese vértice no se puede utilizar para alcanzar en cualquier otro punto del DFS. Esto aseguratiempo de ejecución para el DFS. También es posible trabajar en la otra dirección, desde vértices libres en a aquellos en , que es la variante utilizada en el pseudocódigo.
- Cada uno de los caminos que se encuentran de esta manera se utiliza para ampliar .
El algoritmo termina cuando no se encuentran más rutas de aumento en la primera parte de búsqueda de amplitud de una de las fases.
Análisis
Cada fase consta de una primera búsqueda de amplitud única y una primera búsqueda de profundidad única. Por lo tanto, se puede implementar una sola fase enhora. Por tanto, la primera fases, en un gráfico con vértices y bordes, tómate tu tiempo .
Cada fase aumenta la longitud de la ruta de aumento más corta en al menos uno: la fase encuentra un conjunto máximo de rutas de aumento de la longitud dada, por lo que cualquier ruta de aumento restante debe ser más larga. Por lo tanto, una vez que la inicial fases del algoritmo están completas, la ruta de aumento restante más corta tiene al menos bordes en ella. Sin embargo, la diferencia simétrica del emparejamiento óptimo eventual y del emparejamiento parcial M encontrado por las fases iniciales forma una colección de caminos de aumento disjuntos de vértice y ciclos alternos. Si cada uno de los caminos de esta colección tiene una longitud de al menos, puede haber como máximo rutas en la colección, y el tamaño de la coincidencia óptima puede diferir del tamaño de por como máximo bordes. Dado que cada fase del algoritmo aumenta el tamaño de la coincidencia en al menos uno, puede haber como máximo fases adicionales antes de que termine el algoritmo.
Dado que el algoritmo realiza un total de como máximo fases, se necesita un tiempo total de En el peor de los casos.
En muchos casos, sin embargo, el tiempo que tarda el algoritmo puede ser incluso más rápido de lo que indica este análisis del peor de los casos. Por ejemplo, en el caso promedio de gráficos aleatorios bipartitos dispersos , Bast et al. (2006) (mejorando un resultado anterior de Motwani 1994 ) mostró que, con alta probabilidad, todos los emparejamientos no óptimos tienen trayectorias crecientes de longitud logarítmica . Como consecuencia, para estos gráficos, el algoritmo Hopcroft-Karp toma fases y Tiempo Total.
Comparación con otros algoritmos de emparejamiento bipartito
Para gráficos dispersos , el algoritmo Hopcroft-Karp sigue teniendo el mejor rendimiento conocido en el peor de los casos, pero para gráficos densos () un algoritmo más reciente de Alt et al. (1991) logra un plazo un poco mejor,. Su algoritmo se basa en el uso de un algoritmo de flujo máximo de re-etiquetado push y luego, cuando el emparejamiento creado por este algoritmo se acerca al óptimo, se cambia al método Hopcroft-Karp.
Varios autores han realizado comparaciones experimentales de algoritmos de emparejamiento bipartito. Sus resultados en general tienden a mostrar que el método Hopcroft-Karp no es tan bueno en la práctica como lo es en teoría: es superado tanto por estrategias más simples de amplitud primero y profundidad primero para encontrar caminos de aumento, como por técnicas de empujar y volver a etiquetar. . [7]
Gráficos no bipartitos
La misma idea de encontrar un conjunto máximo de rutas de aumento más cortas funciona también para encontrar coincidencias de cardinalidad máxima en gráficos no bipartitos, y por las mismas razones los algoritmos basados en esta idea toman etapas. Sin embargo, para los gráficos no bipartitos, la tarea de encontrar las rutas de aumento dentro de cada fase es más difícil. Basándose en el trabajo de varios predecesores más lentos, Micali y Vazirani (1980) mostraron cómo implementar una fase en tiempo lineal, lo que resultó en un algoritmo de coincidencia no bipartito con el mismo límite de tiempo que el algoritmo Hopcroft-Karp para gráficos bipartitos. La técnica de Micali-Vazirani es compleja y sus autores no proporcionaron pruebas completas de sus resultados; Posteriormente, Peterson y Loui (1988) publicaron una "exposición clara" error de harvtxt: objetivos múltiples (2 ×): CITEREFPetersonLoui1988 ( ayuda ) y otros autores describieron métodos alternativos. [8] En 2012, Vazirani ofreció una nueva prueba simplificada del algoritmo Micali-Vazirani. [9]
Pseudocódigo
/ * G = U ∪ V ∪ {NIL} donde U y V son los lados izquierdo y derecho del gráfico bipartito y NIL es un vértice nulo especial* / la función BFS () es para cada u en U hacer si Pair_U [u] = NIL entonces Dist [u]: = 0 Poner en cola (Q, u) demás Dist [u]: = ∞ Dist [NIL]: = ∞ while Empty (Q) = falso hacer u: = Retirar de cola (Q) si Dist [u]entonces para cada v en Adj [u] hacer si Dist [Pair_V [v]] = ∞ entonces Dist [Pair_V [v]]: = Dist [u] + 1 Poner en cola (Q, Pair_V [v]) return Dist [NIL] ≠ ∞la función DFS (u) es si u ≠ NIL entonces para cada v en Adj [u] hacer si Dist [Pair_V [v]] = Dist [u] + 1 entonces si DFS (Pair_V [v]) = verdadero entonces Pair_V [v]: = u Par_U [u]: = v volver verdadero Dist [u]: = ∞ devuelve falso devuelve verdaderofunción Hopcroft – Karp es para cada u en U do Pair_U [u]: = NIL para cada v en V hacer Pair_V [v]: = NIL coincidencia: = 0 while BFS () = verdadero hacer para cada u en U hacer si Pair_U [u] = NIL entonces si DFS (u) = verdadero entonces coincidencia: = coincidencia + 1 retorno coincidente
Explicación
Dejemos que los vértices de nuestro gráfico se dividan en U y V, y consideremos una coincidencia parcial, como lo indican las tablas Pair_U y Pair_V que contienen el vértice con el que se empareja cada vértice de U y de V, o NIL para los vértices no emparejados. La idea clave es agregar dos vértices ficticios a cada lado del gráfico: uDummy conectado a todos los vértices no coincidentes en U y vDummy conectado a todos los vértices no coincidentes en V. Ahora, si ejecutamos una búsqueda de amplitud primero (BFS) de uDummy a vDummy, entonces podemos obtener las rutas de longitud mínima que conectan los vértices actualmente no coincidentes en U con los vértices actualmente no coincidentes en V. Tenga en cuenta que, como el gráfico es bipartito, estas rutas siempre alternan entre vértices en U y vértices en V, y requerimos en nuestro BFS que al pasar de V a U, siempre seleccionamos un borde coincidente. Si llegamos a un vértice incomparable de V, terminamos en vDummy y termina la búsqueda de rutas en el BFS. Para resumir, el BFS comienza en vértices no coincidentes en U, va a todos sus vecinos en V, si todos coinciden, vuelve a los vértices en U con los que coinciden todos estos vértices (y que no se visitaron antes), luego se dirige a todos los vecinos de estos vértices, etc., hasta que uno de los vértices alcanzados en V es incomparable.
Observe en particular que BFS marca los nodos no coincidentes de U con distancia 0, luego incrementa la distancia cada vez que regresa a U. Esto garantiza que las rutas consideradas en el BFS son de longitud mínima para conectar vértices no coincidentes de U a vértices no coincidentes de V mientras siempre regresa de V a U en los bordes que actualmente forman parte de la coincidencia. En particular, al vértice especial NIL, que corresponde a vDummy, se le asigna una distancia finita, por lo que la función BFS devuelve verdadero si se ha encontrado alguna ruta. Si no se ha encontrado ninguna ruta, entonces no quedan rutas de aumento y la coincidencia es máxima.
Si BFS devuelve verdadero, entonces podemos continuar y actualizar el emparejamiento de vértices en las rutas de longitud mínima encontradas de U a V: lo hacemos usando una búsqueda en profundidad (DFS). Tenga en cuenta que cada vértice en V en dicha ruta, excepto el último, está actualmente emparejado. Entonces podemos explorar con el DFS, asegurándonos de que los caminos que seguimos corresponden a las distancias calculadas en el BFS. Actualizamos a lo largo de cada una de esas rutas eliminando de la coincidencia todos los bordes de la ruta que se encuentran actualmente en la coincidencia, y agregando a la coincidencia todos los bordes de la ruta que actualmente no están en la coincidencia: ya que esta es una ruta de aumento (la primera y los últimos bordes de la ruta no eran parte de la coincidencia, y la ruta alternaba entre bordes coincidentes y no coincidentes), entonces esto aumenta el número de bordes en la coincidencia. Esto es lo mismo que reemplazar la coincidencia actual por la diferencia simétrica entre la coincidencia actual y la ruta completa.
Tenga en cuenta que el código garantiza que todas las rutas de aumento que consideramos son vértices disjuntos. De hecho, después de hacer la diferencia simétrica para una ruta, ninguno de sus vértices podría considerarse nuevamente en el DFS, solo porque Dist [Pair_V [v]] no será igual a Dist [u] + 1 (sería exactamente Dist [u]).
También observe que el DFS no visita el mismo vértice varias veces. Esto es gracias a las siguientes líneas:
Dist [u] = ∞falso retorno
Cuando no pudimos encontrar ninguna ruta de aumento más corta desde un vértice u, entonces el DFS marca el vértice u estableciendo Dist [u] en infinito, de modo que estos vértices no se visiten nuevamente.
Una última observación es que en realidad no necesitamos uDummy: su función es simplemente poner todos los vértices no coincidentes de U en la cola cuando iniciamos el BFS. En cuanto a vDummy, se indica como NIL en el pseudocódigo anterior.
Ver también
- Coincidencia máxima de cardinalidad , el problema resuelto por el algoritmo y su generalización a grafos no bipartitos
- Problema de asignación , una generalización de este problema en gráficos ponderados , resuelto, por ejemplo, mediante el algoritmo húngaro.
- Algoritmo de Edmonds-Karp para encontrar el flujo máximo, una generalización del algoritmo de Hopcroft-Karp
Notas
- ^ Gabow (2017) ; Annamalai (2018)
- ^ Bast y col. (2006) .
- ^ Dinitz (2006) .
- ^ Peterson, Paul A .; Loui, Michael C. (1 de noviembre de 1988). "El algoritmo de coincidencia máxima general de Micali y Vazirani". Algoritmica . 3 (1): 511–533. doi : 10.1007 / BF01762129 . ISSN 1432-0541 . S2CID 16820 .
- ^ Tarjan, Robert Endre (1 de enero de 1983). Estructuras de datos y algoritmos de red . Serie de conferencias regionales de CBMS-NSF sobre matemáticas aplicadas. Sociedad de Matemáticas Industriales y Aplicadas. doi : 10.1137 / 1.9781611970265 . ISBN 978-0-89871-187-5., p102
- ^ Ahuja, Magnanti y Orlin (1993) , sección 12.3, problema de coincidencia de cardinalidad bipartita, págs. 469–470.
- ^ Chang y McCormick (1990) ; Darby-Dowman (1980) ; Setubal (1993) ; Setubal (1996) .
- ^ Gabow y Tarjan (1991) .
- ↑ Vazirani (2012)
Referencias
- Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993), Flujos de red: teoría, algoritmos y aplicaciones , Prentice-Hall.
- Alt, H .; Blum, N .; Mehlhorn, K .; Paul, M. (1991), "Calcular una coincidencia máxima de cardinalidad en un gráfico bipartito en el tiempo", Cartas de procesamiento de información , 37 (4): 237–240, doi : 10.1016 / 0020-0190 (91) 90195-N.
- Annamalai, Chidambaram (2018), "Finding perfect matchings in bipartite hypergraphs", Combinatorica , 38 (6): 1285-1307, arXiv : 1509.07007 , doi : 10.1007 / s00493-017-3567-2 , MR 3910876 , S2CID 1997334
- Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Los algoritmos de emparejamiento son rápidos en gráficos aleatorios dispersos", Teoría de los sistemas informáticos , 39 (1): 3-14, doi : 10.1007 / s00224-005-1254-y , MR 2189556
- Chang, S. Frank; McCormick, S. Thomas (1990), Una implementación más rápida de un algoritmo de coincidencia de cardinalidad bipartita , Tech. Rep. 90-MSC-005, Facultad de Comercio y Administración de Empresas, Univ. de la Columbia Británica. Como lo cita Setubal (1996) .
- Darby-Dowman, Kenneth (1980), La explotación de la escasez en problemas de programación lineal a gran escala - Estructuras de datos y algoritmos de reestructuración , Ph.D. tesis, Universidad de Brunel. Como lo cita Setubal (1996) .
- Dinitz, Yefim (2006), "Algoritmo de Dinitz: la versión original y la versión de Even", en Goldreich, Oded ; Rosenberg, Arnold L .; Selman, Alan L. (eds.), Theoretical Computer Science: Essays in Memory of Shimon Even , Lecture Notes in Computer Science, 3895 , Berlín y Heidelberg: Springer, págs. 218-240, doi : 10.1007 / 11685654_10.
- Edmonds, Jack (1965), "Senderos, árboles y flores", Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153 / CJM-1965-045-4 , MR 0177907.
- Gabow, Harold N. (2017), "El enfoque de emparejamiento ponderado para el emparejamiento de cardinalidad máxima", Fundamenta Informaticae , 154 (1–4): 109–130, arXiv : 1703.03998 , doi : 10.3233 / FI-2017-1555 , MR 3690573 , S2CID 386509
- Gabow, Harold N .; Tarjan, Robert E. (1991), "Algoritmos de escala más rápidos para problemas generales de coincidencia de gráficos", Journal of the ACM , 38 (4): 815–853, doi : 10.1145 / 115234.115366 , S2CID 18350108.
- Hopcroft, John E .; Karp, Richard M. (1973), "Un algoritmo n 5/2 para coincidencias máximas en gráficos bipartitos", SIAM Journal on Computing , 2 (4): 225-231, doi : 10.1137 / 0202019. Anunciado previamente en el 12 ° Simposio Anual sobre Teoría de la Conmutación y Autómatas, 1971.
- Karzanov, AV (1973), "Una estimación exacta de un algoritmo para encontrar un flujo máximo, aplicado al problema de los representantes", Problemas en cibernética , 5 : 66-70. Anunciado previamente en el Seminario de Matemática Combinatoria (Moscú, 1971).
- Micali, S .; Vazirani, VV (1980), "Analgoritmo para encontrar la máxima coincidencia en gráficos generales ", Proc. 21st IEEE Symp. Foundations of Computer Science , págs. 17–27, doi : 10.1109 / SFCS.1980.12 , S2CID 27467816.
- Peterson, Paul A .; Loui, Michael C. (1988), "El algoritmo de coincidencia máxima general de Micali y Vazirani", Algorithmica , 3 (1–4): 511–533, CiteSeerX 10.1.1.228.9625 , doi : 10.1007 / BF01762129 , S2CID 16820.
- Motwani, Rajeev (1994), "Análisis de casos promedio de algoritmos para emparejamientos y problemas relacionados", Journal of the ACM , 41 (6): 1329-1356, doi : 10.1145 / 195613.195663 , S2CID 2968208.
- Setubal, João C. (1993), "Nuevos resultados experimentales para el emparejamiento bipartito", Proc. Netflow93 , Departamento de Informática, Univ. de Pisa, págs. 211-216. Como lo cita Setubal (1996) .
- Setubal, João C. (1996), Resultados experimentales secuenciales y paralelos con algoritmos de emparejamiento bipartito , Tech. Rep. IC-96-09, Inst. de Computación, Univ. de Campinas, CiteSeerX 10.1.1.48.3539.
- Vazirani, Vijay (2012), Una definición mejorada de flores y una prueba más simple del algoritmo de coincidencia de MV , CoRR abs / 1210.4594, arXiv : 1210.4594 , Bibcode : 2012arXiv1210.4594V.