Arbre De La Famille De L'Algorithme

Question

Je suis en train de travailler sur la mise sur pied d'un ensemble de problèmes pour une intro au niveau de CS, cours et est venu avec une question qui, sur la surface, semble très simple:

On vous a donné une liste de personnes avec les noms de leurs parents, de leurs dates de naissance, et la mort de leurs dates. Vous êtes intéressé à trouver qui, à un certain moment dans leur vie, était un parent, un grand-parent, un grand-parent, etc. Concevoir un algorithme pour l'étiquette de chaque personne avec cette information comme un entier (0 signifie que la personne n'a jamais eu un enfant, à 1 signifie que la personne est un parent, 2 signifie que la personne a été un des grands-parents, etc.)

Pour plus de simplicité, vous pouvez supposer que la famille de graphe est un DAG dont la version non orienté est un arbre.

Le défi intéressant ici, c'est que vous ne pouvez pas il suffit de regarder la forme de l'arbre pour déterminer cette information. Par exemple, j'ai 8 arrière-arrière-grand-grands-parents, mais depuis aucun d'entre eux étaient encore en vie quand je suis né, au cours de leur vie, aucun d'entre eux étaient des arrière-arrière-grand-grands-parents.

Le meilleur algorithme que je peux venir avec ce problème s'exécute en temps O(n²), où n est le nombre de personnes. L'idée est simple: lancer une DFS de chaque personne, de trouver le plus loin descendant vers le bas dans l'arbre de la famille qui est née avant que la personne date de la mort. Cependant, je suis assez sûr que ce n'est pas la solution optimale pour le problème. Par exemple, si le graphe est juste deux parents et de leurs enfants n, alors le problème peut être résolu de façon triviale en O(n). Ce que j'espère c'est un algorithme qui est beats O(n²), ou dont l'exécution est paramétrée sur la forme du graphique qui le rend rapide pour l'échelle des graphiques avec une dégradation progressive de O(n²) dans le pire des cas.

Des idées?

Merci!

Answer 1

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 disposez d'un ensemble d'événements (naissance/mort), parentale état (pas de descendants, parents, grands-parents, etc) et de la vie de l'état (vivant, mort).

Je voudrais stocker 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 de la vie des ancêtres. Cependant, en général vous avez le tri de l'étape de prétraitement qui est O(n log(n)) , et puis vous êtes O(n * avg no of living ancestors) ce qui signifie que la durée totale tend à être O(n log(n)) dans la plupart des populations. (Je n'ai pas compté le tri prestep correctement, grâce à @Alexey Kukanov pour la correction.)

Answer 2

Je pensais à ça ce matin, alors constaté que @Alexey Kukanov eu des pensées similaires. Mais le mien est plus étoffé et plus de l'optimisation, donc je vais le poster quand même.

Cet algorithme est - O(n * (1 + generations)), et va travailler pour tout jeu de données. Pour des données réalistes c'est - O(n).

1. Courir à travers tous les records et de générer des objets représentant des personnes qui comprennent la date de naissance, liens de parents, et des liens vers les enfants, et plusieurs non initialisée champs. (L'heure de la dernière mort entre soi et les ancêtres, et un tableau de dates qu'ils ont 0, 1, 2, ... survivants des générations.)
2. Passer par toutes les personnes et de manière récursive trouver et stocker l'heure de la dernière mort. Si vous appelez la personne à nouveau, de retour de la memoized enregistrement. Pour chaque personne, vous pouvez rencontrer la personne (besoin de la calculer), et peut générer plus de 2 appels à chaque parent la première fois que vous le calculer. Cela donne un total de O(n) de travail pour initialiser ces données.
3. Passer par toutes les personnes et de manière récursive générer un enregistrement de la première fois qu'ils ajouté une génération. Ces enregistrements seulement besoin d'aller au maximum lorsque la personne ou de leur dernier ancêtre est mort. C'est - O(1) pour calculer quand vous avez eu 0 générations. Ensuite, pour chaque appel récursif à un enfant que vous devez faire O(generations) travail à la fusion de l'enfant les données dans le vôtre. Chaque personne est appelée lorsque vous les rencontrez dans la structure de données, et peut être appelée une fois pour chaque parent pour O(n) des appels et des frais totaux O(n * (generations + 1)).
4. Passer par toutes les personnes et de comprendre comment de nombreuses générations étaient vivants à leur mort. C'est encore une fois O(n * (generations + 1)) si mis en œuvre avec une analyse linéaire.

