LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

algoritmo Hopcroft-Karp (a veces más precisamente llamado el algoritmo Hopcroft-Karp-Karzanov ) ^[1] es un algoritmo que toma como entrada un gráfico bipartito y produce como resultado una coincidencia de cardinalidad máxima , un conjunto de tantos bordes como sea posible con la propiedad de que no hay dos bordes que compartan un punto final. Se ejecuta en$${\ displaystyle O (| E | {\ sqrt {| V |}})}tiempo en el peor de los casos , donde$${\ displaystyle E} Es conjunto de aristas en la gráfica, $${\ displaystyle V} es conjunto de vértices de la gráfica, y se supone que $${\ displaystyle | E | = \ Omega (| V |)}. En el caso de gráficos densos, el límite temporal se convierte en$${\ displaystyle O (| V | ^ {2.5})}, y para gráficos aleatorios dispersos se ejecuta en tiempo casi lineal (en | E |).

El algoritmo fue encontrado por John Hopcroft y Richard Karp  ( 1973 ) e independientemente por Alexander Karzanov  ( 1973 ). ^[2] Como en los métodos anteriores para hacer coincidir, como el algoritmo húngaro y el trabajo de Edmonds (1965), el algoritmo Hopcroft-Karp aumenta repetidamente el tamaño de una coincidencia parcial al encontrar rutas de aumento: secuencias de bordes que se alternan entre estar dentro y fuera de la coincidencia, de manera tal que se intercambian los bordes de la ruta y los que están fuera de la coincidencia. produce una mayor coincidencia. Sin embargo, en lugar de encontrar una sola ruta de aumento por iteración, el algoritmo encuentra un conjunto máximo de rutas de aumento más cortas. Como resultado, solo$${\ displaystyle O ({\ sqrt {| V |}})}Se necesitan iteraciones. El mismo principio también se ha utilizado para desarrollar algoritmos más complicados para la comparación no bipartita con el mismo tiempo de ejecución asintótico que el algoritmo Hopcroft-Karp.

Aumentar caminos [ editar ]

Un vértice que no es el punto final de un borde en una coincidencia parcial $${\ displaystyle M}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 no coincidentes y emparejados dentro de la ruta. De esta definición se desprende que, a excepción de los puntos finales, todos los demás vértices (si hay alguno) en la ruta de aumento deben ser vértices no libres. Un camino de aumento podría constar de solo dos vértices (ambos libres) y un solo borde no emparejado entre ellos.

Si $${\ displaystyle M} es una coincidencia, y $${\ displaystyle P} es un camino de aumento en relación con $${\ displaystyle M}, entonces la diferencia simétrica de los dos conjuntos de bordes,$${\ displaystyle M \ oplus P}, formaría una coincidencia con el tamaño $${\ displaystyle | M | +1}. Por lo tanto, al encontrar rutas de aumento, un algoritmo puede aumentar el tamaño de la coincidencia.

A la inversa, supongamos que una coincidencia $${\ displaystyle M} no es óptimo, y deja $${\ displaystyle P} ser la diferencia simétrica $${\ displaystyle M \ oplus M ^ {*}}dónde $${\ displaystyle M ^ {*}}es una coincidencia óptima. Porque$${\ displaystyle M} y $${\ displaystyle M ^ {*}} son ambos emparejamientos, cada vértice tiene un grado máximo de 2 en $${\ displaystyle P}. Asi que$${\ displaystyle P} debe formar una colección de ciclos separados, de rutas con un número igual de bordes coincidentes y no coincidentes en $${\ displaystyle M}, de caminos de aumento para $${\ displaystyle M}, y de aumentar caminos para $${\ displaystyle M ^ {*}}; pero esto último es imposible porque$${\ displaystyle M ^ {*}}es optimo Ahora, los ciclos y las rutas con igual número de vértices emparejados y no emparejados no contribuyen a la diferencia de tamaño entre$${\ displaystyle M} y $${\ displaystyle M ^ {*}}, por lo que esta diferencia es igual al número de rutas de aumento para $${\ displaystyle M} en $${\ displaystyle P}. Así, siempre que exista una concordancia.$${\ displaystyle M ^ {*}}más grande que la coincidencia actual $${\ displaystyle M}, también debe existir un camino de aumento. Si no se puede encontrar una ruta de aumento, un algoritmo puede terminar de forma segura, ya que en este caso$${\ displaystyle M} debe ser optimo

