algorithm - mineria - Algoritmo del árbol genealógico

algoritmos de arboles de decision (9)

Aquí está mi puñalada:

class Person { Person [] Parents; string Name; DateTime DOB; DateTime DOD; int Generations = 0; void Increase(Datetime dob, int generations) { // current person is alive when caller was born if (dob < DOD) Generations = Math.Max(Generations, generations) foreach (Person p in Parents) p.Increase(dob, generations + 1); } void Calculate() { foreach (Person p in Parents) p.Increase(DOB, 1); } } // run for everyone Person [] people = InitializeList(); // create objects from information foreach (Person p in people) p.Calculate();

Estoy trabajando en armar un conjunto de problemas para un curso de CS de nivel de introducción y surgió una pregunta que, en apariencia, parece muy simple:

Le dan una lista de personas con los nombres de sus padres, sus fechas de nacimiento y sus fechas de fallecimiento. Usted está interesado en descubrir quién, en algún momento de su vida, fue un padre, un abuelo, un bisabuelo, etc. Diseñe un algoritmo para etiquetar a cada persona con esta información como un entero (0 significa que la persona nunca tuvo un niño, 1 significa que la persona era un padre, 2 significa que la persona era un abuelo, etc.)

Para simplificar, puede suponer que el gráfico de familia es un DAG cuya versión no dirigida es un árbol.

El desafío interesante aquí es que no puedes simplemente mirar la forma del árbol para determinar esta información. Por ejemplo, tengo 8 tatarabuelos, pero como ninguno de ellos estaba vivo cuando nací, ninguno de ellos fue tatara-tatara-abuelo en vida.

El mejor algoritmo que se me ocurre para este problema se ejecuta en el tiempo O (n ² ), donde n es el número de personas. La idea es simple: comience un DFS de cada persona, encontrando el descendiente más lejano en el árbol genealógico que nació antes de la fecha de fallecimiento de esa persona. Sin embargo, estoy bastante seguro de que esta no es la solución óptima para el problema. Por ejemplo, si el gráfico es solo dos padres y sus n hijos, entonces el problema se puede resolver trivialmente en O (n). Lo que espero es algún algoritmo que sea igual a O (n ² ) o cuyo tiempo de ejecución se parametrice sobre la forma del gráfico que lo hace rápido para gráficos anchos con una degradación elegante a O (n ² ) en el peor de los casos caso.

Crea una lista de personas ordenadas por birth_date . Crea otra lista de personas, clasificada por death_date . Puede viajar lógicamente en el tiempo, extrayendo personas de estas listas, para obtener una lista de los eventos tal como sucedieron.

Para cada persona, defina un campo is_alive . Esto será FALSO para todos al principio. A medida que las personas nacen y mueren, actualice este registro en consecuencia.

Defina otro campo para cada persona, llamado has_a_living_ancestor , inicializado en FALSE para todos al principio. Al nacer, x.has_a_living_ancestor se establecerá en x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor . Entonces, para la mayoría de la gente (pero no para todos), esto se establecerá en VERDADERO al nacer.

El desafío es identificar ocasiones en las que has_a_living_ancestor se puede establecer en FALSE. Cada vez que nace una persona, hacemos un DFS a través de los antepasados, pero solo aquellos ancestros para los cuales ancestor.has_a_living_ancestor || ancestor.is_alive ancestor.has_a_living_ancestor || ancestor.is_alive es verdadero.

Durante ese DFS, si encontramos un ancestro que no tiene antepasados vivos, y ahora está muerto, entonces podemos establecer has_a_living_ancestor en FALSE. Esto significa, creo, que a veces has_a_living_ancestor estará desactualizado, pero con suerte se detectará rápidamente.

El siguiente es un algoritmo O (n log n) que funciona para gráficos en los que cada hijo tiene como máximo un padre (EDITAR: este algoritmo no se extiende al caso de dos padres con rendimiento O (n log n)). Vale la pena señalar que creo que el rendimiento se puede mejorar a O (n log (etiqueta de nivel máximo)) con trabajo adicional.

Un caso principal:

Para cada nodo x, en orden topológico inverso, cree un árbol de búsqueda binaria T_x que aumente estrictamente tanto en fecha de nacimiento como en número de generaciones eliminadas de x. (T_x contiene el primogénito c1 en el subgráfico del linaje de ascendencia enraizado en x, junto con el siguiente hijo nacido más antiguo c2 en este subgráfico, de modo que el "nivel de gran abuelo" de c2 es estrictamente mayor que el de c1, junto con el próximo niño nacido más antiguo c3 en este subgráfico de modo que el nivel de c3 sea estrictamente mayor que el de c2, etc.) Para crear T_x, fusionamos los árboles previamente construidos T_w donde w es un niño de x (están construidos previamente porque nosotros están iterando en orden topológico inverso).

Si tenemos cuidado con la forma en que realizamos las fusiones, podemos demostrar que el costo total de tales fusiones es O (n log n) para todo el gráfico de ascendencia. La idea clave es observar que después de cada fusión, como máximo, un nodo de cada nivel sobrevive en el árbol fusionado. Asociamos con cada árbol T_w un potencial de h (w) log n, donde h (w) es igual a la longitud del camino más largo desde w a una hoja.

Cuando fusionamos los árboles secundarios T_w para crear T_x, ''destruimos'' todos los árboles T_w, liberando todo el potencial que almacenan para su uso en la construcción del árbol T_x; y creamos un nuevo árbol T_x con potencial (log n) (h (x)). Por lo tanto, nuestro objetivo es gastar como máximo O ((log n) (sum_w (h (w)) - h (x) + constante)) tiempo para crear T_x de los árboles T_w para que el costo amortizado de la fusión sea solo O (log n). Esto se puede lograr eligiendo el árbol T_w tal que h (w) sea máximo como punto de partida para T_x y luego modifique T_w para crear T_x. Después de hacer una elección de T_x, fusionamos cada uno de los otros árboles, uno por uno, en T_x con un algoritmo que es similar al algoritmo estándar para unir dos árboles de búsqueda binarios.

Esencialmente, la fusión se logra iterando sobre cada nodo y en T_w, buscando el predecesor z de y por fecha de nacimiento, y luego insertando y en T_x si se eliminan más niveles de x que z; luego, si z se insertó en T_x, buscamos el nodo en T_x del nivel más bajo que es estrictamente mayor que el nivel de z, y empalmamos los nodos intermedios para mantener el invariante que T_x está ordenado estrictamente tanto por fecha de nacimiento como por nivel. Esto cuesta O (log n) para cada nodo en T_w, y hay como máximo O (h (w)) nodos en T_w, por lo que el costo total de fusionar todos los árboles es O ((log n) (sum_w (h (w) ))), sumando todos los niños w, excepto el niño w ''tal que h (w'') es máxima.

Almacenamos el nivel asociado con cada elemento de T_x en un campo auxiliar de cada nodo en el árbol. Necesitamos este valor para que podamos calcular el nivel real de x una vez que hemos construido T_x. (Como detalle técnico, en realidad almacenamos la diferencia del nivel de cada nodo con la de su padre en T_x para que podamos incrementar rápidamente los valores para todos los nodos en el árbol. Este es un truco BST estándar).

Eso es. Simplemente notamos que el potencial inicial es 0 y el potencial final es positivo, por lo que la suma de los límites amortizados es un límite superior en el costo total de todas las fusiones en todo el árbol. Encontramos la etiqueta de cada nodo x una vez que creamos el BST T_x mediante la búsqueda binaria del último elemento en T_x que nació antes de que x muriera al costo O (log n).

Para mejorar el límite de O (n log (etiqueta de nivel máximo)), puede fusionar los árboles de forma diferida, fusionando solo los primeros elementos del árbol según sea necesario para proporcionar la solución para el nodo actual. Si usas una BST que explota la localidad de referencia, como un árbol desplegable, entonces puedes lograr el límite anterior.

Afortunadamente, el algoritmo y el análisis anteriores son al menos lo suficientemente claros como para seguirlos. Simplemente comente si necesita alguna aclaración.

Mi sugerencia:

Además de los valores descritos en el enunciado del problema, cada registro personal tendrá dos campos: contador infantil y un vector dinámicamente creciente (en sentido C ++ / STL) que mantendrá el primer cumpleaños en cada generación de descendientes de una persona.
use una tabla hash para almacenar los datos, con el nombre de la persona como clave. El tiempo para construirlo es lineal (asumiendo una buena función hash, el mapa ha amortizado el tiempo constante para inserciones y hallazgos).
para cada persona, detectar y guardar la cantidad de hijos. También se realiza en tiempo lineal: para cada registro personal, busque el registro de sus padres e incremente sus contadores. Este paso se puede combinar con el anterior: si no se encuentra un registro para un padre, se crea y se agrega, mientras que los detalles (fechas, etc.) se agregarán cuando se encuentren en la entrada.
atraviesa el mapa y coloca referencias a todos los registros personales sin hijos en una cola. Todavía O(N) .
para cada elemento sacado de la cola:
- agrega el cumpleaños de esta persona en descendant_birthday[0] para ambos padres (crece ese vector si es necesario). Si este campo ya está configurado, cámbielo solo si la nueva fecha es anterior.
- Para todas las fechas descendant_birthday[i] disponibles en el vector del registro actual, siga la misma regla que la anterior para actualizar descendant_birthday[i+1] en los registros de los padres.
- disminuir los contadores de hijos de padres; si llega a 0, agregue el registro del padre correspondiente en la cola.
- el costo de este paso es O(C*N) , siendo C el mayor valor de "profundidad familiar" para la entrada dada (es decir, el tamaño del vector descendant_birthday cumpleaños más largo). Para datos realistas, puede limitarse con una constante razonable sin pérdida de corrección (como ya se señaló), y por lo tanto no depende de N.
recorrer el mapa una vez más, y "etiquetar a cada persona" con el mayor i para el cual descendant_birthday[i] todavía es anterior a la fecha de defunción; también O(C*N) .

Por lo tanto, para obtener datos realistas, la solución para el problema se puede encontrar en tiempo lineal. Aunque para datos artificiales como los sugeridos en el comentario de @tilly, C puede ser grande, e incluso del orden de N en casos degenerados. Se puede resolver poniendo un límite en el tamaño del vector o extendiendo el algoritmo con el paso 2 de la solución de @tilly.

Una tabla hash es una parte clave de la solución en caso de que las relaciones entre padres e hijos en los datos de entrada se proporcionen a través de nombres (como está escrito en la declaración del problema). Sin hashes, se requeriría O(N log N) para construir un gráfico de relaciones. La mayoría de las demás soluciones sugeridas parecen suponer que el gráfico de relaciones ya existe.

Pensé en esto esta mañana y luego descubrí que @Alexey Kukanov tenía pensamientos similares. Pero el mío está más desarrollado y tiene algo más de optimización, así que lo publicaré de todos modos.

Este algoritmo es O(n * (1 + generations)) y funcionará para cualquier conjunto de datos. Para datos realistas, esto es O(n) .

Ejecute todos los registros y genere objetos que representen personas que incluyan fecha de nacimiento, enlaces a padres y enlaces a niños, y muchos más campos no inicializados. (Hora de la última muerte entre uno mismo y antepasados, y una serie de fechas en las que tuvieron 0, 1, 2 ... generaciones sobrevivientes).
Repase a todas las personas y recursivamente encuentre y almacene la hora de la última muerte. Si llama a la persona nuevamente, devuelva el registro memorado. Para cada persona puede encontrar a la persona (necesitando calcularla), y puede generar 2 llamadas más a cada padre la primera vez que la calcule. Esto da un total de O(n) trabajo para inicializar estos datos.
Revise a todas las personas y recursivamente genere un registro de cuándo agregaron una generación por primera vez. Estos registros solo necesitan ir al máximo cuando la persona o su último antepasado murieron. Es O(1) para calcular cuándo tenía 0 generaciones. Luego, para cada llamada recursiva a un niño, debe hacer O(generations) para fusionar los datos de ese niño con los suyos. Se llama a cada persona cuando las encuentra en la estructura de datos, y se puede llamar una vez de cada padre para O(n) llamadas y el gasto total O(n * (generations + 1)) .
Repase a todas las personas y descubra cuántas generaciones vivieron al morir. Esto es nuevamente O(n * (generations + 1)) si se implementa con un escaneo lineal.

La suma total de todas estas operaciones es O(n * (generations + 1)) .

Para conjuntos de datos realistas, este será O(n) con una constante bastante pequeña.

Recientemente implementamos el módulo de relación en uno de nuestros proyectos en el que teníamos todo en la base de datos y sí, creo que el algoritmo fue mejor 2nO (m) (m es el factor de bifurcación máximo). Multiplicé las operaciones dos veces a N porque en la primera ronda creamos un gráfico de relaciones y en la segunda ronda visitamos a cada Persona. Hemos almacenado una relación bidireccional entre cada dos nodos. Mientras navegas, solo usamos una dirección para viajar. Pero tenemos dos series de operaciones, una transversal solo para niños, otra transversal solo para padres.

Person{ String Name; // all relations where // this is FromPerson Relation[] FromRelations; // all relations where // this is ToPerson Relation[] ToRelations; DateTime birthDate; DateTime? deathDate; } Relation { Person FromPerson; Person ToPerson; RelationType Type; } enum RelationType { Father, Son, Daughter, Mother }

Este tipo de gráfico parece bidireccional. Pero en este caso, primero compila la lista de todas las personas, y luego puede construir relaciones de lista y configurar FromRelations y ToRelations entre cada nodo. Entonces, todo lo que tiene que hacer es, para cada persona, solo navegar por las relaciones de tipo (hijo, hija) solamente. Y dado que tienes una cita, puedes calcular todo.

No tengo tiempo para verificar la corrección del código, pero esto te dará una idea de cómo hacerlo.

void LabelPerson(Person p){ int n = GetLevelOfChildren(p, p.birthDate, p.deathDate); // label based on n... } int GetLevelOfChildren(Person p, DateTime bd, DateTime? ed){ List<int> depths = new List<int>(); foreach(Relation r in p.ToRelations.Where( x=>x.Type == Son || x.Type == Daughter)) { Person child = r.ToPerson; if(ed!=null && child.birthDate <= ed.Value){ depths.Add( 1 + GetLevelOfChildren( child, bd, ed)); }else { depths.Add( 1 + GetLevelOfChildren( child, bd, ed)); } } if(depths.Count==0) return 0; return depths.Max(); }

Tengo la corazonada de que obtener para cada persona un mapeo (generación -> fecha en que nazca el primer descendiente en esa generación) ayudaría.

Dado que las fechas deben ser estrictamente crecientes, podríamos utilizar la búsqueda binaria (o una estructura de datos ordenada) para encontrar el descendiente vivo más distante en el tiempo O (log n).

El problema es que fusionar estas listas (al menos ingenuamente) es O (número de generaciones) por lo que podría llegar a ser O (n ^ 2) en el peor de los casos (considera A y B son padres de C y D, que son padres de E y F ...).

Todavía tengo que averiguar cómo funciona el mejor caso e intentar identificar mejor los peores casos (y ver si hay una solución para ellos)

Actualización : Esta no es la mejor solución que he encontrado, pero la dejé porque hay muchos comentarios relacionados con ella.

Tienes un conjunto de eventos (nacimiento / muerte), estado parental (sin descendencia, padre, abuelo, etc.) y estado vital (vivo, muerto).

Almacenaba mis datos en estructuras con los siguientes campos:

mother father generations is_alive may_have_living_ancestor

Ordene sus eventos por fecha y luego, para cada evento, tome uno de los siguientes dos cursos de lógica:

Birth: Create new person with a mother, father, 0 generations, who is alive and may have a living ancestor. For each parent: If generations increased, then recursively increase generations for all living ancestors whose generations increased. While doing that, set the may_have_living_ancestor flag to false for anyone for whom it is discovered that they have no living ancestors. (You only iterate into a person''s ancestors if you increased their generations, and if they still could have living ancestors.) Death: Emit the person''s name and generations. Set their is_alive flag to false.

El peor caso es O(n*n) si todos tienen muchos antepasados vivos. Sin embargo, en general tiene el paso de preproceso de clasificación que es O(n log(n)) y luego es O(n * avg no of living ancestors) que significa que el tiempo total tiende a ser O(n log(n)) en la mayoría de las poblaciones. (No conté correctamente la prestep de clasificación, gracias a @Alexey Kukanov por la corrección).

Hay un algoritmo relativamente sencillo de O (n log n) que barre los eventos cronológicamente con la ayuda de un árbol superior adecuado.
Realmente no deberías asignar tareas que no puedas resolver tú mismo.