Algoritmo de Hopcroft-Karp

Algoritmo de Hopcroft-Karp
Lleva el nombre de	John Hopcroft y Richard Manning Karp
Autor	John Hopcroft , Richard Manning Karp y Alexander V. Karzanov [d]
objetivo	Encontrar la coincidencia máxima
Estructura de datos	Grafico
peor momento	$O(E{\sqrt {V)))$
costo de memoria	${\ estilo de visualización O (V)}$

El algoritmo de Hopcroft-Karp es un algoritmo que toma como entrada un gráfico bipartito y devuelve la coincidencia máxima de cardinalidad , es decir, el mayor conjunto de aristas tal que no hay dos que tengan un vértice común. La asintótica del tiempo de ejecución del algoritmo es en el peor de los casos (aquí está el conjunto de aristas del gráfico, y es el conjunto de sus vértices). En el caso de gráficos densos , el tiempo de ejecución se limita a , y para un gráfico aleatorio , el algoritmo se ejecuta en un tiempo casi lineal. $O(|E|{\sqrt {|V|)))$ $mi$ $V$ ${\ estilo de visualización O (| V | ^ {2.5})}$

El algoritmo fue creado por John Hopcroft y Richard Karp en 1973 [1] . Al igual que los algoritmos creados previamente (como el algoritmo húngaro y el algoritmo del trabajo de Edmonds [2] , el algoritmo de Hopcroft-Karp en un ciclo aumenta la coincidencia encontrando caminos crecientes ( cadenas , cuyos bordes pertenecen alternativamente a la coincidencia y no pertenecen a él, y el primer y último vértice no pertenecen al emparejamiento; al alternar el emparejamiento a lo largo de la cadena, es decir, quitando del emparejamiento los bordes que estaban en la cadena y agregando los que no estaban en ella, puede obtener una coincidencia más grande). En lugar de encontrar una ruta de aumento, el algoritmo encuentra el conjunto máximo de aumentos más cortos. La misma idea se usa en algoritmos más complejos para encontrar coincidencias en gráficos no bipartitos con el mismo tiempo de ejecución asintótica que Hopcroft -Karp. algoritmo. ${\ estilo de visualización O ({\ sqrt {| V |}})}$

Descripción de la tarea

El problema de encontrar la coincidencia más grande en un gráfico bipartito se puede describir informalmente de la siguiente manera. Hay un grupo de niños y niñas. Algunos chicos conocen a algunas chicas. Se requiere formar tantas parejas para el baile como sea posible, compuestas por un chico y una chica que se conozcan [3] .

Rutas de aumento

Un vértice que no es el final de ningún borde de una coincidencia se denomina vértice libre (para esa coincidencia). El algoritmo se basa en el concepto de una ruta de aumento : una ruta que comienza y termina en un vértice libre, y dentro de la ruta, los bordes que pertenecen y no pertenecen a una alternativa coincidente. De la definición se sigue que todos los vértices de tal camino, excepto el primero y el último, deben ser no libres. Un camino de aumento puede constar de dos vértices libres y una arista entre ellos (que no está en el emparejamiento). $METRO$ $METRO$

Si es una coincidencia y es un camino de aumento en , entonces la diferencia simétrica de dos conjuntos de aristas es una coincidencia de tamaño . Por lo tanto, al encontrar rutas de aumento, podemos aumentar el tamaño de la coincidencia. $METRO$ $PAGS$ $METRO$ $M\oplus P$ ${\ estilo de visualización | M | +1}$

Por el contrario, que no sea óptimo y que sea una diferencia simétrica , donde hay un emparejamiento óptimo. Como y son coincidencias, cada vértice en tiene grado a lo sumo dos. Esto significa que debe formar un conjunto de caminos y ciclos de aumento que no se cortan o caminos en los que hay tantas aristas del emparejamiento como no las hay. La diferencia de tamaño y es el número de rutas de aumento en . Entonces, si hay una coincidencia mayor que la coincidencia actual , también debe haber una ruta de aumento. Si no existe una ruta de aumento, el algoritmo se puede abortar con éxito, ya que debería ser óptimo [4] . $METRO$ $PAGS$ $M\oplus M^{*}$ $M^*$ $METRO$ $M^*$ $PAGS$ $PAGS$ $METRO$ $M^*$ $PAGS$ $M^*$ $METRO$ $METRO$

Las rutas de aumento en los problemas de coincidencia están estrechamente relacionadas con las rutas de aumento en los problemas de flujo máximo , rutas a lo largo de las cuales se puede aumentar el flujo entre la fuente y el sumidero. Puede reducir el problema de encontrar la coincidencia más grande al problema de encontrar el flujo máximo [5] . La técnica utilizada en el algoritmo de Hopcroft-Karp se puede generalizar a una red de transporte arbitraria , lo que lleva al algoritmo de Dinitz [6] .

Algoritmo

A continuación se muestra la estructura del algoritmo:

Entrada : gráfico bipartito

G(U\taza V,E)

Salida : Coincidencia

M\subseteq E

M\leftarrow\emptyset

ciclo

{\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots,P_{k}\}

conjunto máximo de rutas de aumento más cortas disjuntas de vértice

M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})