Una ruta de aumento en un problema coincidente está estrechamente relacionada con las rutas de aumento quesurgen en los problemas de flujo máximo , rutas a lo largo de las cuales se puede aumentar la cantidad de flujo entre los terminales del flujo. Es posible transformar el problema de coincidencia bipartito en una instancia de flujo máximo, de manera que las rutas alternas del problema coincidente se conviertan en rutas de aumento del problema de flujo. ^[3] De hecho, una generalización de la técnica utilizada en el algoritmo Hopcroft-Karp a redes de flujo arbitrario se conoce como algoritmo de Dinic .

Algoritmo [ editar ]

El algoritmo puede expresarse en el siguiente pseudocódigo .

Entrada : gráfico bipartito$${\ displaystyle G (U \ cup V, E)}

Salida : a juego$${\ displaystyle M \ subseteq E}

$${\ displaystyle M \ leftarrow \ emptyset}

repetir

$${\ displaystyle {\ mathcal {P}} \ leftarrow \ {P_ {1}, P_ {2}, \ dots, P_ {k} \}} Conjunto máximo de rutas de aumento más cortas de vértice-desunión

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

hasta $${\ displaystyle {\ mathcal {P}} = \ emptyset}

En más detalle, vamos a $${\ displaystyle U} y $${\ displaystyle V} Ser los dos conjuntos en la bipartición de $${\ displaystyle G}, y dejar que el emparejamiento de $${\ displaystyle U} a $${\ displaystyle V} En cualquier momento se representará como el conjunto. $${\ displaystyle M}. El algoritmo se ejecuta en fases. Cada fase consta de los siguientes pasos.

• Una búsqueda en primer lugar divide los vértices del gráfico en capas. Los vértices libres en$${\ displaystyle U}se utilizan como los vértices de inicio de esta búsqueda y forman la primera capa de la partición. En el primer nivel de la búsqueda, solo hay bordes no coincidentes, ya que los vértices libres en$${\ displaystyle U}Por definición, no son adyacentes a ningún borde coincidente. En los niveles subsiguientes de la búsqueda, los bordes atravesados ​​deben alternar entre coincidencias y no coincidentes. Es decir, al buscar sucesores de un vértice en$${\ displaystyle U}, solo se pueden atravesar bordes no coincidentes, mientras que desde un vértice en $${\ displaystyle V}solo los bordes coincidentes pueden ser atravesados. La búsqueda termina en la primera capa.$${\ displaystyle k} donde uno o más vértices libres en $${\ displaystyle V} se alcanzan
• Todos los vértices libres en $${\ displaystyle V} en la capa $${\ displaystyle k} se recogen en un conjunto $${\ displaystyle F}. Es decir, un vértice.$${\ displaystyle v} se pone en $${\ displaystyle F}Si y solo si termina un camino de aumento más corto.
• El algoritmo encuentra un conjunto máximo de vértices disjuntos que aumentan las rutas de longitud$${\ displaystyle k}. ( Máximo significa que no se pueden agregar más rutas de este tipo. Esto es diferente de encontrar el número máximo de rutas, lo que sería más difícil de hacer. Afortunadamente, aquí es suficiente encontrar un conjunto máximo de rutas.) Este conjunto puede ser calculada por búsqueda en profundidad (DFS) desde$${\ displaystyle F} a los vértices libres en $${\ displaystyle U}, 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 un camino de aumento que involucra uno de los vértices en$${\ displaystyle F}, el DFS se 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 de acceso a él$${\ displaystyle U} en el punto actual del DFS, entonces ese vértice no se puede usar para alcanzar $${\ displaystyle U}en cualquier otro punto del DFS. Esto garantiza$${\ displaystyle O (| E |)}Tiempo de ejecución para el DFS. También es posible trabajar en la otra dirección, desde vértices libres en$${\ displaystyle U} a aquellos en $${\ displaystyle V}, que es la variante utilizada en el pseudocódigo.
• Cada uno de los caminos encontrados de esta manera se utiliza para agrandar. $${\ displaystyle M}.

El algoritmo termina cuando ya no se encuentran más rutas de aumento en la primera parte de búsqueda de una de las fases.

Análisis [ editar ]

