家谱algorithm

我正在为一个介绍级别的CS课程设置一个问题，并提出了一个问题，表面上看起来很简单：

给你一个有父母姓名，出生date和死亡date的人名单。 你有兴趣找出在他们有生之年的某个时刻，他是一个父母，一个祖父母还是一个曾祖父母，等等。devise一个algorithm，把这个信息标记为一个整数（0表示这个人从来没有孩子，1表示该人是父母，2表示该人是祖父母等）

为了简单起见，您可以假设家族图是一个DAG，其无向版本是一棵树。

这里有趣的挑战是你不能只看树的形状来确定这个信息。 例如，我有八个曾祖父母，但是因为他们中没有一个在我出生的时候还活着，在他们有生之年，没有一个是曾祖父母。

我可以为这个问题提出的最好的algorithm运行时间O（n ² ），其中n是人的数量。 这个想法很简单 – 从每个人开始一个DFS，find在该人的死亡date之前出生的家族树中最远的后裔。 但是，我很确定这不是问题的最佳解决scheme。 例如，如果graphics只是两个父母和他们的n个孩子，那么问题可以在O（n）中平凡地解决。 我希望得到的是一些algorithm，要么是O（n ² ），要么是其运行时参数化的graphicsforms，使得宽图的速度快，而在最差的情况下，O（n ² ）案件。

Answer 1

我今天早上想到这个，然后发现@Alexey Kukanov有类似的想法。 但是我的更加充实，还有一些更多的优化，所以我会把它贴出来。

这个algorithm是O(n * (1 + generations)) ，并且适用于任何数据集。 对于实际的数据，这是O(n) 。

1. 遍历所有logging并生成代表人物的对象，其中包括出生date，父母的链接，以及儿童的链接，以及更多未初始化的字段。 （自我和祖先之间的最后一次死亡的时间，以及他们有0,1,2，……幸存下来的一系列date）。
2. 遍历所有人，recursion地查找和存储上次的死亡时间。 如果您再次致电该人，请返回logging。 对于每个人，你都可以遇到这个人（需要计算它），并且在你第一次计算的时候，可以给每个父母生成另外两个电话。 这给了总共O(n)工作来初始化这些数据。
3. 遍历所有人，并recursion地生成一个他们第一次添加一代的logging。 这些logging只需要在人或者他们的最后一个祖先去世时达到最大值。 计算你有0代的时候是O(1) 。 然后，对于每个recursion调用一个孩子，你需要做O(generations)工作来合并这个孩子的数据到你的。 当你在数据结构中遇到它们时，每个人都被调用，并且可以从每个父节点调用一次O(n)调用和总费用O(n * (generations + 1)) 。
4. 经过所有的人，并找出他们的死亡有多less世代。 如果用线性扫描来实现，这又是O(n * (generations + 1)) 。

所有这些操作的总和是O(n * (generations + 1)) 。

对于现实的数据集，这将是一个相当小的常数O(n) 。

Answer 2

更新 ：这不是我提出的最好的解决scheme，但我已经离开了，因为有这么多的意见。

你有一系列事件（出生/死亡），父母状态（没有后代，父母，祖父母等）和生活状态（活着，死亡）。

我将我的数据存储在以下字段的结构中：

 mother father generations is_alive may_have_living_ancestor 

按datesorting您的事件，然后为每个事件采取以下两种逻辑之一：

 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. 

如果每个人都有很多活着的祖先，最坏的情况是O(n*n) 。 然而，一般来说，你已经有了sorting预处理的步骤，它是O(n log(n)) ，然后你是O(n * avg no of living ancestors) ，这意味着总时间往往是O(n log(n))在大多数人口中。 （由于@Alexey Kukanov的更正，我没有正确地计算好分类的步骤。）

Answer 3

我的build议：