adiós

{\mathcal {P}}\neq\emptyset

Con más detalle, sean y los conjuntos de vértices del grafo bipartito , y el conjunto de sus aristas que conectan los vértices de y . El algoritmo, a partir de una coincidencia vacía , la incrementa secuencialmente. En cada fase, el algoritmo hace lo siguiente: $tu$ $V$ $GRAMO$ $mi$ $tu$ $V$ $METRO$

Breadth First Search (BFS) divide los vértices de un gráfico en capas. BFS comienza con un conjunto de vértices libres , que forman la primera capa de la partición (por lo tanto, la primera capa contiene solo bordes no coincidentes). En los niveles subsiguientes de la búsqueda, el algoritmo agrega vértices a un nuevo nivel, alternando aristas: alternativamente agregará vértices conectados por una arista ya sea en la coincidencia o fuera de ella, por lo que en el proceso de búsqueda desde un vértice siempre iremos a través de los bordes no de una coincidencia, pero si un vértice de - al revés. La búsqueda se interrumpe en el nivel en cuanto se alcanza por primera vez al menos un vértice libre de . $tu$ $tu$ $V$ $k$ $V$
Todos los vértices libres de esta capa se denotarán como . Resulta que un vértice pertenece si y solo si el camino de alargamiento más corto termina en él. $V$ $k$ $F$ $v$ $F$
El algoritmo encuentra el conjunto máximo de caminos separados por vértices de longitud . Este conjunto se puede encontrar mediante la búsqueda en profundidad (DFS), que utiliza las capas encontradas anteriormente. La búsqueda solo puede ir a lo largo de los bordes que conducen a los vértices no utilizados de la capa anterior, y la ruta en el árbol de búsqueda en profundidad debe alternar con respecto a la coincidencia . Tan pronto como la ruta de aumento ingresa a uno de los vértices , el DFS debe comenzar desde el siguiente vértice. $k$ $METRO$ $F$
Cada una de las rutas encontradas se utiliza para incrementar . $METRO$

El algoritmo se interrumpe cuando BFS no encuentra ninguna ruta de aumento en ninguna fase (es decir, está vacío). $F$

Análisis

Cada fase consta de un BFS y un DFS, por lo que una fase se ejecuta en . Por tanto, las primeras fases en un grafo con vértices y aristas tienen un coste . Se puede demostrar que cada fase aumenta la longitud del camino de alargamiento más corto en al menos 1: la fase encuentra el conjunto máximo de caminos complementarios de una longitud dada, por lo que cualquier camino restante debe ser más largo. Por lo tanto, después de que se hayan completado las primeras fases del algoritmo, la ruta de aumento restante más corta tiene una longitud de al menos . Sin embargo, la diferencia simétrica entre la coincidencia óptima y la coincidencia actual encontrada en fases anteriores forma un conjunto de caminos de aumento disjuntos de vértice y ciclos alternos. Si cada ruta tiene una longitud de al menos , puede haber como máximo rutas, y el tamaño de una coincidencia óptima puede diferir del tamaño en como máximo . Dado que cada fase del algoritmo aumenta el tamaño de la coincidencia en al menos 1, no pueden ocurrir más fases. $O(|E|)$ ${\sqrt {|V|}}$ $|V|$ $|E|$ $O(|E|{\sqrt {|V|)))$ ${\sqrt {|V|}}$ ${\sqrt {|V|}}$ $METRO$ ${\sqrt {|V|}}$ ${\sqrt {|V|}}$ $METRO$ ${\sqrt {|V|}}$ ${\sqrt {|V|}}$