Cada fase consiste en una primera búsqueda de amplitud única y una primera búsqueda de profundidad única. Así, una sola fase puede ser implementada en$${\ displaystyle O (| E |)}hora. Por lo tanto, la primera$${\ displaystyle {\ sqrt {| V |}}} fases, en una gráfica con $${\ displaystyle | V |} vértices y $${\ displaystyle | E |} bordes, toma tiempo $${\ displaystyle O (| E | {\ sqrt {| V |}})}.

Cada fase aumenta la longitud del camino de aumento más corto en al menos uno: la fase encuentra un conjunto máximo de caminos de aumento de la longitud dada, por lo que cualquier camino de aumento restante debe ser más largo. Por lo tanto, una vez que la inicial$${\ displaystyle {\ sqrt {| V |}}} las fases del algoritmo están completas, la ruta de aumento restante más corta tiene al menos $${\ displaystyle {\ sqrt {| V |}}}bordes en el mismo. Sin embargo, la diferencia simétrica de la eventual concordancia óptima y de la concordancia parcial M encontrada en las fases iniciales forma una colección de rutas de aumento y ciclos alternos de vértice desunido. Si cada uno de los caminos en esta colección tiene longitud al menos$${\ displaystyle {\ sqrt {| V |}}}, puede haber a lo sumo $${\ displaystyle {\ sqrt {| V |}}} las rutas en la colección, y el tamaño de la coincidencia óptima puede diferir del tamaño de $${\ displaystyle M} como mucho $${\ displaystyle {\ sqrt {| V |}}}bordes Como cada fase del algoritmo aumenta el tamaño de la coincidencia en al menos uno, puede haber como máximo$${\ displaystyle {\ sqrt {| V |}}} Fases adicionales antes de que el algoritmo termine.

Dado que el algoritmo realiza un total de a lo sumo $${\ displaystyle 2 {\ sqrt {| V |}}} fases, lleva un tiempo total de $${\ displaystyle O (| E | {\ sqrt {| V |}})} En el peor de los casos.

Sin embargo, en muchos casos, el tiempo empleado por el algoritmo puede ser incluso más rápido de lo que indica el 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 rutas de aumento de longitud logarítmica . Como consecuencia, para estos gráficos, el algoritmo Hopcroft-Karp toma$${\ displaystyle O (\ log | V |)} fases y $${\ displaystyle O (| E | \ log | V |)} Tiempo Total.

Comparación con otros algoritmos de correspondencia bipartita [ editar ]

Para gráficos dispersos , el algoritmo Hopcroft-Karp continúa teniendo el mejor desempeño de peor caso conocido, pero para gráficos densos ($${\ displaystyle | E | = \ Omega (| V | ^ {2})}) un algoritmo más reciente por Alt et al. (1991) logra un límite de tiempo ligeramente mejor,$${\ displaystyle O \ left (| V | ^ {1.5} {\ sqrt {\ frac {| E |} {\ log | V |}}} \ right)}. Su algoritmo se basa en el uso de un algoritmo de flujo máximo push-reetiquetado y luego, cuando la coincidencia creada 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. En general, sus resultados tienden a mostrar que el método de Hopcroft-Karp no es tan bueno en la práctica como en teoría: es superado tanto por estrategias de amplitud más simples como por estrategias de primer plano más profundas para encontrar caminos de aumento, y por técnicas de push-reetiquetado. . ^[4]

Gráficos no bipartitos [ editar ]

La misma idea de encontrar un 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 los algoritmos basados ​​en esta idea toman $${\ displaystyle O ({\ sqrt {| V |}})}fases 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. Sobre la base del trabajo de varios predecesores más lentos, Micali y Vazirani (1980) mostraron cómo implementar una fase en el tiempo lineal, lo que resulta en un algoritmo de coincidencia no bipartito con el mismo tiempo que el algoritmo Hopcroft-Karp para los gráficos bipartitos. La técnica Micali-Vazirani es compleja, y sus autores no proporcionaron pruebas completas de sus resultados; posteriormente, Peterson & Loui (1988) publicó una "exposición clara" y otros autores describieron métodos alternativos. ^[5] En 2012, Vazirani ofreció una nueva prueba simplificada del algoritmo Micali-Vazirani. ^[6]

Pseudocódigo [ editar ]

/ * 
 G = U ∪ V ∪ {NIL}
 donde U y V son particiones del gráfico y NIL es un vértice nulo especial
* /
  