La somme totale de toutes ces opérations est O(n * (generations + 1)).

Pour les réalistes, des ensembles de données, ce sera O(n) avec une assez petite constante.

Answer 3

Ma suggestion:

• en outre, les valeurs décrites dans l'énoncé du problème, chaque record a deux champs: l'enfant compteur et une croissance dynamique de vecteur (en C++/STL sens) qui tiendra le plus tôt anniversaire, à chaque génération, la descendance d'une personne.
• utiliser une table de hachage pour stocker les données, avec le nom de la personne étant la clé. Le temps pour le construire est linéaire (en supposant une bonne fonction de hachage, la carte a amorti de la constante de temps pour les insertions et les trouve).
• pour chaque personne, de détecter et d'enregistrer le nombre d'enfants. Il est également fait en temps linéaire: pour chaque dossier personnel, trouver l'enregistrement de ses parents et l'incrément de 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.
• parcourir la carte, et de mettre les références de tous les documents personnels sans enfants dans une file d'attente. Encore O(N).
• pour chaque élément de la file d'attente:
  • ajouter l'anniversaire de naissance de cette personne, en descendant_birthday[0] pour les deux parents (qui poussent 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 en cours, suivent la même règle que ci-dessus pour mettre à jour descendant_birthday[i+1] des parents des dossiers.
  • décrémenter des parents de l'enfant compteurs; si elle atteint 0, ajouter le parent correspondant de l'enregistrement dans la file d'attente.
  • le coût de cette étape est - O(C*N), avec C la plus grande valeur de la "famille" profondeur de la donnée d'entrée (c'est à dire la taille de la plus longue descendant_birthday vecteur). Pour des données réalistes, il peut être limitée par certaines raisonnable constante sans exactitude de la perte (comme d'autres l'a déjà souligné), et donc ne dépend pas de N.
• traverser la carte une fois de plus, et "l'étiquette de chaque personne" avec le plus grand i dont descendant_birthday[i] est encore plus tôt que la date de la mort; aussi O(C*N).

Ainsi, pour des données réalistes de la solution de ce problème peut être trouvée dans le temps linéaire. Si pour inventée de données comme suggéré dans @btilly commentaire, 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 couvercle sur la taille de vecteur ou par extension de l'algorithme à l'étape 2 de @btilly de la solution.

Une table de hachage est un élément clé de la solution dans le 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 hachages, il faudrait O(N log N) de construire une relation de graphe. La plupart des autres solutions proposées semblent supposer que la relation graphique existe déjà.

Answer 4

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, popping personnes à partir de ces listes, afin d'obtenir une liste des événements comme ils se sont produits.

Pour chaque Personne, de définir un is_alive champ. Ce sera FAUX pour tout le monde au premier abord. Que les gens naissent et meurent, mise à jour de cet enregistrement en conséquence.

Définir un autre champ pour chaque personne, has_a_living_ancestor, initialisé à FALSE pour tout le monde au premier abord. À la naissance, x.has_a_living_ancestor sera mis à l' x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor. Donc, pour la plupart des gens (mais pas tout le monde), ce sera la valeur TRUE à la naissance.

Le défi consiste à identifier les occasions lorsqu' has_a_living_ancestor peut être définie sur FALSE. Chaque fois qu'une personne est née, nous faisons un DFS en place par les ancêtres, mais seulement ceux ancêtres pour qui ancestor.has_a_living_ancestor || ancestor.is_alive est vrai.

Pendant que DFS, si nous trouvons un ancêtre qui n'a pas de vie ancêtres, et est maintenant mort, alors nous pouvons définir has_a_living_ancestor de FAUX. Cela signifie, je pense, que, parfois, has_a_living_ancestor sera hors de date, mais il faut espérer être pris rapidement.

Answer 5

Ce qui suit est un O(n log n) algorithme de travail pour les graphes dans laquelle chaque enfant a au plus un parent (EDIT: cet algorithme ne s'étend pas aux deux parents de cas avec O(n log n) de la performance). Il est intéressant de noter que, je crois, le rendement peut être amélioré à O(n log(niveau max de l'étiquette)) avec un supplément de travail.

