Algorithme De L'Arbre Généalogique

mise à Jour: Ce n'est pas la meilleure solution je suis venu avec, mais je l'ai quitté parce qu'il ya tellement de nombreux commentaires s'y rapportant.

vous avez un ensemble d'événements (naissance/mort), l'état parental (pas de descendants, parent, grand-parent, etc) et l'état de vie (vivant, mort).

je stocke mes données dans des structures avec les champs suivants:

mother
father
generations
is_alive
may_have_living_ancestor

Trier les événements par date, puis pour chaque événement de prendre l'un des deux cours de logique:

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.

dans Le pire des cas O(n*n) si tout le monde a beaucoup d'ancêtres vivants. Cependant, en général, vous avez l'étape de tri prétraitement qui est O(n log(n)) vous êtes O(n * avg no of living ancestors) ce qui signifie que le temps total tend à être O(n log(n)) dans la plupart des populations. (Je n'avais pas compté correctement le prestep de tri, merci à @Alexey Kukanov pour la correction.)

ma suggestion:

• en plus des valeurs décrites dans l'énoncé du problème, chaque dossier personnel comportera deux champs: le compteur enfant et un vecteur croissant dynamiquement (au sens C++/STL) qui gardera l'anniversaire le plus tôt possible dans chaque génération de descendants d'une personne.
• utilisez une table de hachage pour stocker les données, le nom de la personne étant la clé. Le temps de construction est linéaire (en supposant une bonne fonction de hachage, la carte a amorti le temps constant pour les insertions et les trouve).
• pour chaque personne, détecter et sauver le nombre d'enfants. C'est aussi fait en temps linéaire: pour chaque dossier personnel, trouver le dossier pour ses parents et incrémenter leurs compteurs. Cette étape peut être combinée avec la précédente: si un enregistrement pour un parent n'est pas trouvé, il est créé et ajouté, tandis que les détails (dates, etc) seront ajoutées lors de trouve dans l'entrée.
• parcourez la carte, et mettez des références à tous les dossiers personnels sans enfants dans file. Encore O(N).
• pour chaque élément de la file d'attente:
  • ajouter l'anniversaire de naissance de cette personne dans descendant_birthday[0] pour les deux parents (cultivez ce vecteur si nécessaire). Si ce champ est déjà défini, le changer seulement si la nouvelle date est antérieure.
  • pour tous descendant_birthday[i] dates disponibles dans le vecteur de l'enregistrement courant, suivre la même règle que ci-dessus pour mettre à jour descendant_birthday[i+1] dans les dossiers des parents.
  • les compteurs d'enfants des parents décrémentants; si elle atteint 0, ajouter l'enregistrement correspondant du parent dans la file d'attente.
  • le coût de cette étape est O(C*N), C étant la plus grande valeur de "profondeur de la famille" pour l'input donné (i.e. la taille de la plus longue descendant_birthday vecteur). Pour des données réalistes il peut être plafonné par une certaine constante raisonnable sans perte de justesse (comme d'autres l'ont déjà souligné), et donc ne dépend pas de N.
• parcourir la carte une fois de plus, et "étiqueter chaque personne" avec le plus grand i pour descendant_birthday[i] est toujours antérieur à la date de décès; aussi O(C*N).

ainsi pour des données réalistes la solution du problème peut être trouvée dans le temps linéaire. Bien que pour les données inventées comme suggéré dans le commentaire de @btilly, C peut être grand, et même de l'ordre de N dans les cas dégénérés. Il peut être résolu en mettant un cap sur la taille du vecteur ou en étendant l'algorithme avec l'étape 2 de la solution de @btilly.

Une table de hachage est un élément clé de la solution au cas où si les relations parent-enfant dans les données d'entrée sont fournis par des noms (comme écrit dans l'énoncé du problème). Sans hashs, il faudrait O(N log N) pour construire un rapport de graphique. La plupart des autres solutions proposées semblent supposer que le graphique des relations existe déjà.

Créer une liste de personnes, triés par birth_date. Créer une autre liste de personnes, triés par death_date. Vous pouvez voyager logiquement à travers le temps, en détachant des personnes de ces listes, afin d'obtenir une liste des événements au fur et à mesure qu'ils se sont produits.

