首页 文章

家谱算法

提问于
浏览 次
45

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

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

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

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

我能解决这个问题的最佳算法是在时间O（n2）中运行，其中n是人数 . 这个想法很简单 - 从每个人开始一个DFS，找到在该人之前出生的家族树中最远的后代's death date. However, I'我非常确定这不是问题的最佳解决方案 . 例如，如果图形只是两个父母及其n个孩子，则问题可以在O（n）中平凡地解决 . 我希望的是一些算法要么胜过O（n2），要么运行时参数化在图形的形状上，这使得它对于在最坏情况下优雅降级到O（n2）的宽图表来说是快速的 .

algorithm graph tree family-tree

9 回答

  • 3

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

    此算法为 O(n * (1 + generations)) ，适用于任何数据集 . 对于实际数据，这是 O(n) .

    • 运行所有记录并生成表示人员的对象，其中包括出生日期，父母的链接，子项链接以及其他几个未初始化的字段 . （自我和祖先之间的最后一次死亡时间，以及他们有0,1,2，......幸存几代的一系列日期 . ）

    • 通过所有人并以递归方式查找并存储上次死亡的时间 . 如果再次呼叫此人，请返回已记录的记录 . 对于每个人，您可以遇到该人（需要计算它），并且在您第一次计算时可以为每个父母再生成2个呼叫 . 这总共提供了 O(n) 工作来初始化这些数据 .

    • 浏览所有人并递归生成他们第一次添加一代时的记录 . 这些记录只需要在该人或其最后一位祖先去世时达到最大值 . 当你有0代时计算 O(1) . 然后，对于每个递归调用的孩子，你需要做 O(generations) 工作将孩子的数据合并到你的 . 每个人在数据结构中遇到它们时都会被调用，并且可以从每个父项调用一次 O(n) 调用和总费用 O(n * (generations + 1)) .

    • 通过所有人，弄清楚他们死后有多少代人活着 . 如果使用线性扫描实现，则再次 O(n * (generations + 1)) .

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

    对于实际数据集，这将是 O(n) ，具有相当小的常量 .

    回复于
  • 3

    Update ：这不是我提出的最好的解决方案，但是我已经离开了，因为有很多评论与之相关 .

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

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

    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的纠正，我没有正确计算排序前提 . ）

    回复于
  • 0

    我的建议：

    除了问题陈述中描述的值之外，每个个人记录还有两个字段：子计数器和动态增长的向量（在C / STL意义上），它将在每个人的后代中保留最早的生日 .

    • 使用哈希表来存储数据，人名是密钥 . 构建它的时间是线性的（假设一个好的散列函数，映射已经为插入和查找分摊了恒定的时间） .

    • 为每个人，检测并保存孩子的数量 . 它也是在线性时间内完成的：对于每个个人记录，找到其父母的记录并增加他们的计数器 . 此步骤可以与前一步骤结合使用：如果未找到父级记录，则创建并执行此步骤添加，同时在输入中找到详细信息（日期等） .

    • 遍历 Map ，并将没有子项的所有个人记录的引用放入队列中 . 仍 O(N) .
      对于从队列中取出的每个元素，

    • ：

    • 为父母双方将这个人的生日添加到 descendant_birthday[0] （必要时增长该向量） . 如果已设置此字段，则仅在新日期较早时更改此字段 .

    • 对于当前记录向量中可用的所有 descendant_birthday[i] 日期，请遵循上述相同的规则更新父记录中的 descendant_birthday[i+1] .

    • 减少父母' child counters; if it reaches 0, add the corresponding parent'的记录进入队列 .

    • 此步骤的成本是 O(C*N) ，其中C是给定输入的最大值"family depth"（即最长 descendant_birthday 向量的大小） . 对于实际数据，它可以被一些合理的常数限制而没有正确性损失（正如其他已经指出的那样），因此不依赖于N.

    • 再次遍历 Map ，"label each person"最大 i ，其中 descendant_birthday[i] 仍然早于死亡日期;也 O(C*N) .

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

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

    回复于
  • 6

    创建一个人员列表，按 birth_date 排序 . 创建另一个人员列表，按 death_date 排序 . 您可以在逻辑上随时间旅行，从这些列表中弹出人员，以便在事件发生时获取事件列表 .

    对于每个Person，定义一个 is_alive 字段 . 这对每个人来说都是假的 . 当人们出生并死亡时，相应地更新此记录 .

    为每个人定义另一个字段，称为 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 . 因此，对于大多数人（但不是每个人），这将在出生时设置为TRUE .

    挑战是确定 has_a_living_ancestor 可以设置为FALSE的情况 . 每次一个人出生时，我们都会通过祖先进行DFS，但只有那些 ancestor.has_a_living_ancestor || ancestor.is_alive 为真的祖先 .

    在那个DFS期间，如果我们找到一个没有活着的祖先的祖先，并且现在已经死了，那么我们可以将 has_a_living_ancestor 设置为FALSE . 我认为，这确实意味着有时 has_a_living_ancestor 将会过时，但它有望很快被捕获 .

    回复于
  • 11

    以下是一个O（n log n）算法，该算法适用于每个子节点最多只有一个父节点的图形（编辑：此算法不会扩展到具有O（n log n）性能的双父案例） . 值得注意的是，我相信可以通过额外的工作将性能提高到O（n log（最大级别标签）） .

    One parent case:

    对于每个节点x，以反向拓扑顺序，创建二进制搜索树T_x，其严格地在出生日期和从x移除的世代数中增加 . （T_x包含以x为根的祖先图的子图中的第一个出生的孩子c1，以及该子图中下一个最早出生的孩子c2，使得c2的“大祖父母级别”严格大于c1的级别，以及这个子图中下一个最早出生的孩子c3，使得c3的水平严格大于c2的水平等 . ）为了创建T_x，我们合并先前构造的树T_w，其中w是x的子元素（它们之前是构造的，因为我们以反向拓扑顺序迭代） .

    如果我们小心我们如何执行合并，我们可以证明这种合并的总成本是整个祖先图的O（n log n） . 关键的想法是要注意，在每次合并之后，每个级别的最多一个节点在合并树中存活 . 我们将每个树T_w与h（w）log n的电势相关联，其中h（w）等于从w到叶子的最长路径的长度 .

    当我们合并子树T_w以创建T_x时，我们“销毁”所有树T_w，释放它们存储的所有潜力以用于构建树T_x;我们用（log n）（h（x））势创建一个新的树T_x . 因此，我们的目标是花费最多O（（log n）（sum_w（h（w）） - h（x）常数））时间从树T_w创建T_x，以便合并的摊销成本仅为O（log n） . 这可以通过选择树T_w使得h（w）最大作为T_x的起始点然后修改T_w以创建T_x来实现 . 在对T_x做出这样的选择之后，我们将每个其他树一个接一个地合并到T_x中，其算法类似于用于合并两个二叉搜索树的标准算法 .

    本质上，合并是通过迭代完成的在T_w中的每个节点y上，按出生日期搜索y的前任z，然后如果从x除去更多级别，则将y插入T_x;然后，如果z被插入到T_x中，我们在T_x中搜索严格大于z的级别的最低级别的节点，并拼接出中间节点以保持T_x严格按出生日期和级别排序的不变量 . 这花费了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且最终潜力为正，因此摊销边界的总和是整个树中所有合并的总成本的上限 . 一旦我们通过二进制搜索T_x中的最新元素创建BST T_x，我们找到每个节点的标签x，该元素在x死于成本O（log n）之前出生 .

    要改进O（n log（最大级别标签））的绑定，您可以懒惰地合并树，只需根据需要合并树的前几个元素，以便为当前节点提供解决方案 . 如果您使用利用引用局部性的BST，例如展开树，那么您可以实现上述限制 .

    希望上述算法和分析至少足够明确 . 如果您需要任何澄清，请发表评论 .

    回复于
  • 5

    我有一种预感，即为每个人获得一个映射（生成 - >那一代中第一个后代诞生的日期）会有所帮助 .

    由于日期必须严格增加，我们将能够使用二进制搜索（或整齐的数据结构）在O（log n）时间内找到最远的生活后代 .

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

    我仍然需要弄清楚最好的情况如何工作，并尝试更好地识别最坏的情况（并查看是否有解决方法）

    回复于
  • -2

    我们最近在我们的一个项目中实现了关系模块，其中我们拥有数据库中的所有内容，是的，我认为算法最好2nO（m）（m是最大分支因子） . 我将操作乘以两次到N，因为在第一轮中我们创建关系图，在第二轮中我们访问每个人 . 我们在每两个节点之间存储了双向关系 . 在导航时，我们只使用一个方向来旅行 . 但是我们有两组操作，一组是遍历子项，另一组是遍历父项 .

    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
}

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

    我没有时间检查代码的正确性，但这会让你知道如何做到这一点 .

    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();
}
    回复于
  • 2

    这是我的刺：

    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();
    回复于
  • 2

    • 有一个相对简单的O（n log n）算法，它可以在合适的top tree的帮助下按时间顺序扫描事件 .

    • 你真的不应该分配你自己无法解决的作业 .

    回复于

相关问题