En teoría de grafos e informática , el ancestro común más bajo ( LCA ) 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 tanto v como w como descendientes, donde define cada nodo como un descendiente de sí mismo (por lo que si v tiene una conexión directa de w , w es el ancestro común más bajo).
El LCA 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 antepasados 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 de la raíz av , más la distancia desde la raíz hasta w , menos el doble de la distancia desde la raíz hasta su antepasado común más bajo ( Djidjev, Pantziou y Zaroliagis 1991 ). En ontologías , el ancestro común más bajo también se conoce como el ancestro menos común .
En una estructura de datos de árbol donde cada nodo apunta a su padre, el ancestro común más bajo se pueden determinar fácilmente mediante la búsqueda de la primera intersección de los caminos de v y w a la raíz. En general, el tiempo de cálculo requerido para este algoritmo es O (h) donde h es la altura del árbol (longitud del camino más largo desde una hoja hasta la raíz). Sin embargo, existen varios algoritmos para procesar árboles, de modo que los antepasados 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 de LCA en tiempo constante. En general, los DAG existen algoritmos similares, pero con una complejidad superlineal.
Historia
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 antepasados comunes más bajos puedan responderse en un 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 de búsqueda de unión , para calcular los antepasados comunes más bajos de un lote de pares de nodos fuera de línea .
Baruch Schieber y Uzi Vishkin ( 1988 ) simplificaron la estructura de datos de Harel y Tarjan, lo que condujo a una estructura implementable con los mismos límites de tiempo de consulta y preprocesamiento asintóticos. Su simplificación se basa en el principio de que, en dos tipos especiales de árboles, los antepasados comunes más bajos son fáciles de determinar: si el árbol es un camino, entonces el ancestro común más bajo puede calcularse simplemente a partir del mínimo de los niveles de los dos consultados. nodos, mientras que si el árbol es un árbol binario completo , los nodos pueden indexarse de tal manera que los antepasados 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 rutas, de modo que las conexiones entre las rutas 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 las consultas de ancestros comunes más bajos, logrando nuevamente un tiempo de preprocesamiento lineal con un tiempo de consulta constante. Su método consiste en formar un recorrido de Euler de un gráfico formado a partir del árbol de entrada al duplicar cada borde y utilizar 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 de ancestro común más bajo se puede transformar 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 combinando dos técnicas, una técnica basada en el cálculo previo de las respuestas a intervalos grandes que tienen tamaños que son potencias de dos, y la otra basada en la búsqueda de tablas para consultas de intervalos pequeños. Este método fue posteriormente presentado de forma simplificada por Michael Bender y Martin Farach-Colton ( 2000 ). Como habían observado previamente Gabow, Bentley y Tarjan (1984) , el problema del rango mínimo puede, a su vez, volver a transformarse en un problema de ancestro común más bajo utilizando la técnica de los árboles cartesianos .
Otras simplificaciones fueron hechas por Alstrup et al. (2004) y Fischer y Heun (2006) .
Sleator y Tarjan ( 1983 ) propusieron la variante LCA dinámica del problema en la que la estructura de datos debe estar preparada para manejar consultas LCA entremezcladas con operaciones que cambian el árbol (es decir, reorganizar el árbol agregando y quitando bordes). Esta variante se puede resolver entiempo en el tamaño total del árbol para todas las modificaciones y consultas. Esto se hace manteniendo el bosque usando la estructura de datos de árboles dinámicos con particiones por tamaño; esto mantiene una descomposición pesada-ligera de cada árbol y permite que las consultas de LCA se realicen en tiempo logarítmico en el tamaño del árbol.
También se puede mejorar el tiempo de cálculo del ingenuo algoritmo en línea para en la altura del árbol almacenando los caminos a través del árbol usando listas de acceso aleatorio binarias sesgadas, aunque las ediciones se limitan a la extensión en las hojas. [1]
Extensión a grafos acíclicos dirigidos
Aunque originalmente se estudió en el contexto de los árboles, la noción de antepasados comunes más bajos se puede definir para gráficos acíclicos dirigidos (DAG), utilizando cualquiera de las dos definiciones posibles. En ambos, se supone que los bordes del DAG apuntan de padres a hijos.
- Dado G = ( V , E ) , Aït-Kaci et al. (1989) definen un poset ( V , ≤) tal que x ≤ y sif x es alcanzable desde y . Los ancestro común más bajo de x y y son entonces los elementos mínimos bajo ≤ del conjunto ancestro común { z ∈ V | x ≤ z y y ≤ z }.
- Bender y col. (2005) dio una definición equivalente, donde el ancestro común más bajo de x y y son los nodos de fuera de grado cero en el subgrafo de G inducido por el conjunto de ancestros comunes de x y y .
En un árbol, el antepasado 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.
Un algoritmo de fuerza bruta para encontrar los ancestros comunes más bajos es proporcionado por Aït-Kaci et al. (1989) : encontrar todos los antepasados de x y y , a continuación, devolver el elemento de máxima de la intersección de los dos conjuntos. Existen mejores algoritmos que, de forma análoga a los algoritmos LCA en árboles, preprocesan un gráfico para permitir consultas LCA en tiempo constante. El problema de la existencia de LCA se puede resolver de manera óptima para DAG escasos mediante un algoritmo O (| V || E |) debido a Kowaluk & Lingas (2005) .
Dash y col. (2013) presentan un marco unificado para preprocesar gráficos acíclicos dirigidos para calcular los antepasados comunes más bajos en tiempo constante. Su marco puede lograr tiempos de preprocesamiento casi lineales para gráficos dispersos y está disponible para uso público. [2]
Aplicaciones
El problema de calcular los antepasados comunes más bajos de las clases en una jerarquía de herencia surge en la implementación de sistemas de programación orientados a objetos ( Aït-Kaci et al. 1989 ). El problema de LCA también encuentra aplicaciones en modelos de sistemas complejos que se encuentran en la computación distribuida ( Bender et al. 2005 ).
Ver también
- Problema de ancestro de nivel
- Semirredura
Referencias
- ^ https://www.schoolofhaskell.com/user/edwardk/online-lca Edward Kmett (2012)
- ^ "Pruebe nuestro código fuente de forma gratuita" .
- Aho, Alfred ; Hopcroft, John ; Ullman, Jeffrey (1973), "Sobre la búsqueda de los antepasados comunes más bajos en los árboles", Proc. 5th ACM Symp. Teoría de la Computación (STOC) , págs. 253–265, doi : 10.1145 / 800125.804056.
- Aït-Kaci, H .; Boyer, R .; Lincoln, P .; Nasr, R. (1989), "Implementación eficiente de operaciones de celosía" (PDF) , ACM Transactions on Programming Languages and Systems , 11 (1): 115–146, CiteSeerX 10.1.1.106.4911 , doi : 10.1145 / 59287.59293.
- Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis (2004), "Ancestros comunes más cercanos: una encuesta y un nuevo algoritmo para un entorno distribuido" , Teoría de los sistemas informáticos , 37 (3): 441–456, CiteSeerX 10.1.1.76.5973 , doi : 10.1007 / s00224 -004-1155-5. Una versión preliminar apareció en SPAA 2002.
- Bender, Michael A .; Farach-Colton, Martin (2000), "The LCA problem revisited", Proceedings of the 4th Latin American Symposium on Theoretical Informatics , Lecture Notes in Computer Science , 1776 , Springer-Verlag, pp. 88–94 , doi : 10.1007 / 10719839_9 , ISBN 978-3-540-67306-4.
- Bender, Michael A .; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena, Steven ; Sumazin, Pavel (2005), "Los ancestros comunes más bajos en árboles y gráficos acíclicos dirigidos" (PDF) , Journal of Algorithms , 57 (2): 75–94, doi : 10.1016 / j.jalgor.2005.08.001.
- Berkman, Omer; Vishkin, Uzi (1993), "Recursive Star-Tree Parallel Data Structure" , SIAM Journal on Computing , 22 (2): 221–242, doi : 10.1137 / 0222017.
- Dash, Santanu Kumar; Scholz, Sven-Bodo; Herhut, Stephan; Christianson, Bruce (2013), "Un enfoque escalable para calcular el antepasado común más bajo representativo en gráficos acíclicos dirigidos" (PDF) , Theoretical Computer Science , 513 : 25–37, doi : 10.1016 / j.tcs.2013.09.030 , hdl : 2299/12152
- Djidjev, Hristo N .; Pantziou, Grammati E .; Zaroliagis, Christos D. (1991), "Computación de trayectorias y distancias más cortas en gráficos planos", Autómatas, lenguajes y programación: 18º Coloquio Internacional, Madrid, España, 8 al 12 de julio de 1991, Actas , Notas de conferencia en Ciencias de la Computación, 510 , Springer, págs. 327–338, doi : 10.1007 / 3-540-54233-7_145 , ISBN 978-3-540-54233-9.
- Fischer, Johannes; Heun, Volker (2006), "Mejoras teóricas y prácticas en el problema RMQ, con aplicaciones a LCA y LCE", Actas del 17º Simposio Anual sobre Concordancia de Patrones Combinatorios , Lecture Notes in Computer Science, 4009 , Springer-Verlag, págs. . 36–48, CiteSeerX 10.1.1.64.5439 , doi : 10.1007 / 11780441_5 , ISBN 978-3-540-35455-0.
- Gabow, Harold N .; Bentley, Jon Louis ; Tarjan, Robert E. (1984), "Escalado y técnicas relacionadas para problemas de geometría", STOC '84: Proc. 16º Simposio de ACM sobre Teoría de la Computación , Nueva York, NY, EE. UU.: ACM, págs. 135–143, doi : 10.1145 / 800057.808675 , ISBN 978-0897911337.
- Harel, Dov; Tarjan, Robert E. (1984), "Algoritmos rápidos para encontrar ancestros comunes más cercanos", SIAM Journal on Computing , 13 (2): 338–355, doi : 10.1137 / 0213024.
- Kowaluk, Miroslaw; Lingas, Andrzej (2005), "Consultas LCA en grafos acíclicos dirigidos", en Caires, Luís; Italiano, Giuseppe F .; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti (eds.), Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisboa, Portugal, 11-15 de julio de 2005, Proceedings , Lecture Notes in Computer Science, 3580 , Springer, págs. 241–248 , CiteSeerX 10.1.1.460.6923 , doi : 10.1007 / 11523468_20 , ISBN 978-3-540-27580-0
- Schieber, Baruch; Vishkin, Uzi (1988), "Sobre la búsqueda de ancestros comunes más bajos: simplificación y paralelización", SIAM Journal on Computing , 17 (6): 1253-1262, doi : 10.1137 / 0217079.
- Sleator, DD ; Tarjan, RE (1983), "A Data Structure for Dynamic Trees" (PDF) , Actas del decimotercer simposio anual de ACM sobre teoría de la computación - STOC '81 , págs. 114-122, doi : 10.1145 / 800076.802464
enlaces externos
- El antepasado común más bajo de un árbol de búsqueda binaria , por Kamal Rawat
- Implementación en Python del algoritmo de Bender y Farach-Colton para árboles , por David Eppstein
- Implementación de Python para gráficos acíclicos dirigidos arbitrarios
- Apuntes de conferencias sobre LCA de un curso de estructuras de datos del MIT de 2003 . Curso de Erik Demaine , notas escritas por Loizos Michael y Christos Kapoutsis. Notas de 2007 que ofrecen el mismo curso , escritas por Alison Cichowlas.
- Antepasado común más bajo en los árboles binarios en C . Una versión simplificada de la técnica de Schieber-Vishkin que funciona solo para árboles binarios balanceados.
- Video de Donald Knuth explicando la técnica de Schieber-Vishkin
- Artículo de consulta mínima de rango y antepasado común más bajo en Topcoder
- Documentación para el paquete lca para Haskell de Edward Kmett, que incluye el algoritmo de lista de acceso aleatorio binario sesgado. Estructuras de datos puramente funcionales para diapositivas de LCA en línea para el mismo paquete.