• 除了问题描述中所描述的值之外，每个个人logging都有两个字段：儿童计数器和一个dynamic增长的向量（C ++ / STL意义上的），它将在每一代人的后代中保留最早的生日。
• 使用散列表来存储数据，以人名为关键。 build立它的时间是线性的（假设一个好的散列函数，这个映射对于插入和查找具有分期固定的时间）。
• 为每个人检测并保存孩子的数量。 这也是以线性时间完成的：对于每个个人logging，find父母的logging并增加他们的计数器。 这个步骤可以和前一个步骤结合：如果找不到父logging，则会创build并添加logging，而在input中find详细信息（date等）。
• 遍历地图，并将没有孩子的所有个人logging引用到队列中。 还是O(N) 。
• 对于从队列中取出的每个元素：
  • 将这个人的生日添加到父母双方的descendant_birthday[0]中（如果需要，增加该生日）。 如果此字段已设置，请仅在新date较早时更改它。
  • 对于当前logging向量中的所有descendant_birthday[i]date，请按照与上述相同的规则更新父母logging中的descendant_birthday[i+1] 。
  • 减less父母的子女柜台; 如果达到0，则将相应的父logging添加到队列中。
  • 这个步骤的代价是O(C*N) ，其中C是给定input（即最长的descendant_birthday _ descendant_birthdayvector的大小）的“族深度”的最大值。 对于现实的数据，可以通过一些合理的常数来限制，而不会损失正确性（正如其他人已经指出的那样），所以不依赖于N.
• 再次遍历地图，并以“ descendant_birthday[i]的死亡date早于“ i ”最大的“ i ”来标记每个人; 也是O(C*N) 。

因此，对于实际的数据，可以在线性时间内find问题的解决scheme。 尽pipe在@ btilly的评论中提出的人为的数据，C可以是大的，甚至退化情况下的N的数量级。 它可以通过在vector大小上加上一个上限来解决，也可以用@ btilly解决scheme的第2步来扩展algorithm。

如果input数据中的父子关系是通过名称（如问题陈述中所写）提供的，则散列表是解决scheme的关键部分。 如果没有散列，则需要O(N log N)来构build一个关系图。 大多数其他build议的解决scheme似乎假定关系图已经存在。

Answer 4

根据birth_date创build一个人员列表。 创build另一个人列表，按death_datesorting。 您可以通过时间逻辑旅行，从这些列表中popup人物，以便获取发生的事件列表。

对于每个人，定义一个is_alive字段。 起初，这对每个人都是假的。 随着人的出生和死亡，相应地更新这个logging。

为每个人定义另一个字段，名为has_a_living_ancestor ，首先为每个人初始化为FALSE。 出生时， x.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 x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor 。 所以，对于大多数人（但不是每个人）来说，在出生时这将被设置为TRUE。

挑战是确定has_a_living_ancestor可以设置为FALSE的场合。 每当一个人出生时，我们通过祖先做DFS，但只有那些祖先为ancestor.has_a_living_ancestor || ancestor.is_alive ancestor.has_a_living_ancestor || ancestor.is_alive是真的。

在DFS期间，如果我们发现一个没有祖先的祖先，现在已经死了，那么我们可以设置has_a_living_ancestor为FALSE。 我认为这确实意味着，有时候has_a_living_ancestor会过时，但希望很快就会被抓住。

Answer 5

下面是一个O（n log n）algorithm，适用于每个子图最多只有一个父图的编辑器（编辑：此algorithm不会扩展到具有O（n log n）性能的双亲情况）。 值得注意的是，我相信可以通过额外的工作将性能提高到O（n log（max level label））。

一个父母的情况：

对于每个节点x，按照逆向拓扑顺序，创build一个二进制search树T_x，该树在出生date和从x中删除的代数中严格增加。 （T_x包含以x为根的祖先图的子图中的第一个出生的孩子c1以及该子图中的第二个最早出生的孩子c2，使得c2的“祖父辈级别”严格大于c1，这个子图中的下一个最早出生的孩子c3，使得c3的级别严格大于c2的级别等）。为了创buildT_x，我们合并了先前构build的树T_w，其中w是x的子元素（它们是先前构build的，因为我们以逆向拓扑顺序迭代）。

如果我们仔细考虑如何执行合并，我们可以certificate这种合并的总成本是整个祖先图的O（n log n）。 关键的想法是注意到在每次合并之后，每个级别的最多一个节点在合并的树中存活。 我们将每棵树T_w与h（w）log n的一个势相关联，其中h（w）等于从w到叶的最长path的长度。

