家谱算法

Question

我正在努力为一个介绍级别的CS课程设置一个问题集,并提出一个问题,从表面上看,似乎很简单:

您将获得一份包含父母姓名,出生日期和死亡日期的人员名单.你有兴趣找出谁在他们一生中的某个时刻是父母,祖父母,曾祖父母等等.设计一个算法,用这个信息作为一个整数来标记每个人(0表示这个人从来没有过孩子,1表示该人是父母,2表示该人是祖父母,等等.)

为简单起见,您可以假设族图是DAG,其无向版本是树.

这里有趣的挑战是你不能只看树的形状来确定这些信息.例如,我有8位曾祖父母,但由于我们出生时没有一个人活着,在他们的一生中,他们中没有一个是伟大的曾祖父母.

我能解决这个问题的最佳算法是在时间O(n ²)中运行,其中n是人数.这个想法很简单 - 从每个人开始一个DFS,找到在该人死亡日期之前出生的家谱中最远的后代.但是,我很确定这不是问题的最佳解决方案.例如,如果图形只是两个父母及其n个孩子,那么问题可以在O(n)中平凡地解决.我希望的是一些算法要么胜过O(n ²),要么运行时参数化在图形的形状上,这使得它对于宽图形来说很快,在最坏的情况下优雅地降低到O(n ²)案件.

Answer 1

更新:这不是我提出的最佳解决方案,但我已经离开了,因为有很多与之相关的评论.

你有一系列事件(出生/死亡),父母状态(没有后代,父母,祖父母等)和生活状态(活着,死亡).

我会将我的数据存储在具有以下字段的结构中:

mother
father
generations
is_alive
may_have_living_ancestor

按日期对事件进行排序,然后对于每个事件,请执行以下两个逻辑过程之一:

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)如果每个人都有很多活着的祖先.然而,一般来说,你已经有了排序预处理步骤,O(n log(n))然后你就O(n * avg no of living ancestors)意味着总时间往往O(n log(n))在大多数人群中.(由于@Alexey Kukanov的修正,我没有正确计算排序前提.)

Answer 2

今天早上我想到了这一点,然后发现@Alexey Kukanov有类似的想法.但我的更充实,并有更多的优化,所以我会发布它无论如何.

该算法O(n * (1 + generations))适用于任何数据集.对于现实数据,这是O(n).

1. 运行所有记录并生成表示人员的对象,其中包括出生日期,父母的链接,子项链接以及其他几个未初始化的字段.(自我和祖先之间的最后一次死亡时间,以及他们有0,1,2,......幸存下来的一系列日期.)
2. 通过所有人并递归地查找和存储上次死亡的时间.如果再次呼叫此人,请返回已记录的记录.对于每个人,您可以遇到该人(需要计算它),并且可以在您第一次计算时为每个父母再生成2个呼叫.这提供了O(n)初始化此数据的总计工作.
3. 遍历所有人并递归地生成他们第一次添加一代时的记录.这些记录只需要在该人或其最后一位祖先去世时达到最大值.这是O(1)计算你有0代的时间.然后,对于每个孩子的递归调用,您需要做的O(generations)工作是将该子项的数据合并到您的子项中.当您在数据结构中遇到它们时,每个人都会被调用,并且可以从每个父项调用一次以进行O(n)调用和总费用O(n * (generations + 1)).
4. 通过所有人,弄清楚他们死后有多少代人活着.O(n * (generations + 1))如果使用线性扫描实现,则再次这样做.

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

对于实际数据集,这将是O(n)一个相当小的常量.

Answer 3

我的建议:

• 除了问题陈述中描述的值之外,每个个人记录还有两个字段:子计数器和动态增长的向量(在C++/STL意义上),它将在每个人的后代中保留最早的生日.
• 使用哈希表来存储数据,人名是密钥.构建它的时间是线性的(假设一个好的散列函数,映射已经为插入和查找分摊了恒定的时间).
• 为每个人,检测并保存孩子的数量.它也是在线性时间内完成的:对于每个个人记录,找到其父母的记录并增加他们的计数器.此步骤可以与前一步骤结合使用:如果未找到父级记录,则会创建并添加该记录,而在输入中找到时将添加详细信息(日期等).
• 遍历地图,并将没有子项的所有个人记录的引用放入队列中.还是O(N).
• 对于从队列中取出的每个元素:
  • descendant_birthday[0]为这两个父母添加这个人的生日(必要时增长该向量).如果已设置此字段,则仅在新日期较早时更改此字段.
  • 对于descendant_birthday[i]当前记录的向量中可用的所有日期,请遵循上述相同的规则以更新descendant_birthday[i+1]父记录.
  • 减少父母的子女柜台; 如果它达到0,则将相应的父记录添加到队列中.
  • 这一步的成本是O(C*N),C是给定输入的"族深度"的最大值(即最长descendant_birthday向量的大小).对于实际数据,它可以被一些合理的常数限制而没有正确性损失(正如其他已经指出的那样),因此不依赖于N.
• 穿越地图上一个更多的时间,而"标注每个人"用最大i的这descendant_birthday[i]仍然是早于死亡日期; 也O(C*N).

因此,对于实际数据,可以在线性时间内找到问题的解决方案.虽然对于@ btilly评论中提出的人为设计数据,C可能很大,甚至在退化情况下也可能是N的顺序.它可以通过在矢量大小上设置上限或通过@btilly解决方案的第2步扩展算法来解决.

如果输入数据中的父子关系是通过名称提供的(如问题陈述中所述),则哈希表是解决方案的关键部分.如果没有哈希,则需要O(N log N)构建关系图.大多数其他建议的解决方案似乎假设关系图已经存在.