46

我正在为入门级 CS 课程整理一个问题集，并提出了一个表面上看起来非常简单的问题：

你会得到一份名单，上面有他们父母的姓名、出生日期和死亡日期。你有兴趣找出谁在他们一生中的某个时刻是父母、祖父母、曾祖父母等。设计一个算法，用这个信息将每个人标记为一个整数（0 表示这个人从来没有孩子，1 表示此人是父母，2 表示此人是祖父母，以此类推）

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

这里有趣的挑战是你不能只看树的形状来确定这些信息。例如，我有 8 个曾曾祖父母，但由于我出生时他们都不在世，所以在他们的有生之年，他们都不是曾曾祖父母。

对于这个问题，我能想出的最佳算法运行时间为 O(n 2 )，其中 n 是人数。这个想法很简单——从每个人开始一个 DFS，在该人死亡日期之前出生的家谱中找到最远的后代。但是，我很确定这不是问题的最佳解决方案。例如，如果图只是两个父母和他们的 n 个孩子，那么问题可以在 O(n) 中轻松解决。我希望的是某种算法，它要么优于 O(n 2 )，要么其运行时间在图形的形状上被参数化，这使得它对于宽图快速，在最坏的情况下优雅地降级到 O(n 2 ) -案子。

4

9 回答 9

11

更新：这不是我想出的最佳解决方案，但我留下了它，因为有很多与它相关的评论。

您有一组事件（出生/死亡）、父母状态（没有后代、父母、祖父母等）和生命状态（活着、死去）。

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

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 的更正，我没有正确计算排序前的步骤。）

于 2011-05-23T20:07:20.453 回答
8

我今天早上想到了这个，然后发现@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)一个相当小的常数。

于 2011-05-26T16:53:11.927 回答
5

我的建议：

  • 除了问题陈述中描述的值之外，每个个人记录将有两个字段：子计数器和一个动态增长的向量（在 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)构建关系图。大多数其他建议的解决方案似乎都假设关系图已经存在。

于 2011-05-26T13:14:25.023 回答
3

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

对于每个人，定义一个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会过时，但希望很快就会被抓住。

于 2011-05-23T22:37:04.810 回答
3

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

一位家长案例：

对于每个节点 x，以相反的拓扑顺序，创建一个二叉搜索树 T_x，它的出生日期和从 x 中删除的代数都严格增加。（T_x 包含以 x 为根的祖先图的子图中的第一个出生的孩子 c1，以及该子图中的下一个最早出生的孩子 c2，因此 c2 的“曾祖父母级别”a 严格大于 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) + constant)) 时间从树 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 中删除的级别多于 z，则将 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' 之外的所有子 w 求和，使得 h(w') 最大。

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

就是这样。我们只是注意到初始潜力为 0，最终潜力为正，因此摊销边界的总和是整个树中所有合并总成本的上限。一旦我们通过对 T_x 中在 x 以成本 O(log n) 死亡之前出生的最新元素进行二进制搜索来创建 BST T_x，我们就会找到每个节点 x 的标签。

为了提高对 O(n log(max level label)) 的限制，您可以延迟合并树，仅根据需要合并树的前几个元素，以便为当前节点提供解决方案。如果您使用利用局部引用的 BST，例如 splay 树，则可以实现上述界限。

希望上述算法和分析至少足够清晰，可以遵循。如果您需要任何澄清，请发表评论。

于 2011-05-30T05:32:20.223 回答
2

我有一种预感，为每个人获取一个映射（世代->该世代中第一个后代出生的日期）会有所帮助。

由于日期必须严格递增，我们可以使用二进制搜索（或简洁的数据结构）在 O(log n) 时间内找到最远的后代。

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

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

于 2011-05-25T21:14:16.293 回答
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。然后你所要做的就是，对于每个人，你只需要导航类型为 (Son,Daughter) 的 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();
}
于 2011-05-28T10:17:06.727 回答
0

这是我的刺：

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();
于 2011-05-25T20:53:33.653 回答
-2

  • 有一个相对简单的 O(n log n) 算法，它在合适的顶部树的帮助下按时间顺序扫描事件。

  • 你真的不应该分配你自己解决不了的作业。

于 2011-05-23T20:03:14.673 回答