pour chaque personne, définissez un is_alive champ. Ce sera faux pour tout le monde au début. Comme les gens naissent et meurent, mettez à jour ce dossier en conséquence.

définissez un autre champ pour chaque personne, appelé has_a_living_ancestor, initialisé à FALSE for tout le monde au premier abord. À la naissance, x.has_a_living_ancestor sera réglé à x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor. Ainsi, pour la plupart des gens (mais pas pour tout le monde), cela se réalisera à la naissance.

le défi consiste à identifier les occasions où has_a_living_ancestor peut être défini à FALSE. Chaque fois qu'une personne est née, nous faisons une FDS à travers les ancêtres, mais seulement les ancêtres pour lesquels ancestor.has_a_living_ancestor || ancestor.is_alive est vraie.

pendant cette DFS, si nous trouvons un ancêtre qui n'a pas d'ancêtres vivants, et qui est maintenant mort, alors nous pouvons mettre has_a_living_ancestor à FALSE. Ce signifie, je pense, que, parfois,has_a_living_ancestor sera périmé, mais on espère le rattraper rapidement.

ce qui suit est un algorithme O(N log n) qui fonctionne pour les graphiques dans lesquels chaque enfant a au plus un parent (éditer: cet algorithme ne s'étend pas au cas de deux parents avec O(N log n) performance). Il est intéressant de noter que je crois que la performance peut être améliorée à O(N log(max level label)) avec du travail supplémentaire.

cas d'un parent:

pour chaque noeud x, dans l'ordre topologique inverse, créer un arbre de recherche binaire T_x qui augmente strictement les deux dans date de naissance et nombre de générations enlevées de X. (T_x contient le premier enfant c1 dans le sous-graphe du Graphe de l'ascendance enraciné à x, ainsi que le premier enfant c2 suivant dans ce sous-graphe tel que le "grand-parent niveau" de c2 est un Strictement plus grand que celui de c1, avec le premier enfant suivant c3 dans ce sous-graphe tel que le niveau de c3 est strictement plus grand que celui de c2, etc.) Pour créer T_x, nous fusionnons les arbres t_w construits précédemment où w est un enfant de x (ils sont construits précédemment parce que nous itérons dans l'ordre topologique inverse).

si nous faisons attention à la façon dont nous réalisons les fusions, nous pouvons montrer que le coût total de ces fusions est O(N log n) Pour l'ensemble du graphique d'ascendance. L'idée clé est de noter qu'après chaque fusion, au plus un noeud de chaque niveau survit dans l'arbre fusionné. Nous associons à chaque arbre T_w un potentiel de h(w) log n, où h(w) est égale à la longueur du plus long chemin de w pour une feuille.

lorsque nous fusionnons les arbres enfants T_w pour créer T_x, nous' détruisons ' tous les arbres T_w, libérant tout le potentiel qu'ils emmagasinent pour l'utiliser dans la construction de L'arbre T_x; et nous créons un nouvel arbre T_x avec (log n)(h(x)) le potentiel. Ainsi, notre objectif est de passer tout au plus O((log n)(sum_w(h(w)) - h(x) + constant)) temps pour créer T_x à partir des arbres T_w de sorte que le coût amorti de la fusion sera seulement O(log n). Cela peut être réalisé en choisissant l'arbre T_w de telle sorte que h(w) est maximale comme point de départ pour T_x et ensuite modifier T_w pour créer T_x. Après qu'un tel choix est fait pour T_x, nous fusionnons chacun des autres arbres, un par un, dans T_x avec un algorithme qui est similaire à l'algorithme standard pour fusionner deux arbres de recherche binaires.

essentiellement, la fusion est réalisée en itérant sur chaque noeud y dans T_w, en recherchant le prédécesseur de y z par date de naissance, puis en insérant y dans T_x si elle est plus de niveaux supprimés de x que z; puis, si z a été inséré dans T_x, nous recherchons le noeud dans T_x du niveau le plus bas qui est strictement supérieur au niveau de z, et nous séparons les noeuds intermédiaires pour maintenir l'invariant que T_x est ordonné strictement à la fois par la date de naissance et le niveau. Cela coûte O (log n) pour chaque noeud dans T_w, et il y a au plus O(h(w)) les noeuds dans T_w, de sorte que le coût total de la fusion de tous les arbres est O((log n) (sum_w(h(w))), sommant sur tous les enfants w sauf pour l'enfant w' tel que h(w') est maximale.

