En teoría de grafos y ciencias de la computación , el ancestro común más bajo ( LCA ) (también llamado ancestro mínimo común ) de dos nodos v y w en un árbol o grafo acíclico dirigido (DAG) T es el nodo más bajo (es decir, el más profundo) que tiene a v y w como descendientes, donde definimos cada nodo como un descendiente de sí mismo (por lo que si v tiene una conexión directa desde w , w es el ancestro común más bajo).
El ACV de v y w en T es el ancestro compartido de v y w que se encuentra más alejado de la raíz. El cálculo de los ancestros comunes más bajos puede ser útil, por ejemplo, como parte de un procedimiento para determinar la distancia entre pares de nodos en un árbol: la distancia de v a w se puede calcular como la distancia desde la raíz a v , más la distancia desde la raíz a w , menos el doble de la distancia desde la raíz a su ancestro común más bajo (Djidjev, Pantziou y Zaroliagis 1991).
En una estructura de datos de árbol donde cada nodo apunta a su padre, el ancestro común más bajo se puede determinar fácilmente al encontrar la primera intersección de las rutas desde v y w hasta la raíz. En general, el tiempo computacional requerido para este algoritmo es O(h), donde h es la altura del árbol (longitud de la ruta más larga desde una hoja hasta la raíz). Sin embargo, existen varios algoritmos para procesar árboles de modo que los ancestros comunes más bajos se puedan encontrar más rápidamente. El algoritmo de ancestros comunes más bajos fuera de línea de Tarjan , por ejemplo, preprocesa un árbol en tiempo lineal para proporcionar consultas LCA de tiempo constante. En general, en los DAG, existen algoritmos similares, pero con una complejidad superlineal.
El problema del ancestro común más bajo fue definido por Alfred Aho , John Hopcroft y Jeffrey Ullman (1973), pero Dov Harel y Robert Tarjan (1984) fueron los primeros en desarrollar una estructura de datos de ancestro común más bajo óptimamente eficiente. Su algoritmo procesa cualquier árbol en tiempo lineal, utilizando una descomposición de ruta pesada , de modo que las consultas posteriores de ancestro común más bajo puedan responderse en tiempo constante por consulta. Sin embargo, su estructura de datos es compleja y difícil de implementar. Tarjan también encontró un algoritmo más simple pero menos eficiente, basado en la estructura de datos union-find , para calcular los ancestros comunes más bajos de un lote fuera de línea de pares de nodos .
Baruch Schieber y Uzi Vishkin (1988) simplificaron la estructura de datos de Harel y Tarjan, lo que dio lugar a una estructura implementable con los mismos límites de tiempo de consulta y preprocesamiento asintótico. Su simplificación se basa en el principio de que, en dos tipos especiales de árboles, los ancestros comunes más bajos son fáciles de determinar: si el árbol es un camino, entonces el ancestro común más bajo se puede calcular simplemente a partir del mínimo de los niveles de los dos nodos consultados, mientras que si el árbol es un árbol binario completo , los nodos se pueden indexar de tal manera que los ancestros comunes más bajos se reduzcan a operaciones binarias simples en los índices. La estructura de Schieber y Vishkin descompone cualquier árbol en una colección de caminos, de modo que las conexiones entre los caminos tienen la estructura de un árbol binario, y combina estas dos técnicas de indexación más simples.
Omer Berkman y Uzi Vishkin (1993) descubrieron una forma completamente nueva de responder a las consultas sobre el ancestro común más bajo, logrando nuevamente un tiempo de preprocesamiento lineal con un tiempo de consulta constante. Su método implica formar un recorrido de Euler de un grafo formado a partir del árbol de entrada duplicando cada arista y usar este recorrido para escribir una secuencia de números de nivel de los nodos en el orden en que el recorrido los visita; una consulta sobre el ancestro común más bajo puede luego transformarse en una consulta que busca el valor mínimo que ocurre dentro de algún subintervalo de esta secuencia de números. Luego manejan este problema de consulta de rango mínimo (RMQ) combinando dos técnicas, una técnica basada en precalcular las respuestas a intervalos grandes que tienen tamaños que son potencias de dos, y la otra basada en la búsqueda en tablas para consultas de intervalos pequeños. Este método fue presentado más tarde en una forma simplificada por Michael Bender y Martin Farach-Colton (2000). Como habían observado previamente Gabow, Bentley y Tarjan (1984), el problema del mínimo rango puede a su vez transformarse nuevamente en un problema de ancestro común más bajo utilizando la técnica de árboles cartesianos .
Alstrup et al. (2004) y Fischer & Heun (2006) realizaron simplificaciones adicionales.
Sleator y Tarjan (1983) propusieron la variante dinámica del problema del ACV, en la que la estructura de datos debe estar preparada para manejar consultas ACV intercaladas con operaciones que cambian el árbol (es decir, reorganizan el árbol agregando y quitando aristas). Esta variante se puede resolver en el tiempo en el tamaño total del árbol para todas las modificaciones y consultas. Esto se hace manteniendo el bosque utilizando la estructura de datos de árboles dinámicos con particionamiento por tamaño; esto luego mantiene una descomposición pesada-liviana de cada árbol y permite que las consultas ACV se realicen en tiempo logarítmico en el tamaño del árbol.
Como se mencionó anteriormente, el ACV se puede reducir a RMQ. Una solución eficiente para el problema de RMQ resultante comienza por dividir la secuencia numérica en bloques. Se utilizan dos técnicas diferentes para las consultas entre bloques y dentro de los bloques.
La reducción del LCA a RMQ comienza recorriendo el árbol. Para cada nodo visitado, registre en secuencia su etiqueta y profundidad. Suponga que los nodos x e y se encuentran en las posiciones i y j en esta secuencia, respectivamente. Entonces, el LCA de x e y se encontrará en la posición RMQ( i , j ), donde el RMQ se toma sobre los valores de profundidad.
A pesar de que existe una solución de tiempo constante y espacio lineal para RMQ general, se puede aplicar una solución simplificada que haga uso de las propiedades del ACV. Esta solución simplificada solo se puede utilizar para RMQ reducido a partir del ACV.
De manera similar a la solución mencionada anteriormente, dividimos la secuencia en cada bloque , donde cada bloque tiene un tamaño de .
Al dividir la secuencia en bloques, la consulta se puede resolver resolviendo dos casos diferentes:
Para responder a la consulta del caso uno, hay 3 grupos de variables precalculadas para ayudar a reducir el tiempo de consulta.
En primer lugar, se calcula previamente el elemento mínimo con el índice más pequeño en cada bloque y se denota como . Un conjunto de ocupa espacio.
En segundo lugar, dado el conjunto de , la consulta RMQ para este conjunto se calcula previamente utilizando la solución con tiempo constante y espacio linealítmico . Hay bloques, por lo que la tabla de búsqueda en esa solución ocupa espacio. Porque , = espacio. Por lo tanto, la consulta RMQ calculada previamente que utiliza la solución con tiempo constante y espacio linealítmico en estos bloques solo ocupa espacio.
En tercer lugar, en cada bloque , sea un índice en tal que . Para todos desde hasta , el bloque se divide en dos intervalos y . Luego, se precalcula el elemento mínimo con el índice más pequeño para los intervalos en y en cada bloque . Dichos elementos mínimos se denominan prefijo min para el intervalo en y sufijo min para el intervalo en . Cada iteración de calcula un par de prefijo min y sufijo min. Por lo tanto, el número total de prefijo min y sufijo min en un bloque es . Dado que hay bloques, en total, todas las matrices de prefijo min y sufijo min toman que es espacios.
En total, se necesita espacio para almacenar los tres grupos de variables precalculadas mencionadas anteriormente.
Por lo tanto, responder a la pregunta del caso 1 es simplemente plantear el mínimo de las tres preguntas siguientes:
Sea el bloque que contiene el elemento en el índice , y para el índice .
Las tres preguntas pueden responderse en tiempo constante. Por lo tanto, el caso 1 puede responderse en espacio lineal y tiempo constante.
La secuencia de RMQ que se redujo a partir de LCA tiene una propiedad que un RMQ normal no tiene. El siguiente elemento siempre es +1 o -1 desde el elemento actual. Por ejemplo:
Por lo tanto, cada bloque se puede codificar como una cadena de bits, donde 0 representa la profundidad actual -1 y 1 representa la profundidad actual +1. Esta transformación convierte un bloque en una cadena de bits de tamaño . Una cadena de bits de tamaño tiene posibles cadenas de bits. Como , entonces .
Por lo tanto, siempre es una de las posibles cadenas de bits con tamaño de .
Luego, para cada una de las posibles cadenas de bits, aplicamos la solución ingenua de tiempo constante espacial cuadrática . Esto ocupará espacios, que son .
Por lo tanto, responder a la consulta del caso 2 es simplemente encontrar el bloque correspondiente (en el que hay una cadena de bits) y realizar una búsqueda en la tabla para esa cadena de bits. Por lo tanto, el caso 2 se puede resolver utilizando un espacio lineal con un tiempo de búsqueda constante.
Aunque originalmente se estudió en el contexto de los árboles, la noción de ancestro común más bajo se puede definir para los grafos acíclicos dirigidos (DAG), utilizando cualquiera de dos definiciones posibles. En ambas, se supone que los bordes del DAG apuntan de los padres a los hijos.
En un árbol, el ancestro común más bajo es único; en un DAG de n nodos, cada par de nodos puede tener hasta n -2 LCA (Bender et al. 2005), mientras que la existencia de un LCA para un par de nodos ni siquiera está garantizada en DAG conectados arbitrariamente.
Aït-Kaci et al. (1989) ofrecen un algoritmo de fuerza bruta para encontrar los ancestros comunes más bajos: se encuentran todos los ancestros de x e y y , luego se devuelve el elemento máximo de la intersección de los dos conjuntos. Existen mejores algoritmos que, de manera análoga a los algoritmos LCA en árboles, preprocesan un gráfico para permitir consultas LCA de tiempo constante. El problema de la existencia de LCA se puede resolver de manera óptima para DAG dispersos mediante un algoritmo O(| V || E |) debido a Kowaluk y Lingas (2005).
Dash et al. (2013) presentan un marco unificado para el preprocesamiento de grafos acíclicos dirigidos con el fin de calcular un ancestro común más bajo representativo en un DAG enraizado en tiempo constante. Su marco puede lograr tiempos de preprocesamiento casi lineales para grafos dispersos y está disponible para uso público. [1]
El problema de calcular los ancestros comunes más bajos de las clases en una jerarquía de herencia surge en la implementación de sistemas de programación orientada a objetos (Aït-Kaci et al. 1989). El problema del ACV también encuentra aplicaciones en modelos de sistemas complejos que se encuentran en la computación distribuida (Bender et al. 2005).
