Estaba echando un vistazo a this question y luego leyendo sobre Tarjan's least common ancestors algorithm. Nunca me encontré con ninguna aplicación de algoritmos LCA antes.¿Cuáles son las aplicaciones prácticas de los algoritmos ancestrales comunes más bajos?
¿Dónde se utilizan estos algoritmos LCA?
No sabe donde se utiliza, pero tengo un par de ideas, donde puede ser que consiga utilizados:
gráficos por ordenador: a menudo escenarios 3D separarnos en cubos que forman una estructura de árbol. Si tiene un objeto que está contenido en dos de tales cubos, un algoritmo LCA le proporciona el cubo más grande que contiene más grande.
análisis de gens con el fin de encontrar las relaciones entre las especies y su ancestro común más bajo
algoritmos de fusión de los sistemas de control de versiones
gracias! control de versiones -> combinación de tres vías: http://en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Lazer
También es útil para ciertos tipos de procesamiento de cadenas cuando se buscan palabras raíz para diferentes sufijos. –
En compiladores, el ACV de dos bloques básicos es una lugar puede poner un cálculo para que esté disponible para ambos. Esto podría ser útil para eliminar subexpresiones comunes, o insertar phi-node para la conversión de SSA. Sin embargo, estos algoritmos están bien desarrollados y altamente optimizados, por lo que el ACV puede ser difícil de ver, por ejemplo, SSA y PRE
gracias @ Doug Currie – Lazer
Acabo de escribir una entrada de blog sobre cómo tuve que implementar mi propio algoritmo para este problema (extendido a un conjunto de nodos con una longitud arbitraria) para un árbol de la taxonomía en el contexto de la metagenómica:
Cheers,
Pablo
espacial árboles de estructura de datos en computación científica, árboles de sufijos para cadenas en biología computacional, etc. Olvidó los detalles, lo siento, pero definitivamente es útil. – polygenelubricants