Nous stockons le niveau associé à chaque élément de T_x dans un champ auxiliaire de chaque noeud de l'arbre. Nous avons besoin de cette valeur pour pouvoir calculer le niveau réel de x une fois que nous aurons construit T_x. (Comme détail technique, nous stockons en fait la différence du niveau de chaque noeud avec celui de son parent dans T_x de sorte que nous pouvons rapidement incrémenter les valeurs pour tous les noeuds dans l'arbre. C'est un tour standard de la BST.)

c'est tout. Nous indiquons simplement que le potentiel initial est 0 et la dernière potentiel est positif de sorte que la somme des bornes amorties est une limite supérieure sur le coût total de toutes les fusions à travers l'arbre entier. Nous trouvons l'étiquette de chaque noeud x Une fois que nous créons le TSB T_x par recherche binaire pour le dernier élément dans T_x qui est né avant x est mort au coût O(log n).

pour améliorer la liaison à O (N log (étiquette de niveau max)), vous pouvez paresseusement fusionner les arbres, fusionnant seulement les premiers éléments de l'arbre comme nécessaire pour fournir la solution pour le noeud courant. Si vous utilisez une BST qui exploite la localité de référence, comme un arbre splay, alors vous pouvez atteindre la limite ci-dessus.

avec un peu de chance, l'algorithme et l'analyse ci-dessus sont au moins assez clairs pour suivre. Il suffit de commenter si vous avez besoin d'une clarification.

j'ai le pressentiment qu'obtenir pour chaque personne une carte (génération -> date de naissance du premier descendant dans cette génération) aiderait.

puisque les dates doivent être strictement croissantes, nous serions en mesure d'utiliser la recherche binaire (ou une structure de données soignée) pour trouver le descendant vivant le plus éloigné dans le temps O(log n).

le problème est que la fusion de ces listes (au moins naïvement) est O (nombre de générations) donc cela pourrait devenir O (N^2) dans le pire des cas (A et B sont les parents de C et D, qui sont les parents de E et F...).

j'ai encore à travailler sur la façon le meilleur des cas, de travaux et d'essayer d'identifier le pire des cas, la meilleure (et de voir si il y a une solution pour eux)

nous avons récemment implémenté le module relationship dans un de nos projets dans lequel nous avions tout dans la base de données et oui je pense que l'algorithme était le meilleur 2nO(m) (m est le facteur de branche max). J'ai multiplié les opérations deux fois à N parce que dans le premier tour nous créons le graphique de relation et dans le deuxième tour nous visitons chaque personne. Nous avons stocké relation bidirectionnelle entre deux nœuds. Pendant la navigation, nous n'utilisons qu'une seule direction pour voyager. Mais nous avons deux séries d'opérations, une traverse seulement les enfants, autre traverse parent seul.

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
}

ce type de ressemble à un graphe bidirectionnel. Mais dans ce cas, vous construisez d'abord la liste de toutes les personnes, et ensuite vous pouvez construire des relations de liste et setup À partir des relations et des relations entre chaque noeud. Alors tout ce que vous avez à faire est, pour chaque personne, vous devez naviguer seulement aux relations de type (Fils,Fille) seulement. Et puisque vous avez rendez-vous, vous pouvez tout calculer.

je n'ai pas le temps d'en vérifier l'exactitude du code, mais ce vous donnera idée de comment le faire.

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();
}

Voici mon coup de poignard:

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();

• il y a un algorithme O(N log n) relativement simple qui balaie les événements chronologiquement à l'aide d'un en haut de l'arbre.

• Vous ne devriez vraiment pas assigner des devoirs que vous ne pouvez pas résoudre vous-même.