función BFS ()
    para cada u en u
        si Pair_U [u] == NIL
            Dist [u] = 0
            Encolar (Q, u)
        más
            Dist [u] = ∞
    Dist [NIL] = ∞
    mientras está vacío (Q) == falso
        u = Dequeue (Q)
        si Dist [u] 
            para cada v en Adj [u]
                si Dist [Pair_V [v]] == ∞
                    Dist [Pair_V [v]] = Dist [u] + 1
                    Encolar (Q, Pair_V [v])
    volver Dist [NIL]! = ∞

función DFS (u)
    si u! = NIL
        para cada v en Adj [u]
            si Dist [Pair_V [v]] == Dist [u] + 1
                si DFS (Pair_V [v]) == verdadero
                    Pair_V [v] = u
                    Pair_U [u] = v
                    volver verdadero
        Dist [u] = ∞
        falso retorno
    volver verdadero

función Hopcroft-Karp
    para cada u en u
        Pair_U [u] = NIL
    para cada v en v
        Pair_V [v] = NIL
    coincidente = 0
    mientras que BFS () == verdadero
        para cada u en u
            si Pair_U [u] == NIL
                si DFS (u) == verdadero
                    coincidencia = coincidencia + 1
    volver a juego

Ejecución en un gráfico de ejemplo que muestra el gráfico de entrada y la coincidencia después de la iteración intermedia 1 y la iteración final 2.

Explicación [ editar ]

Deje que nuestro gráfico tenga dos particiones U, V. La idea clave es agregar dos vértices ficticios en cada lado del gráfico: uDummy conectándolo a todos los vértices no coincidentes en U y vDummy conectando a todos los vértices no coincidentes en V. Ahora, si ejecutamos BFS de uDummy a vDummy, entonces podemos obtener la ruta más corta entre un vértice no coincidente en U y un vértice no coincidente en V. Debido a la naturaleza bipartita de la gráfica, esta ruta zigzag de U a V. Sin embargo, debemos asegurarnos de que al ir de V a U, siempre seleccionamos el borde emparejado. Si no hay un borde coincidente, terminamos en vDummy. Si nos aseguramos de estos criterios durante BFS, la ruta generada cumpliría con los criterios para ser la ruta más corta aumentada.

Una vez que hayamos encontrado la ruta más corta aumentada, queremos asegurarnos de ignorar cualquier otra ruta que sea más larga que esta. El algoritmo BFS marca los nodos en la ruta con la fuente siendo 0. Por lo tanto, después de hacer BFS, podemos comenzar en cada vértice no emparejado en U, seguir la ruta siguiendo los nodos con la distancia que se incrementa en 1. Cuando finalmente lleguemos al destino vDummy Si su distancia es 1 más que el último nodo en V, entonces sabemos que la ruta que seguimos es (posiblemente una de las muchas) más corta. En ese caso, podemos continuar y actualizar el emparejamiento de vértices en la ruta en U y V. Tenga en cuenta que cada vértice en V en la ruta, excepto el último, no es un vértice libre. Por lo tanto, la actualización del emparejamiento para estos vértices en V a diferentes vértices en U equivale a eliminar el borde previamente coincidente y agregar un nuevo borde no coincidente en la coincidencia.

¿Cómo nos aseguramos de que los caminos aumentados estén separados de vértice? Ya está garantizado: después de hacer la diferencia simétrica para una ruta, ninguno de sus vértices podría considerarse de nuevo solo porque Dist [Pair_V [v]] no será igual a Dist [u] + 1 (sería exactamente Dist [ u]).

Entonces, ¿cuál es la misión de estas dos líneas en pseudocódigo ?:

Dist [u] = ∞
falso retorno

Cuando no pudimos encontrar ninguna ruta aumentada más corta desde un vértice, DFS devuelve falso. En este caso, sería bueno marcar estos vértices para no volver a visitarlos. Esta marca se hace simplemente estableciendo Dist [u] a infinito.

Finalmente, en realidad no necesitamos uDummy porque está ahí solo para poner en cola todos los vértices no emparejados de U cuando se inicia BFS. Eso lo podemos hacer igual que la inicialización. VDummy se puede agregar en U para mayor comodidad en muchas implementaciones e inicializar el emparejamiento predeterminado para que todas las V apunten a vDummy. De esa manera, si el vértice final en V no tiene ningún vértice coincidente en U, finalmente terminamos en vDummy, que es el final de nuestra ruta aumentada. En el anterior pseudocódigo vDummy se denota como Nil.