Dado que el algoritmo tiene fases en el peor de los casos, el tiempo de ejecución total es en el peor de los casos [1] . $2{\sqrt {|V|}}$ $O(|E|{\sqrt {|V|)))$

Sin embargo, en muchos casos, el algoritmo puede ser mucho más rápido de lo que dice la estimación del peor de los casos. Por ejemplo, en el caso de un grafo aleatorio bipartito disperso , se demostró en 2006 [7] (mejorando el resultado anterior [8] ) que, con una alta probabilidad, todos los emparejamientos no óptimos tienen caminos crecientes de longitud logarítmica . Como consecuencia, para dichos gráficos, el número de iteraciones y el tiempo de ejecución del algoritmo es . $O(\log |V|)$ $O(|E|\log |V|)$

Comparación con otros algoritmos para encontrar la coincidencia máxima

Para gráficos dispersos, el algoritmo Hopcroft-Karp tiene el mejor comportamiento asintótico en el peor de los casos de todos los algoritmos conocidos, pero para gráficos densos, el algoritmo más nuevo [9] tiene un límite ligeramente mejor . Este algoritmo se basa en el algoritmo de empuje de preflujo y, cuando la coincidencia se vuelve casi óptima, cambia al método Hopcroft-Karp. $O\left(n^{1.5}{\sqrt {\frac {m}{\log n))}\right)$

Varios autores han llevado a cabo una comparación experimental de algoritmos para encontrar la coincidencia máxima. Sus resultados mostraron que, en general, el algoritmo de Hopcroft-Karp no es tan bueno en la práctica como en la teoría: es superado por estrategias BFS y DFS simples para encontrar una ruta de aumento y algoritmos basados en el método de empuje de preflujo [10] .

Grafos no bipartitos

La misma idea de encontrar el conjunto máximo de rutas de aumento más cortas también funciona para encontrar coincidencias de cardinalidad máxima en gráficos no bipartitos, y por las mismas razones que el algoritmo tendrá en la mayoría de las fases. Sin embargo, para gráficos no bipartitos, es más difícil encontrar caminos de alargamiento en cada fase. Sobre la base de trabajos anteriores, Micali y Vazirani (1980 ) mostraron cómo ejecutar la fase en tiempo lineal, lo que resultó en un algoritmo con el mismo límite superior que el algoritmo Hopcroft-Karp para gráficos bipartitos. El método de Micali-Vazirani es complejo y los autores no proporcionaron pruebas completas de sus resultados; más tarde , Peterson y Loui (1988 ) publicaron una justificación completa del algoritmo de Micali-Vazirani, y también se han publicado otros algoritmos: Gabow y Tarjan (1991 ) y Blum (2001 ). En 2012, Vazirani propuso una prueba nueva y simplificada del algoritmo de Micali: Vazirani [11] . ${\ estilo de visualización O ({\ sqrt {| V |}})}$

Pseudocódigo

A continuación se muestra el pseudocódigo del algoritmo, cercano a la implementación en Java [12] .

