时间戳

首页 > 解决方案 > 图问题：查找两个节点是否在 O(1) 时间和每个节点 O(1) 存储中共享相同的分支

c++ - 图问题：查找两个节点是否在 O(1) 时间和每个节点 O(1) 存储中共享相同的分支

问题描述

假设我们有一个有向树（有向图）。因此，随着时间的推移，我们在主分支上构建，我们将主分支定义为从根（整个树中的第一个节点）开始的最长分支，并且在构建它时，我们可以随时构建新分支通过将新节点附加到任意节点，但大多数时候，我们建立在尖端（在最长的分支上）。

图形节点具有以下形式：

struct {
    int id;
    int prev_node_id; // this is what links nodes together
}

假设我们选择两个随机节点 X 和 Y。问题是：这些节点是否共享一个分支？

每个节点都由一个 ID 定义（基本上是加密哈希，在这里用一个 int 简化）。这个问题的一个解决方案是我们简单地从一个节点开始回到图中，直到我们遇到另一个节点。这需要遍历分支中的所有节点，因此这是 O(N)，其中 N 是分支中的节点数，它可以非常非常长（数百万个节点）。是否有任何类型的数据可以构建到可以使该操作 O(1) 的节点中，其中每个节点的数据大小也是 O(1)？

我的第一个解决方案（不好，因为每个节点的存储空间为 O(N)）：

我们将任意长素数添加到数据结构中：

struct {
    int id;
    int prev_node_id;
    ArbitraryPrecisionInt branch_index;
}

每当我们将节点附加到树的任何部分时，我们将其定义branch_index为：

branch_index_new = branch_index_old * new_prime_number;

其中新的素数来自单例生成器。假设我们有几百万个节点，这并不昂贵。至少没有那么糟糕。

那么，节点 X 和 Y 是否共享同一个分支？

X % Y == 0如果：或，答案是肯定的Y % X == 0。

问题就在这里，这个产品的规模会增长得非常快。前 1000 个素数的乘积很大。

我的第二个解决方案（有点糟糕，因为它的搜索时间为 O(log(N))，但每个节点的存储为 O(1)）：

struct {
    int id;
    int prev_node_id;
    int branch_id;
}

branch_id基本上来自单身人士。我们从 0 开始，对于我们创建的每个新节点，我们都有两种情况。

  1. 如果我们添加的节点位于树的顶端（该节点不存在其他分支），我们添加相同的值
  2. 如果该节点上已经存在分支，我们将数字加一（数字是从单例生成的，因此永远不会有重复）。

之后，我们创建一个数据库表，在其中写入每个新增量与每个值的高度（我们将高度定义为从根节点到该节点的长度）。

那么，节点 X 和 Y 是否共享同一个分支？为了回答这个问题，我们查看 X's branch_id，然后查看数据库，然后找到创建分支的高度。我们去那里，找到branch_id之前的那个点。我们一直这样做，直到我们到达根（失败）或找到branch_idY的根。

这整个故事是我试图解决的区块链问题。真正问题的细节真的很复杂，没有必要去经历。但是，如果您有兴趣，请随时与我聊天。我这么说是因为有人肯定会称之为 XY 问题。

有一个更好的方法吗？

标签： c++algorithmgraphtreetraversal

解决方案

只是为了澄清术语：当您向树添加叶子时，您希望能够选择任意两个节点并确定一个节点是否是另一个节点的祖先。

是的，你可以这样做。基本程序是：

  • 每个节点都有两个标签——一个开始标签和一个结束标签。这些就像数字一样，标签之间有一个总排序
  • 当您将新子节点添加到节点时，您为其提供位于父节点的结束标签和其最后一个子节点的结束标签之间的开始和结束标签，或者如果要添加第一个子节点，则为父节点的开始和结束标签.
  • 然后每个节点的开始和结束标签将定义与其子树相对应的范围，这样您就可以通过比较标签来测试一个节点是否在另一个节点的子树中。

当然，您不能只对这些标签使用数字，因为如果您继续将子项添加到最小的可用区间，您最终会用完位。

您可以使用字符串，因为总是可以在其他两个字符串之间生成一个字符串，但是存储是无限的，并且比较可能需要超过 O(1) 的时间。

因此，您需要某种神奇的标签类型，让您可以在任意一对标签之间添加任意数量的标签，并且仍然可以快速比较它们。

该问题称为订单维护问题：https ://en.wikipedia.org/wiki/Order-maintenance_problem

在大多数情况下，我认为最实用的方法是本文中的简单算法：https ://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf 。该论文还提到订单维护是解决您的问题的方法。

使用该算法，您可以在链表中使用数字，只要数字类型可以容纳 N 2，并且添加新条目需要分摊的 O(log N) 时间。

越来越复杂的结构可以为您提供更好的理论结果，一直到非 amoritzed O(1) 时间插入和 O(1) 时间比较，但这会变得非常复杂。

推荐阅读