当我们合并子树T_w来创buildT_x时，我们“销毁”所有树T_w，释放它们存储用于构build树T_x的所有潜力; 我们用（log n）（h（x））势创build一个新的树T_x。 因此，我们的目标是花费至多O（（log n）（sum_w（h（w）） – h（x）+ constant）时间从树T_w创buildT_x，以便合并的摊销成本将是只有O（log n）。 这可以通过select树T_w来实现，使得h（w）作为T_x的起始点是最大的，然后修改T_w来创buildT_x。 在对T_x进行了这样的select之后，我们将每个其他树一个接一个地合并到T_x中，其algorithm类似于合并两个二叉search树的标准algorithm。

本质上，合并是通过遍历T_w中的每个节点y，按照出生datesearchy的前辈z，然后将y插入到T_x中，如果它比x更多地从x中移除; 那么，如果将z插入到T_x中，我们search严格大于z水平的最低水平的T_x中的节点，并且将中间节点拼接以保持T_x严格按照出生date和水平sorting的不variables。 这在T_w中每个节点的成本为O（log n），T_w中最多有O（h（w））个节点，所以合并所有树的总成本为O（（log n）（sum_w（h（w ））），除了孩子w'，使得h（w'）是最大值的所有孩子的总和。

我们将与T_x的每个元素关联的级别存储在树中每个节点的辅助字段中。 我们需要这个值，这样一旦我们构造了T_x，我们就可以计算出x的实际水平。 （作为一个技术细节，实际上我们在T_x中存储每个节点的级别与其父级的差异，这样我们可以快速增加树中所有节点的值，这是一个标准的BST技巧。

而已。 我们简单地注意到，初始的潜力是0，最后的潜力是积极的，所以摊分边界的总和是整个树中所有合并的总成本的上限。 一旦我们创build了BST T_x，我们就find了每个节点x的标签，通过二进制search在x以成本O（log n）死亡之前出生的T_x中的最新元素。

为了改进对O（n log（最大级别标签））的绑定，可以懒惰地合并树，只根据需要合并树的前几个元素，为当前节点提供解决scheme。 如果使用引用局部性的BST（如splay树），则可以实现上述限制。

有希望的是，上面的algorithm和分析至less应该足够清晰。 只是评论，如果你需要任何澄清。

Answer 6

我有一个预感，为每个人获得一个映射（一代 – >约会在那一代的第一个后代诞生）将有所帮助。

由于date必须严格增加，我们可以使用二进制search（或一个整洁的数据结构）在O（log n）时间内find最遥远的后代。

问题是，合并这些列表（至less天真）是O（世代），所以在最坏的情况下这可能是O（n ^ 2）（考虑A和B是C和D的父母，他们是父母E和F …）。

我仍然需要研究最好的案例是如何工作的，并且试图找出最坏的案例（看看是否有解决方法）

Answer 7

我们最近在我们的项目中实现了关系模块，其中我们拥有数据库中的所有东西，是的，我认为algorithm最好是2nO（m）（m是最大分支因子）。 我把操作两次乘以N，因为第一轮我们创build关系图，第二轮我们访问每个人。 我们已经存储了每两个节点之间的双向关系。 在导航的时候，我们只用一个方向去旅行。 但是我们有两套操作，一个只能遍历子，另一个只能遍历父。

 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 } 

这种看起来像双向图。 但在这种情况下，首先build立所有Person的列表，然后可以build立列表关系并设置每个节点之间的FromRelations和ToRelations。 那么你所要做的就是，对于每一个人，你只需要导航ToRelationstypes（儿子，女​​儿）。 既然你有约会，你可以计算一切。

我没有时间检查代码的正确性，但是这会让你知道如何去做。

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

Answer 8

这是我的刺：

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

Answer 9

• 有一个相对简单的O（n log n）algorithm，可以在合适的顶层树的帮助下按时间顺序扫描事件。

• 你真的不应该分配你不能解决自己的功课。