/* GRAMO = U ∪ V ∪ {NIL} donde U y V son la partición del gráfico y NIL es un vértice nulo especial */ función BFS() para ti en ti si Par_U[u] == NIL Dist[u] = 0 En cola (Q, u) más Dist[u] = ∞ Dist[NIL] = ∞ while Vacío(Q) == falso u = Desencolar(Q) si Dist[u] < Dist[NIL] para cada v en Adj[u] si Dist[ Par_V[v] ] == ∞ Dist[ Par_V[v] ] = Dist[u] + 1 Poner en cola(Q,Pair_V[v]) devuelve Dist[NIL] != ∞ función DFS(u) si tu != NIL para cada v en Adj[u] si Dist[ Pair_V[v] ] == Dist[u] + 1 si DFS (Par_V [v]) == verdadero Par_V[v] = u Par_U[u] = v volver verdadero Dist[u] = ∞ falso retorno volver verdadero función Hopcroft-Karp por cada tu en ti Par_U[u] = NIL para cada v en V Par_V[v] = NIL coincidencia = 0 mientras que BFS() == verdadero por cada tu en ti si Par_U[u] == NIL si DFS(u) == verdadero coincidencia = coincidencia + 1 volver a coincidir

Explicaciones

Deje que el gráfico consista en partes de U y V. La idea clave es agregar dos vértices ficticios en cada lado del gráfico: uDummy conectado a todos los vértices descubiertos de U, y vDummy conectado a todos los vértices descubiertos de V. Ahora, si ejecutamos BFS de uDummy en vDummy, obtenemos la ruta más corta entre un vértice descubierto de U y un vértice descubierto de V. Debido al gráfico bipartito, la ruta alternará entre U y V. Sin embargo, debemos asegurarnos de que al pasar de V a U, siempre elegimos un borde de la coincidencia. Si no quedan vértices coincidentes, terminamos en vDummy. Según este criterio en el proceso BFS, al final obtenemos la ruta de aumento más corta.

Una vez que se ha encontrado la ruta de aumento más corta, se deben ignorar todas las rutas que sean más largas. BFS marca los vértices cuya distancia a la fuente es 0. Después de ejecutar BFS, podemos, partiendo de cada vértice de U que no está en el emparejamiento, ir por el camino en el que la distancia al siguiente vértice es mayor que la distancia al siguiente vértice. anterior por 1. Si terminamos llegamos a vDummy, cuya distancia es 1 más que la distancia a uno de los vértices de V, al que se puede llegar por uno de los caminos más cortos. En este caso, podemos continuar y actualizar la coincidencia de los vértices en el camino. Tenga en cuenta que cada vértice V en la ruta, excepto el último, ya está en una coincidencia. Por lo tanto, actualizar una coincidencia es equivalente a una diferencia simétrica (es decir, eliminar los bordes de la ruta que estaban en la coincidencia y agregar los que no lo estaban).

¿Cómo asegurarse de que las rutas de aumento no se crucen en los vértices? Esto ya está proporcionado. Después de realizar la diferencia simétrica, ninguno de los vértices del camino será considerado nuevamente, ya que Dist[ Pair_V[v] ] no será igual a Dist[u] + 1 (será exactamente Dist[u]).

¿Por qué son necesarias las siguientes líneas?

Dist[u] = ∞ falso retorno

Cuando no podemos encontrar ninguna ruta de aumento más corta desde u, DFS devuelve False. En este caso, será bueno marcar estos vértices para no volver a visitarlos. Para marcarlos, simplemente establecemos Dist[u] en infinito.

No necesitamos uDummy porque solo está ahí para agregar todos los vértices que no coinciden a la cola BFS. Esto se puede hacer con una simple inicialización. vDummy se puede agregar a U por conveniencia en muchas implementaciones, y la coincidencia de todos los vértices en V se puede inicializar con un puntero a vDummy. Entonces, si, después de todo, el último vértice de U no coincide con ningún vértice de V, entonces el último vértice de nuestro camino de extensión será vDummy. En el pseudocódigo anterior, vDummy se denota como Nil.

Véase también

Notas