Un parent cas:

Pour chaque nœud x, en sens inverse l'ordre topologique, créer un arbre de recherche binaire T_x que est strictement croissante à la fois dans la date de naissance et le nombre de générations retiré de x. (T_x contient le premier enfant né c1 dans le sous-graphe de l'ascendance graphe de racine x, ainsi que la suivante plus tôt né c2 dans ce sous-graphe tel que c2 "grande niveau des grands-parents' est strictement plus grande que celle de la c1, avec la prochaine premières né c3 dans ce sous-graphe tels que la c3 niveau est strictement plus grande que celle de c2, etc.) Pour créer T_x, nous fusionner précédemment construit des arbres T_w où w est un enfant de x (ils sont déjà construits, parce que nous sommes une itération inverse l'ordre topologique).

Si nous faisons attention à la façon dont nous effectuons les fusionne, on peut montrer que le coût total de ces fusions est O(n log n) pour l'ensemble de l'ascendance graphique. L'idée clé est à noter qu'après chaque fusion, tout au plus un nœud de chaque niveau survit dans la fusion de l'arbre. 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 à une feuille.

Lorsque nous fusionner les arbres de l'enfant T_w pour créer T_x, nous détruire ' tous les arbres de l'T_w, libérant tout le potentiel qu'ils stocker pour une utilisation dans la construction de l'arbre T_x; et nous créer une nouvelle arborescence T_x avec (log n)(h(x)) potentiel. Ainsi, notre objectif est de passer au plus O((log n)(sum_w(h(w)) - h(x) + constante), le temps de créer T_x des arbres T_w de sorte que le coût amorti de la fusion sera seulement O(log n). Ceci peut être réalisé en choisissant l'arbre T_w tels que h(w) est maximale en tant que point de départ pour T_x et puis de modifier T_w pour créer T_x. Après un tel choix est fait pour T_x, nous fusionner les uns des autres arbres, un par un, dans T_x avec un algorithme qui est similaire à l'algorithme de fusion de deux arbres binaires.

Essentiellement, la fusion est réalisée par une itération sur chaque nœud y en T_w, recherche pour y prédécesseur de z par date de naissance, et puis en insérant y en T_x si c'est plus de niveaux retiré de x de z; alors, si z a été inséré dans T_x, nous recherchons pour le nœud de T_x du niveau le plus bas qui est strictement plus grand que z est de niveau, et épissure hors de la période de nœuds pour maintenir l'invariant que T_x est commandé strictement à la fois par la date de naissance et le niveau. Cela coûte O(log n) pour chaque nœud dans T_w, et il y a au plus O(h(w)) les nœuds T_w, de sorte que le coût total de la fusion de tous les arbres est en O((log n)(sum_w(h(w))), sommation sur l'ensemble des enfants w sauf pour l'enfant du w' tel que h(w') est maximale.

Nous stockons le niveau associé à chaque élément de T_x dans les services auxiliaires de champ de chaque nœud dans l'arbre. Nous avons besoin de cette valeur, de sorte que nous pouvons déterminer le niveau réel de x une fois que nous avons construit T_x. (Comme un détail technique, nous avons effectivement le magasin de la différence de chaque nœud de niveau avec celle de son parent dans T_x afin que nous puissions rapidement incrémenter les valeurs pour tous les nœuds de l'arbre. C'est un standard BST truc.)

C'est tout. Nous indiquons simplement que le potentiel initial est 0 et la dernière potentiel est positif donc la somme de l'amorti limites est une limite supérieure sur le coût total de toutes les fusions dans l'ensemble de l'arbre. Nous trouver l'étiquette de chaque nœud x une fois que nous créons de la BST T_x en binaire de la recherche pour le dernier élément dans T_x qui est né avant le x est mort au coût O(log n).

Pour améliorer le liés à O(n log(niveau max de l'étiquette)), vous pouvez paresseusement fusionner les arbres, seulement de fusionner les premiers éléments de l'arbre qui est nécessaire pour fournir la solution pour le nœud actuel. Si vous utilisez un BST qui exploite la localité de référence, tel qu'un splay tree, vous pouvez profiter de la ci-dessus lié.

Heureusement, l'algorithme ci-dessus et l'analyse est au moins assez claire à suivre. Juste un commentaire si vous avez besoin d'une clarification.