↑ 1 2 Hopcroft y Karp (1973 )
↑ Edmonds (1965 )
↑ Algoritmos para encontrar la coincidencia máxima en un gráfico bipartito . Archivado desde el original el 19 de enero de 2017. (indefinido)
↑ Edmonds, 1965 , pág. 453.
↑ Ahuja, Magnanti & Orlin (1993 ), sección 12.3, problema de coincidencia de cardinalidad bipartita, págs. 469-470.
↑ Yefim Dinitz. Algoritmo de Dinitz: la versión original y la versión de Even // Informática teórica: Ensayos en memoria de Shimon Even (inglés) / ed. Oded Goldreich, Arnold L. Rosenberg y Alan L. Selman. - Springer, 2006. - Pág. 218-240. — ISBN 978-3540328803 .
↑ Bast et al. (2006 )
↑ Motwani (1994 )
↑ Alt et al. (1991 )
↑ Chang y McCormick (1990 ); Darby-Dowman (1980 ); Setúbal (1993 ); Setúbal (1996 ).
↑ Vazirani (2012 )
↑ Programa Java para implementar el algoritmo Hopcroft - Sanfoundry , Sanfoundry ( 20 de noviembre de 2013). Archivado desde el original el 7 de abril de 2017. Consultado el 6 de abril de 2017.

Literatura

Ahuja, Ravindra K.; Magnanti, Thomas L. & Orlin, James B. (1993), Flujos de red: teoría, algoritmos y aplicaciones , Prentice-Hall .
Alt, H.; Bloom, N.; Mehlhorn, K. y Paul, M. (1991), Cálculo de una coincidencia máxima de cardinalidad en un gráfico bipartito en el tiempo $\scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n))}\right)$ , Information Processing Letters vol 37 (4): 237–240 , DOI 10.1016/0020-0190(91)90195- n._ _
Bast, Holger; Mehlhorn, Kurt; Schafer, Guido y Tamaki, Hisao (2006), Los algoritmos de coincidencia son rápidos en gráficos aleatorios dispersos , Theory of Computing Systems vol 39 (1): 3–14 , DOI 10.1007/s00224-005-1254-y .
Blum, Norbert (2001), Una realización simplificada del enfoque de Hopcroft-Karp para la coincidencia máxima en gráficos generales , Tech. Reps. 85232-CS, Departamento de Ciencias de la Computación, Univ. de Bonn , < http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85232-CS.ps.gz > .
Chang, S. Frank & McCormick, S. Thomas (1990), Una implementación más rápida de un algoritmo de coincidencia de cardinalidad bipartita , Tech. Reps. 90-MSC-005, Facultad de Comercio y Administración de Empresas, Univ. de la Columbia Británica . Como lo cita Setúbal (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 Brunel . Como lo cita Setúbal (1996 ).
Edmonds, Jack (1965), Paths, Trees and Flowers , Canadian J. Math Vol. 17: 449–467 , DOI 10.4153/CJM-1965-045-4 .
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 Vol. 38 (4): 815–853 , DOI 10.1145/115234.115366 .
Hopcroft, John E. & Karp, Richard M. (1973), Un algoritmo n 5/2 para coincidencias máximas en gráficos bipartitos , SIAM Journal on Computing Vol. 2 (4): 225–231 , DOI 10.1137/0202019 .
Micali, S. & Vazirani, VV (1980), Un algoritmo para encontrar la coincidencia máxima en grafos generales $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ , Proc. 21º Simposio IEEE. Fundamentos de Ciencias de la Computación , p. 17–27 , DOI 10.1109/SFCS.1980.12 .
Peterson, Paul A. & Loui, Michael C. (1988), El algoritmo general de coincidencia máxima de Micali y Vazirani , Algorithmica vol.3 (1-4): 511–533 , DOI 10.1007/BF01762129 .
Motwani, Rajeev (1994), Análisis de casos promedio de algoritmos para coincidencias y problemas relacionados , Journal of the ACM Vol. 41 (6): 1329–1356 , DOI 10.1145/195613.195663 .
Setubal, João C. (1993), Nuevos resultados experimentales para emparejamiento bipartito, Proc. Netflow93 , Departamento de Informática, Univ. de Pisa, pág. 211–216 . Como lo cita Setúbal (1996 ).
Setubal, João C. (1996), Resultados experimentales secuenciales y paralelos con algoritmos de emparejamiento bipartito , Tech. Reps. IC-96-09, Inst. de Informática, Univ. de Campinas , < http://citeseerx.ist.psu.edu/viewdoc/summary?doi=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 .